Kuorilajittelu

Tässä opetusohjelmassa opit, kuinka kuoren lajittelu toimii. Löydät myös toimivia esimerkkejä kuoren lajittelusta C, C ++, Java ja Python.

Kuorilajittelu on algoritmi, joka lajittelee ensin elementit kaukana toisistaan ​​ja vähentää peräkkäin lajiteltavien elementtien välistä aikaväliä. Se on yleistetty versio lisäyslajittelusta.

Kuorilajittelussa tietyn aikavälin elementit lajitellaan. Elementtien välistä aikaa vähennetään vähitellen käytetyn sekvenssin perusteella. Kuorilajittelun suorituskyky riippuu tietyssä syötetaulukossa käytetyn sekvenssin tyypistä.

Jotkut optimaalisista sekvensseistä ovat:

  • Shellin alkuperäinen järjestys: N/2 , N/4 ,… , 1
  • Knuthin lisäykset: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewickin lisäykset: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbardin lisäykset: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernovin ja Stasevichin lisäys: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Kuinka Shell-lajittelu toimii?

  1. Oletetaan, että meidän on lajiteltava seuraava taulukko. Alkuperäinen taulukko
  2. Käytämme kuoren alkuperäistä sekvenssiä (N/2, N/4,… 1intervallina algoritmissamme.
    Ensimmäisessä silmukassa, jos matriisin koko on N = 8silloin, välillä olevat elementit N/2 = 4verrataan ja vaihdetaan, jos ne eivät ole kunnossa.
    1. 0. elementtiä verrataan neljänteen elementtiin.
    2. Jos 0. elementti on suurempi kuin 4. elementti, 4. elementti tallennetaan ensin tempmuuttujaan ja 0thelementti (eli suurempi elementti) tallennetaan 4thsijaintiin ja elementti, johon tallennetaan, temptallennetaan 0thsijaintiin. Järjestä elementit uudelleen n / 2 välein.
      Tämä prosessi jatkuu kaikille muille elementeille. Järjestä kaikki elementit uudelleen n / 2 välein
  3. Toisessa silmukassa N/4 = 8/4 = 2otetaan aikaväli ja taas järjestetään näillä väleillä olevat elementit. Järjestä elementit uudelleen n / 4 välein.
    Saatat hämmentyä tässä vaiheessa. Matriisin kaikkia nykyisellä aikavälillä olevia elementtejä verrataan.
    Elementtejä 4. ja 2ndsijainnissa verrataan. Myös 2. ja 0thsijainnin elementtejä verrataan. Matriisin kaikkia nykyisellä aikavälillä olevia elementtejä verrataan.
  4. Sama prosessi jatkuu muille elementeille. Järjestä kaikki elementit uudelleen n / 4 välein
  5. Lopuksi, kun intervalli on, N/8 = 8/8 =1taulukon elementit, jotka ovat välillä 1, lajitellaan. Matriisi on nyt täysin lajiteltu. Järjestä elementit uudelleen n / 8 välein

Shell-lajittelualgoritmi

 shellSort (matriisi, koko) aikavälille i <- koko / 2n alaspäin 1 kullekin taulukon jokaiselle aikavälille "i" lajittelee kaikki elementit välin "i" lopussa shellSort

Python-, Java- ja C / C ++ -esimerkkejä

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

Monimutkaisuus

Kuorilajittelu on epävakaa lajittelualgoritmi, koska tämä algoritmi ei tutki välien välissä olevia elementtejä.

Ajan monimutkaisuus

  • Pahimman tapauksen monimutkaisuus : pienempi tai yhtä suuri kuin pahimman tapauksen monimutkaisuus kuoren lajittelussa on aina pienempi tai yhtä suuri kuin . Mukaan Poonen Lause, pahimmassa tapauksessa monimutkaisuutta kuori sort on tai tai tai jotain siltä väliltä.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Parhaan tapauksen monimutkaisuus : O(n*log n)
    Kun matriisi on jo lajiteltu, vertailujen kokonaismäärä kullekin aikavälille (tai lisäykselle) on yhtä suuri kuin taulukon koko.
  • Keskimääräinen tapauksen monimutkaisuus : O(n*log n)
    Se on noin .O(n1.25)

Monimutkaisuus riippuu valitusta aikavälistä. Edellä mainitut monimutkaisuudet eroavat eri valittujen lisäyssekvenssien suhteen. Paras lisäysjärjestys on tuntematon.

Avaruuden monimutkaisuus:

Avaruuden monimutkaisuus kuoren lajittelulle on O(1).

Shell-lajittelusovellukset

Kuoren lajittelua käytetään, kun:

  • pinon soittaminen on yläpuolella. uClibc-kirjasto käyttää tällaista.
  • rekursio ylittää rajan. bzip2-kompressori käyttää sitä.
  • Lisälajittelu ei toimi hyvin, kun läheiset elementit ovat kaukana toisistaan. Kuorilajittelu auttaa vähentämään läheisten elementtien välistä etäisyyttä. Siten suoritettavia vaihtoja on vähemmän.

Mielenkiintoisia artikkeleita...