Quicksort
Hajota ja hallitse.
Quicksort on ilmainen C Academy-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu C Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. C Academy-kurssilla on yhteensä 4 oppituntia.
Jaa ja hallitse
Quicksort on jaa ja hallitse -periaatteeseen perustuva lajittelumenetelmä. Se valitsee jakajan, järjestää taulukon niin, että pienemmät alkiot ovat vasemmalla ja suuremmat oikealla, ja lajittelee sitten kummankin puolen rekursiivisesti.
Keskimääräinen aikavaativuus on O(n log n).
Osiointivaihe
Keskeinen ajatus on osiointi: järjestä taulukko jakajan ympärille niin, että kaikki jakajan vasemmalla puolella olevat alkiot ovat pienempiä ja oikealla puolella olevat suurempia. Jakaja päätyy tällöin lopulliseen lajiteltuun paikkaansa.
Lomuton osiointimenetelmä
Lomuton menetelmä käyttää viimeistä alkiota jakajana. Se ylläpitää indeksiä i pienempien alkioiden rajalle ja vaihtaa alkioita taulukkoa läpikäydessään.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Rekursiivinen lajittelu
Quicksort kutsuu osiointia ja suorittaa sitten rekursion jakajan ympärillä oleville kahdelle alitaulukolle. Perustapaus on alitaulukko, jonka koko on 0 tai 1.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Hyvän jakajan valitseminen
Huono jakaja (esimerkiksi aina viimeinen alkio valmiiksi lajitellulla syötteellä) aiheuttaa O(n:neliö)-aikavaativuuden. Paremmat valinnat jakavat osiot tasaisemmin.
- Kolmen mediaani
- Satunnainen jakaja
Kolmen mediaani
Kolmen mediaani valitsee jakajaksi ensimmäisen, keskimmäisen ja viimeisen alkion mediaanin, mikä ehkäisee valmiiksi lajitellun datan huonoimman tapauksen.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}Huonoimman tapauksen analyysi
Jos jokainen osio erottaa vain yhden alkion, rekursion syvyys kasvaa arvoon n ja kustannus on O(n:neliö). Näin tapahtuu käytettäessä kiinteää jakajaa lajitellulla tai käänteisessä järjestyksessä olevalla syötteellä.
Satunnaistaminen tekee huonoimmasta tapauksesta erittäin epätodennäköisen.
Satunnainen jakaja
Kun satunnainen alkio vaihdetaan jakajan paikalle ennen osiointia, menetelmä kestää paremmin tarkoituksellisesti hankalat syötteet.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}Paikallaan tapahtuva eikä vakaa
Quicksort lajittelee paikallaan käyttäen keskimäärin vain O(log n) pinotilaa. Se ei kuitenkaan ole vakaa: samanarvoisten alkioiden järjestys voi muuttua osioinnin aikana tehtävien vaihtojen vuoksi.
Hännän rekursion optimointi
Kun rekursio tehdään ensin pienemmälle puolikkaalle ja suurempi käsitellään silmukassa, pinon syvyys rajoittuu arvoon O(log n), mikä estää pinon ylivuodon suurilla taulukoilla.
Merkkijonojen lajittelu
Sama rakenne lajittelee minkä tahansa vertailtavissa olevan tyypin. Tässä quicksort järjestää kokonaislukutaulukon, mutta vertailun vaihtamalla voit käsitellä myös muita tyyppejä.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Pikatarkistus
Testaa ymmärryksesi quicksortista.
Kertaus
Opit quicksortin.
- Osioi taulukko jakajan ympäriltä ja suorita sitten rekursio kummallekin puolelle
- Keskimäärin O(n log n), huonoimmassa tapauksessa O(n:neliö)
- Kolmen mediaani tai satunnaiset jakajat ehkäisevät huonoimman tapauksen
- Lajittelee paikallaan, mutta ei ole vakaa
Opi C tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 39
- Oppitunnit
- 144
Usein kysytyt kysymykset
Onko oppitunti ”Quicksort” ilmainen?
Kyllä – oppitunnin ”Quicksort” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko C Academy-kurssin, päivitä CoddyKit PROhon. C Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Quicksort”?
Hajota ja hallitse. Harjoittelet C Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni C Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin C Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Quicksort”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä C Academy-oppitunnilla?
Kyllä. Jokainen C Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.