Shell Sorteren

In deze tutorial leer je hoe shell-sortering werkt. Ook vindt u werkende voorbeelden van shell-sortering in C, C ++, Java en Python.

Shell-sortering is een algoritme dat eerst de elementen ver uit elkaar sorteert en achtereenvolgens het interval tussen de te sorteren elementen verkleint. Het is een algemene versie van invoegsortering.

Bij shell-sortering worden elementen met een specifiek interval gesorteerd. Het interval tussen de elementen wordt geleidelijk verkleind op basis van de gebruikte volgorde. De prestatie van de shell-sortering hangt af van het type reeks dat wordt gebruikt voor een gegeven invoerarray.

Enkele van de optimale gebruikte sequenties zijn:

• Shell's oorspronkelijke volgorde: N/2 , N/4 ,… , 1
• Knuth's verhogingen: 1, 4, 13,… , (3k - 1) / 2
• Sedgewick's stappen: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
• Hibbard's verhogingen: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Papernov & Stasevich stap: 1, 3, 5, 9, 17, 33, 65,…
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Hoe werkt Shell Sort?

1. Stel dat we de volgende array moeten sorteren. Eerste array
2. We gebruiken de oorspronkelijke volgorde van de shell (N/2, N/4,… 1) als intervallen in ons algoritme.
   In de eerste lus, als de array-grootte N = 8dan is, worden de elementen die in het interval van N/2 = 4liggen vergeleken en verwisseld als ze niet in orde zijn.
   1. Het 0e element wordt vergeleken met het 4e element.
   2. Als het 0e element groter is dan het 4e, wordt het 4e element eerst in tempvariabele opgeslagen en wordt het 0thelement (dat wil zeggen grotere element) in de 4thpositie opgeslagen en wordt het element dat tempis opgeslagen in de 0thpositie opgeslagen . Herschik de elementen met een interval van n / 2
      Dit proces gaat door voor alle overige elementen. Herschik alle elementen met een interval van n / 2
3. In de tweede lus wordt een interval van N/4 = 8/4 = 2genomen en opnieuw worden de elementen die op deze intervallen liggen gesorteerd. Herschik de elementen met een interval van n / 4
   U kunt op dit punt in de war raken. Alle elementen in de array die op het huidige interval liggen, worden vergeleken.
   De elementen op 4 en 2ndpositie worden vergeleken. De elementen op 2e en 0thpositie worden ook vergeleken. Alle elementen in de array die op het huidige interval liggen, worden vergeleken.
4. Hetzelfde proces gaat door voor de resterende elementen. Herschik alle elementen met een interval van n / 4
5. Ten slotte, wanneer het interval is, N/8 = 8/8 =1worden de array-elementen die op het interval van 1 liggen gesorteerd. De array is nu volledig gesorteerd. Herschik de elementen met een interval van n / 8

Shell-sorteeralgoritme

 shellSort (array, size) voor interval i <- size / 2n tot 1 voor elk interval "i" in array sorteer alle elementen op interval "i" einde shellSort

Python, Java en C / C ++ voorbeelden

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

Complexiteit

Shell-sortering is een onstabiel sorteeralgoritme omdat dit algoritme de elementen tussen de intervallen niet onderzoekt.

Tijdscomplexiteit

• Worst Case Complexity : minder dan of gelijk aan Worst case complexiteit voor shell-sortering is altijd kleiner dan of gelijk aan . Volgens de stelling van Poonen is de worst case-complexiteit voor shell-sortering of of of iets daartussenin.O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
• Complexiteit in het beste geval : O(n*log n)
  als de array al is gesorteerd, is het totale aantal vergelijkingen voor elk interval (of increment) gelijk aan de grootte van de array.
• Gemiddelde casuscomplexiteit : O(n*log n)
  het is rond .O(n1.25)

De complexiteit hangt af van het gekozen interval. De bovenstaande complexiteit verschilt voor de verschillende gekozen incrementsequenties. De beste stapvolgorde is onbekend.

Ruimtecomplexiteit:

De ruimtecomplexiteit voor shell-sortering is O(1).

Shell Sort-toepassingen

Shell-sortering wordt gebruikt wanneer:

• het callen van een stack is overhead. uClibc-bibliotheek gebruikt deze soort.
• recursie overschrijdt een limiet. bzip2-compressor gebruikt het.
• Invoegsortering werkt niet goed als de sluitelementen ver uit elkaar staan. Shell-sortering helpt bij het verkleinen van de afstand tussen de nabije elementen. Er hoeven dus minder swappings te worden uitgevoerd.