Сортировка оболочки

В этом руководстве вы узнаете, как работает сортировка оболочки. Также вы найдете рабочие примеры сортировки оболочки на 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… .

Как работает сортировка оболочки?

  1. Допустим, нам нужно отсортировать следующий массив. Исходный массив
  2. Мы используем исходную последовательность оболочки (N/2, N/4,… 1) в качестве интервалов в нашем алгоритме.
    В первом цикле, если размер массива равен N = 8then, элементы, лежащие в интервале N/2 = 4, сравниваются и меняются местами, если они не в порядке.
    1. 0-й элемент сравнивается с 4-м элементом.
    2. Если 0-й элемент больше 4-го, то 4-й элемент сначала сохраняется в tempпеременной, а 0thэлемент (т. Е. Больший элемент) сохраняется в 4thпозиции, а элемент, хранящийся в temp, сохраняется в этой 0thпозиции. Переставьте элементы с интервалом n / 2.
      Этот процесс продолжается для всех остальных элементов. Переставьте все элементы с интервалом n / 2
  3. Во втором цикле N/4 = 8/4 = 2берется интервал и снова сортируются элементы, лежащие в этих интервалах. Переставьте элементы с интервалом n / 4. Здесь
    вы можете запутаться. Сравниваются все элементы массива, лежащие в текущем интервале. Сравниваются
    элементы на 4-й 2ndпозиции и позиции. 0thТакже сравниваются элементы на 2-й позиции и позиции. Сравниваются все элементы массива, лежащие в текущем интервале.
  4. То же самое происходит и с остальными элементами. Переставьте все элементы с интервалом n / 4
  5. Наконец, когда интервал равен, 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 around O(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.
  • Сортировка вставкой не работает, когда близкие элементы далеко друг от друга. Сортировка шелла помогает сократить расстояние между близкими элементами. Таким образом, количество замен будет меньше.

Интересные статьи...