Shell Sort

I denne vejledning lærer du, hvordan shell-sortering fungerer. Du finder også arbejdseksempler på shell-sortering i C, C ++, Java og Python.

Shell-sortering er en algoritme, der først sorterer elementerne langt fra hinanden og successivt reducerer intervallet mellem de elementer, der skal sorteres. Det er en generaliseret version af indsættelsessortering.

I shell-sortering sorteres elementer med et bestemt interval. Intervallet mellem elementerne reduceres gradvist baseret på den anvendte sekvens. Ydelsen af ​​shell-sorteringen afhænger af typen af ​​sekvens, der bruges til et givet input-array.

Nogle af de optimale anvendte sekvenser er:

  • Shells originale sekvens: N/2 , N/4 ,… , 1
  • Knuth's trin: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewicks trin: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbards trin: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernov & Stasevich stigning: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Hvordan fungerer Shell Sort?

  1. Antag, at vi skal sortere følgende array. Indledende array
  2. Vi bruger skalets originale sekvens (N/2, N/4,… 1) som intervaller i vores algoritme.
    I den første loop, hvis matrixstørrelsen er N = 8, N/2 = 4sammenlignes elementerne, der ligger i intervallet, og byttes, hvis de ikke er i orden.
    1. Det 0. element sammenlignes med det 4. element.
    2. Hvis det 0. element er større end det fjerde, lagres det 4. element først i tempvariabel, og 0thelementet (dvs. større element) lagres i 4thpositionen, og elementet, der er gemt i temp, lagres i 0thpositionen. Omarranger elementerne med n / 2-interval
      Denne proces fortsætter for alle de resterende elementer. Omarranger alle elementerne med n / 2-intervallet
  3. I den anden sløjfe tages et interval på N/4 = 8/4 = 2, og igen sorteres elementerne, der ligger ved disse intervaller. Omarranger elementerne med n / 4 interval
    Du kan blive forvirret på dette tidspunkt. Alle elementer i arrayet, der ligger i det aktuelle interval, sammenlignes.
    Elementerne på 4. og 2ndposition sammenlignes. Elementerne på 2. og 0thposition sammenlignes også. Alle elementer i arrayet, der ligger i det aktuelle interval, sammenlignes.
  4. Den samme proces fortsætter for de resterende elementer. Omarranger alle elementerne med n / 4-intervallet
  5. Endelig, når intervallet er, N/8 = 8/8 =1sorteres arrayelementerne, der ligger i intervallet 1. Arrayet er nu fuldstændigt sorteret. Omarranger elementerne med n / 8-intervallet

Skalsorteringsalgoritme

 shellSort (array, størrelse) for interval i <- størrelse / 2n ned til 1 for hvert interval "i" i array sorterer alle elementerne i interval "i" end shellSort

Python, Java og C / C ++ eksempler

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); )

Kompleksitet

Shell-sortering er en ustabil sorteringsalgoritme, fordi denne algoritme ikke undersøger de elementer, der ligger mellem intervallerne.

Tidskompleksitet

  • Kompleksitet i værste tilfælde : mindre end eller lig med kompleksiteten i værste tilfælde er altid mindre end eller lig med . Ifølge Poonen Sætning, værste fald kompleksitet for skallen slags er eller eller eller noget midt imellem.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Best case-kompleksitet : O(n*log n)
    Når arrayet allerede er sorteret, er det samlede antal sammenligninger for hvert interval (eller inkrement) lig med størrelsen på arrayet.
  • Gennemsnitlig sagskompleksitet : O(n*log n)
    Det er omkring .O(n1.25)

Kompleksiteten afhænger af det valgte interval. Ovenstående kompleksitet adskiller sig for forskellige valgte sekvenser. Bedste forøgelsessekvens er ukendt.

Rumkompleksitet:

Rumkompleksiteten for skalesortering er O(1).

Shell Sort applikationer

Skalsortering bruges, når:

  • at kalde en stak er overhead. uClibc-biblioteket bruger denne slags.
  • rekursion overstiger en grænse. bzip2 kompressor bruger det.
  • Indsætningssortering fungerer ikke godt, når de tætte elementer er langt fra hinanden. Skalsortering hjælper med at reducere afstanden mellem de tætte elementer. Således vil der være færre antal swappings, der skal udføres.

Interessante artikler...