В этом руководстве вы узнаете, как работает сортировка оболочки. Также вы найдете рабочие примеры сортировки оболочки на C, C ++, Java и Python.
Сортировка оболочки - это алгоритм, который сначала сортирует элементы далеко друг от друга и последовательно уменьшает интервал между элементами, которые нужно отсортировать. Это обобщенная версия сортировки вставкой.
При сортировке оболочки сортируются элементы с определенным интервалом. Интервал между элементами постепенно уменьшается в зависимости от используемой последовательности. Производительность сортировки оболочки зависит от типа последовательности, используемой для данного входного массива.
Некоторые из используемых оптимальных последовательностей:
- Исходная последовательность Shell:
N/2 , N/4 ,… , 1
- Приращения Кнута:
1, 4, 13,… , (3k - 1) / 2
- Приращения Седжвика:
1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
- Приращения Хиббарда:
1, 3, 7, 15, 31, 63, 127, 255, 511…
- Папернов и Стасевич приращение:
1, 3, 5, 9, 17, 33, 65,…
- Пратт:
1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .
Как работает сортировка оболочки?
- Допустим, нам нужно отсортировать следующий массив.
Исходный массив
- Мы используем исходную последовательность оболочки
(N/2, N/4,… 1
) в качестве интервалов в нашем алгоритме.
В первом цикле, если размер массива равенN = 8
then, элементы, лежащие в интервалеN/2 = 4
, сравниваются и меняются местами, если они не в порядке.- 0-й элемент сравнивается с 4-м элементом.
- Если 0-й элемент больше 4-го, то 4-й элемент сначала сохраняется в
temp
переменной, а0th
элемент (т. Е. Больший элемент) сохраняется в4th
позиции, а элемент, хранящийся вtemp
, сохраняется в этой0th
позиции.Переставьте элементы с интервалом n / 2.
Этот процесс продолжается для всех остальных элементов.Переставьте все элементы с интервалом n / 2
- Во втором цикле
N/4 = 8/4 = 2
берется интервал и снова сортируются элементы, лежащие в этих интервалах.Переставьте элементы с интервалом n / 4. Здесь
вы можете запутаться.Сравниваются все элементы массива, лежащие в текущем интервале. Сравниваются
элементы на 4-й2nd
позиции и позиции.0th
Также сравниваются элементы на 2-й позиции и позиции. Сравниваются все элементы массива, лежащие в текущем интервале. - То же самое происходит и с остальными элементами.
Переставьте все элементы с интервалом n / 4
- Наконец, когда интервал равен,
N/8 = 8/8 =1
то элементы массива, лежащие в интервале 1, сортируются. Теперь массив полностью отсортирован.Переставьте элементы с интервалом n / 8
Алгоритм сортировки оболочки
shellSort (array, size) для интервала i <- size / 2n до 1 для каждого интервала "i" в массиве отсортировать все элементы в интервале "i" end shellSort
Примеры Python, Java и C / C ++
Python Java C C ++# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); )
// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); )
Сложность
Сортировка оболочки - это нестабильный алгоритм сортировки, потому что этот алгоритм не проверяет элементы, лежащие между интервалами.
Сложность времени
- Сложность наихудшего случая : меньше или равна Сложность наихудшего случая для сортировки оболочки всегда меньше или равна . Согласно теореме Poonen, в худшем случае сложность для рода оболочечной или или или что - то между ними.
O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)
Θ(Nlog N)2/log log N)
Θ(N(log N)2)
- Best Case Complexity:
O(n*log n)
When the array is already sorted, the total number of comparisons for each interval (or increment) is equal to the size of the array. - Average Case Complexity:
O(n*log n)
It is aroundO(n1.25)
.
The complexity depends on the interval chosen. The above complexities differ for different increment sequences chosen. Best increment sequence is unknown.
Space Complexity:
The space complexity for shell sort is O(1)
.
Shell Sort Applications
Shell sort is used when:
- calling a stack is overhead. uClibc library uses this sort.
- recursion exceeds a limit. bzip2 compressor uses it.
- Сортировка вставкой не работает, когда близкие элементы далеко друг от друга. Сортировка шелла помогает сократить расстояние между близкими элементами. Таким образом, количество замен будет меньше.