Sortare Shell

În acest tutorial, veți afla cum funcționează sortarea shell-urilor. De asemenea, veți găsi exemple de lucru de sortare shell în C, C ++, Java și Python.

Sortarea Shell este un algoritm care sortează mai întâi elementele depărtate unul de altul și reduce succesiv intervalul dintre elementele de sortat. Este o versiune generalizată a sortării prin inserție.

În sortarea shell-ului, elementele la un anumit interval sunt sortate. Intervalul dintre elemente este redus treptat pe baza secvenței utilizate. Performanța sortării shell depinde de tipul secvenței utilizate pentru o matrice de intrare dată.

Unele dintre secvențele optime utilizate sunt:

  • Secvența originală a lui Shell: N/2 , N/4 ,… , 1
  • Incrementările lui Knuth: 1, 4, 13,… , (3k - 1) / 2
  • Incrementările lui Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Incrementările lui Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Increment Papernov și Stasevici: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Cum funcționează sortarea Shell?

  1. Să presupunem că trebuie să sortăm următoarea matrice. Matricea inițială
  2. Folosim secvența originală a shell-ului (N/2, N/4,… 1) ca intervale în algoritmul nostru.
    În prima buclă, dacă dimensiunea matricei este N = 8atunci, elementele situate la interval de N/2 = 4sunt comparate și schimbate dacă nu sunt în ordine.
    1. Elementul 0 este comparat cu elementul 4.
    2. Dacă elementul 0 este mai mare decât cel de-al patrulea, atunci al patrulea element este stocat mai întâi în tempvariabilă și 0thelementul (adică elementul mai mare) este stocat în 4thpoziție și elementul stocat în tempeste stocat în 0thpoziție. Rearanjați elementele la interval n / 2
      Acest proces continuă pentru toate elementele rămase. Rearanjați toate elementele la un interval n / 2
  3. În cea de-a doua buclă, se ia un interval de N/4 = 8/4 = 2și din nou sunt sortate elementele situate la aceste intervale. Rearanjați elementele la interval n / 4
    S-ar putea să vă confundați în acest moment. Se compară toate elementele din matrice situate la intervalul curent.
    Elementele de la 4 și 2ndpoziție sunt comparate. Elementele de la 2 și 0thpoziție sunt, de asemenea, comparate. Se compară toate elementele din matrice situate la intervalul curent.
  4. Același proces continuă și pentru elementele rămase. Rearanjați toate elementele la un interval n / 4
  5. În cele din urmă, atunci când intervalul este N/8 = 8/8 =1atunci sunt sortate elementele matrice situate la intervalul 1. Matricea este acum complet sortată. Rearanjați elementele la un interval n / 8

Algoritmul Sortare Shell

 shellSort (matrice, dimensiune) pentru intervalul i <- dimensiune / 2n până la 1 pentru fiecare interval "i" din matrică sortează toate elementele la intervalul "i" final shellSort

Exemple Python, Java și 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); )

Complexitate

Sortarea Shell este un algoritm instabil de sortare, deoarece acest algoritm nu examinează elementele aflate între intervale.

Complexitatea timpului

  • Complexitatea cazului cel mai rău : mai mică sau egală cu Complexitatea cazului cel mai rău pentru sortarea shell este întotdeauna mai mică sau egală cu . Conform teoremei lui Poonen, cel mai rău caz de complexitate pentru tipul de shell este sau sau sau ceva între ele.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.
  • Sortarea prin inserție nu funcționează bine atunci când elementele apropiate sunt la distanță. Sortarea Shell ajută la reducerea distanței dintre elementele apropiate. Astfel, va exista un număr mai mic de swapp-uri care trebuie efectuate.

Articole interesante...