Сортиране на черупката

В този урок ще научите как работи сортирането на черупки. Също така ще намерите работещи примери за сортиране на черупки в C, C ++, Java и Python.

Сортирането на черупки е алгоритъм, който първо сортира елементите далеч един от друг и последователно намалява интервала между сортираните елементи. Това е обобщена версия на сортиране на вмъкване.

При сортиране на черупки се сортират елементи на определен интервал. Интервалът между елементите постепенно намалява въз основа на използваната последователност. Изпълнението на сортирането на черупката зависи от типа на последователността, използвана за даден входен масив.

Някои от използваните оптимални последователности са:

  • Оригиналната последователност на Shell: N/2 , N/4 ,… , 1
  • Прирастванията на Knuth: 1, 4, 13,… , (3k - 1) / 2
  • Прирастванията на Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Прирастванията на Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Прирастване на Papernov & Stasevich: 1, 3, 5, 9, 17, 33, 65,…
  • Прат: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Как работи сортирането на Shell?

  1. Да предположим, че трябва да сортираме следния масив. Първоначален масив
  2. Използваме оригиналната последователност на черупката (N/2, N/4,… 1) като интервали в нашия алгоритъм.
    В първия цикъл, ако размерът на масива е N = 8тогава, елементите, лежащи в интервала от, 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позиция. Елементите на 2-ро и 0thпозиция също се сравняват. Всички елементи в масива, разположени в текущия интервал, се сравняват.
  4. Същият процес продължава и за останалите елементи. Пренаредете всички елементи на интервал n / 4
  5. И накрая, когато интервалът е N/8 = 8/8 =1тогава, сортират се елементите на масива, лежащи в интервала 1 Масивът вече е напълно сортиран. Пренаредете елементите на интервал n / 8

Алгоритъм за сортиране на черупки

 shellSort (масив, размер) за интервал i <- размер / 2n до 1 за всеки интервал "i" в масива сортиране на всички елементи в интервал "i" край 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)
  • Най-добрата сложност : O(n*log n)
    Когато масивът вече е сортиран, общият брой сравнения за всеки интервал (или увеличение) е равен на размера на масива.
  • Средна сложност на случая : O(n*log n)
    Около .O(n1.25)

Сложността зависи от избрания интервал. Горните сложности се различават при различните избрани последователности на нарастване. Най-добрата последователност на нарастване е неизвестна.

Космическа сложност:

Сложността на пространството за сортиране на черупки е O(1).

Приложения за сортиране на черупки

Сортирането на черупки се използва, когато:

  • извикването на стека е излишно. Библиотеката uClibc използва този сорт.
  • рекурсията надвишава лимит. bzip2 компресорът го използва.
  • Сортирането при вмъкване не се представя добре, когато близките елементи са отдалечени. Сортирането на черупки помага за намаляване на разстоянието между близките елементи. По този начин ще има по-малък брой замени, които трябва да бъдат извършени.

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