Схелл Сорт

У овом упутству ћете научити како сортирање љуске функционише. Такође, наћи ћете радне примере сортирања љуске у Ц, Ц ++, Јава и Питхон.

Сортирање љуске је алгоритам који прво сортира елементе међусобно далеко и узастопно смањује интервал између елемената који се сортирају. То је уопштена верзија сортирања уметања.

У сортирању љуске, елементи у одређеном интервалу се сортирају. Интервал између елемената се постепено смањује на основу употребљене секвенце. Учинак сортирања љуске зависи од врсте секвенце која се користи за дати улазни низ.

Неке од оптималних секвенци које се користе су:

  • Оригинални слијед шкољке: 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 = 8тада, елементи који леже у интервалу од N/2 = 4упоређују се и замењују ако нису у реду.
    1. 0. елемент се упоређује са 4. елементом.
    2. Ако је тада 0-и елемент већи од четвртог, четврти елемент се прво чува у tempпроменљивој, а 0thелемент (тј. Већи елемент) се чува у 4thпозицији, а елемент који tempсе чува у њему 0th. Прераспоредите елементе у интервалу од н / 2
      Овај поступак се наставља за све преостале елементе. Преуредите све елементе у интервалу н / 2
  3. У другој петљи N/4 = 8/4 = 2се узима интервал од и поново се сортирају елементи који леже у тим интервалима. Прераспоредите елементе у интервалу н / 4
    У овом тренутку можете се збунити. Упоређују се сви елементи у низу који леже у тренутном интервалу.
    Упоређују се елементи на 4. и 2ndположају. 0thТакође се упоређују елементи на 2. месту и положају. Упоређују се сви елементи у низу који леже у тренутном интервалу.
  4. Исти поступак тече и за преостале елементе. Преуредите све елементе у интервалу н / 4
  5. Коначно, када је интервал N/8 = 8/8 =1тада се разврставају елементи низа који леже у интервалу 1. Низ је сада потпуно сортиран. Преуредите елементе у интервалу н / 8

Алгоритам сортирања шкољке

 схеллСорт (низ, величина) за интервал и <- величина / 2н до 1 за сваки интервал "и" у низу сортирај све елементе на крају интервала "и" на крају схеллСорт

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
# 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); )

Сложеност

Сортирање љуске је нестабилан алгоритам сортирања јер овај алгоритам не испитује елементе који се налазе између интервала.

Сложеност времена

  • Сложеност најгорег случаја : мање или једнако сложености Најгоре сложености за сортирање љуске увек је мање или једнако . Према Поонен теорема, најгори случај комплексност за схеллсорт је или или или нешто између.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).

Апликације за сортирање шкољки

Сортирање љуске користи се када:

  • позивање стека је изнад главе. Библиотека уЦлибц користи ову врсту.
  • рекурзија прелази ограничење. бзип2 компресор га користи.
  • Сортирање уметања нема добар учинак када су блиски елементи међусобно удаљени. Сортирање љуске помаже у смањењу удаљености између блиских елемената. Тако ће бити изведен мањи број замена.

Занимљиви Чланци...