Tartalomjegyzék:
Meghatározás - Mit jelent a Quicksort?
A Quicksort egy népszerű válogatási algoritmus, amely a gyakorlatban gyakran gyorsabb, mint más rendezési algoritmus. Az osztási és meghódítási stratégiát használja az adatelemek gyors rendezéséhez, ha egy nagy tömböt két kisebb tömbre oszt fel. Ezt Charles Antony Richard Hoare (közismert néven CAR Hoare vagy Tony Hoare) fejlesztette ki 1960-ban a Nemzeti Fizikai Laboratórium gépi fordításának projektjeként.A Techopedia magyarázza a Quicksortot
A Quicksort egy olyan algoritmus, amelyet a tömbben lévő elemek gyors rendezéséhez használnak, függetlenül attól, hogy mekkora a tömb. Meglehetősen méretezhető, viszonylag jól működik kis és nagy adatkészleteknél, és könnyű megvalósítani, kevés időbonyolultsággal. Ezt megosztási és hódítási módszerrel hajtja végre, amely egy nagy tömböt ketté oszt fel és kisméretre osztja ezt a folyamatot az összes létrehozott tömbre, amíg a rendezés befejeződik.
A gyorskeresési algoritmust a következőképpen hajtjuk végre:
- A tömbből egy fordulópontot választunk.
- A tömb átrendezése úgy történik, hogy az összes forgatókészletnél kisebb érték elmozduljon előtte, és az összes forgatókészletnél nagyobb érték elmozduljon utána, az értékek megegyeznek a forgás mindkét irányba. Amikor ez megtörtént, a pivot a végső helyzetében van.
- A fenti lépést megismételjük minden kisebb értékű alcsoport esetében, és külön-külön megismételjük a nagyobb értékekkel rendelkező alcsoport számára.
Ezt addig ismételjük, amíg a teljes tömb rendezésre nem kerül.
