Senda inn spurningu
Sólin Sólin Rís 05:40 • sest 21:16 í Reykjavík
Tunglið Tunglið Rís 15:13 • Sest 05:59 í Reykjavík
Flóð Flóð Árdegis: 03:57 • Síðdegis: 16:31 í Reykjavík
Fjaran Fjara Árdegis: 10:23 • Síðdegis: 22:34 í Reykjavík
Visit the English version

Flokkun:

Náttúruvísindi og verkfræði Tölvunarfræði

Hvernig er stærðfræðileg skýring á Quicksort algoritmanum?

Hjálmtýr Hafsteinsson

Spurningin í heild er sem hér segir:

Hvernig er stærðfræðileg skýring á Quicksort algoritmanum? Er til hraðari algoritmi til þess að raða gögnum og ef svo er, hvernig er hann?

Til eru ýmsar útgáfur af Quicksort röðunaraðferðinni, en grunnaðferðinni má lýsa þannig að byrjað er á að velja svokallað vendistak (á ensku "pivot"). Þetta gæti til dæmis verið stakið sem er í fyrsta sæti listans sem á að raða. Listanum er síðan skipt upp í tvo hluta, þannig að í annan hlutann fara þau stök sem eru minni en vendistakið en í hinn þau sem eru stærri. Þessum hlutlistum, sem hvor um sig er minni en upphaflegi listinn, er síðan raðað með Quicksort aðferðinni. Þegar þeim hefur verið raðað er einfaldlega hægt að skeyta þeim saman til að fá raðaða útgáfu af upphaflega listanum.

Þessi lýsing er ekki alveg augljós, enda er Quicksort ekki aðferð sem við myndum sjálf nota til að raða hlutum í höndunum. Til þess eru of mörg smáatriði sem þarf að halda utanum. Fólk á ekki gott með það, en tölvum hentar það mun betur.

Skoðum dæmi um hvernig Quicksort myndi raða 7 staka listanum: 75, 40, 8, 91, 46, 50, 87. Við byrjum á að velja vendistak. Það er alltaf valið á sama hátt, t.d. stakið í fyrsta sæti. Hér er það talan 75. Við skiptum listanum upp í tvennt, þar sem annar hlutinn hefur allar tölur sem eru minni en 75, en hinn allar sem eru stærri en 75. Fyrri listinn verður 40, 8, 46, 50 og sá seinni verður 91, 87. Athugið að við rennum í gegnum upphaflega listann og setjum stök annað hvort í fyrri eða seinni hlutlistann.

Nú höldum við áfram og röðum þessum tveimur listum sjálfstætt með Quicksort. Fyrri listinn er 40, 8, 46, 50. Við veljum aftur sem vendistak stakið sem er í fyrsta sætinu, en það er 40. Skiptum listanum upp í tvennt: 8 annars vegar og 46, 50 hins vegar. Nú eigum við að raða þessum tveimur listum með Quicksort. Eins staks listi er raðaður, svo að listinn 8 er raðaður. Það vill líka þannig til að hinn listinn er raðaður, en ef við vinnum blint samkvæmt Quicksort aðferðinni þá er 46 valið sem vendistak, annar listinn (sá með minni stökunum) er tómur, en hinn hefur aðeins eitt stak.

Þegar báðum hlutlistunum hefur verið raðað þá er þeim skeytt saman ásamt vendistakinu. Við fáum því listann 8, vendistakið 40 og listann 46, 50. Það gefur listann 8, 40, 46, 50. Þá er sá listi orðinn raðaður og við eigum aðeins eftir að raða seinni listanum í efsta laginu, sem var 91, 87. Þar er 91 valið sem vendistak, annar listinn verður bara 87, en hinn tómur. Við samskeytinguna fæst 87, 91. Því er hægt að skeyta saman á efsta laginu: annar listinn er 8, 40, 46, 50, vendistakið er 75, hinn listinn er 87, 91. Niðurstaðan verður því 8, 40, 46, 50, 75, 87, 91. Á myndinni sést þetta ferli betur.



Einnig sést nokkuð vel af þessu dæmi hversvegna ekki er fýsilegt að nota Quicksort til að raða hlutum í höndunum. Halda þarf utan um marga hlutlista sem eru mislangt komnir í röðunarferlinu. Erfitt er fyrir fólk að muna eftir öllum þessum hlutlistum og stöðu þeirra. Fyrir tölvur er þetta hins vegar ekkert mál.

Af dæminu að ráða virðist þessi aðferð ekki sérlega hraðvirk þar sem hún virðist krefjast mikillar vinnu kringum lista með mjög fáum stökum. Reyndar er Quicksort ekki besta röðunaraðferðin fyrir fá stök. Aðrar aðferðir eru oftast betri ef aðeins á að raða 2-5 stökum. Það sem gerir Quicksort hraðvirka er skipting stakanna um vendistakið. Jafnvel þótt vendistakið sé valið á mjög einfaldan hátt (til dæmis alltaf stakið í fyrsta sætinu) skiptir það oftast listanum í nokkurn veginn jafnstóra hluta. Athugið að þetta á ekki við þegar listinn er þegar raðaður, því að þá verður annar listinn alltaf tómur. En ef hlutlistarnir eru jafnstórir minnka þeir mjög hratt. Ef fjöldi staka í listanum er 1000 eru listarnir tveir með um það bil 500 stök hvor eftir fyrstu skiptingu. Þeim er síðan skipt upp í lista sem hver um sig er um 250 stök, og svo framvegis þar til aðeins standa eftir listar með einu eða engu staki. Á hverju lagi aðferðarinnar er aðeins verið að vinna með í mesta lagi 1000 stök. Fyrst er 1000 stökum skipt upp í tvo 500 staka lista, síðan þeim skipt upp í fjóra 250 staka lista, og svo framvegis. Því er mikilvægt að ekki þurfi að gera þetta mjög oft.

Ef listarnir skiptast alltaf í jafnstóra hluta er fjöldi skiptinga lágmarkaður. Miðað við 1000 stök í upphaflega listanum erum við komin með eins staks lista eftir um það bil 10 skiptingar. Þar sem heildarfjöldi aðgerða á hverju lagi Quicksort er um 1000 þá þýðir þetta að heildarfjöldi aðgerða við að raða 1000 staka lista er um 10.000.

Quicksort röðunaraðferðin er yfirleitt talin hraðvirkasta röðunaraðferðin og hún er það í langflestum tilfellum. Þó eru til kringumstæður þar sem aðrar röðunaraðferðir eru betri. Áður var minnst á að Quicksort er ekki best fyrir fá stök, en einnig má nefna tilfellið þegar inntakið er nálægt því að vera raðað (það er aðeins nokkur stök á röngum stöðum). Þá eru aðferðir eins og innsetningarröðun (á ensku "Insertion sort") hraðvirkari. Hið sama gildir ef inntakið er mjög stórt og kemst ekki fyrir í minni tölvunnar. Þá þarf að ná í einstök gildi af disk tölvunnar þar sem aðgangshraðinn er mun minni og því ekki hentugt að vera að hoppa mikið til og frá í gögnunum. Þar henta sérstakar útgáfur af samrunaröðun (á ensku "Merge sort"), sem ná í blokkir gagna af diskinum, raða þeim og sameina þær síðan öðrum röðuðum blokkum.

Nánari upplýsingar um röðunaraðferðir má finna í kennslubókum um gagnagrindur og reiknirit (flestar bækur sem hafa orðin "Data structures" og/eða "Algorithms" í titlinum).

Bók sem notuð er við kennslu í Háskóla Íslands um þetta efni er eftir Robert Sedgewick og heitir "Algorithms in C++: Third Edition, Parts 1-4".

Frekara lesefni af Vísindavefnum:

Höfundur

Hjálmtýr Hafsteinsson

Hjálmtýr Hafsteinsson

dósent í tölvunarfræði við HÍ

Útgáfudagur

19.12.2000

Spyrjandi

Jóhann Gunnarsson, fæddur 1982

Efnisorð

Tilvísun

Hjálmtýr Hafsteinsson. „Hvernig er stærðfræðileg skýring á Quicksort algoritmanum?“ Vísindavefurinn, 19. desember 2000. Sótt 19. apríl 2024. http://visindavefur.is/svar.php?id=1244.

Hjálmtýr Hafsteinsson. (2000, 19. desember). Hvernig er stærðfræðileg skýring á Quicksort algoritmanum? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=1244

Hjálmtýr Hafsteinsson. „Hvernig er stærðfræðileg skýring á Quicksort algoritmanum?“ Vísindavefurinn. 19. des. 2000. Vefsíða. 19. apr. 2024. <http://visindavefur.is/svar.php?id=1244>.

Chicago | APA | MLA

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki
Spyrja

Sendu inn spurningu LeiðbeiningarTil baka

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

Senda grein til vinar

=

Hvernig er stærðfræðileg skýring á Quicksort algoritmanum?
Spurningin í heild er sem hér segir:

Hvernig er stærðfræðileg skýring á Quicksort algoritmanum? Er til hraðari algoritmi til þess að raða gögnum og ef svo er, hvernig er hann?

Til eru ýmsar útgáfur af Quicksort röðunaraðferðinni, en grunnaðferðinni má lýsa þannig að byrjað er á að velja svokallað vendistak (á ensku "pivot"). Þetta gæti til dæmis verið stakið sem er í fyrsta sæti listans sem á að raða. Listanum er síðan skipt upp í tvo hluta, þannig að í annan hlutann fara þau stök sem eru minni en vendistakið en í hinn þau sem eru stærri. Þessum hlutlistum, sem hvor um sig er minni en upphaflegi listinn, er síðan raðað með Quicksort aðferðinni. Þegar þeim hefur verið raðað er einfaldlega hægt að skeyta þeim saman til að fá raðaða útgáfu af upphaflega listanum.

Þessi lýsing er ekki alveg augljós, enda er Quicksort ekki aðferð sem við myndum sjálf nota til að raða hlutum í höndunum. Til þess eru of mörg smáatriði sem þarf að halda utanum. Fólk á ekki gott með það, en tölvum hentar það mun betur.

Skoðum dæmi um hvernig Quicksort myndi raða 7 staka listanum: 75, 40, 8, 91, 46, 50, 87. Við byrjum á að velja vendistak. Það er alltaf valið á sama hátt, t.d. stakið í fyrsta sæti. Hér er það talan 75. Við skiptum listanum upp í tvennt, þar sem annar hlutinn hefur allar tölur sem eru minni en 75, en hinn allar sem eru stærri en 75. Fyrri listinn verður 40, 8, 46, 50 og sá seinni verður 91, 87. Athugið að við rennum í gegnum upphaflega listann og setjum stök annað hvort í fyrri eða seinni hlutlistann.

Nú höldum við áfram og röðum þessum tveimur listum sjálfstætt með Quicksort. Fyrri listinn er 40, 8, 46, 50. Við veljum aftur sem vendistak stakið sem er í fyrsta sætinu, en það er 40. Skiptum listanum upp í tvennt: 8 annars vegar og 46, 50 hins vegar. Nú eigum við að raða þessum tveimur listum með Quicksort. Eins staks listi er raðaður, svo að listinn 8 er raðaður. Það vill líka þannig til að hinn listinn er raðaður, en ef við vinnum blint samkvæmt Quicksort aðferðinni þá er 46 valið sem vendistak, annar listinn (sá með minni stökunum) er tómur, en hinn hefur aðeins eitt stak.

Þegar báðum hlutlistunum hefur verið raðað þá er þeim skeytt saman ásamt vendistakinu. Við fáum því listann 8, vendistakið 40 og listann 46, 50. Það gefur listann 8, 40, 46, 50. Þá er sá listi orðinn raðaður og við eigum aðeins eftir að raða seinni listanum í efsta laginu, sem var 91, 87. Þar er 91 valið sem vendistak, annar listinn verður bara 87, en hinn tómur. Við samskeytinguna fæst 87, 91. Því er hægt að skeyta saman á efsta laginu: annar listinn er 8, 40, 46, 50, vendistakið er 75, hinn listinn er 87, 91. Niðurstaðan verður því 8, 40, 46, 50, 75, 87, 91. Á myndinni sést þetta ferli betur.



Einnig sést nokkuð vel af þessu dæmi hversvegna ekki er fýsilegt að nota Quicksort til að raða hlutum í höndunum. Halda þarf utan um marga hlutlista sem eru mislangt komnir í röðunarferlinu. Erfitt er fyrir fólk að muna eftir öllum þessum hlutlistum og stöðu þeirra. Fyrir tölvur er þetta hins vegar ekkert mál.

Af dæminu að ráða virðist þessi aðferð ekki sérlega hraðvirk þar sem hún virðist krefjast mikillar vinnu kringum lista með mjög fáum stökum. Reyndar er Quicksort ekki besta röðunaraðferðin fyrir fá stök. Aðrar aðferðir eru oftast betri ef aðeins á að raða 2-5 stökum. Það sem gerir Quicksort hraðvirka er skipting stakanna um vendistakið. Jafnvel þótt vendistakið sé valið á mjög einfaldan hátt (til dæmis alltaf stakið í fyrsta sætinu) skiptir það oftast listanum í nokkurn veginn jafnstóra hluta. Athugið að þetta á ekki við þegar listinn er þegar raðaður, því að þá verður annar listinn alltaf tómur. En ef hlutlistarnir eru jafnstórir minnka þeir mjög hratt. Ef fjöldi staka í listanum er 1000 eru listarnir tveir með um það bil 500 stök hvor eftir fyrstu skiptingu. Þeim er síðan skipt upp í lista sem hver um sig er um 250 stök, og svo framvegis þar til aðeins standa eftir listar með einu eða engu staki. Á hverju lagi aðferðarinnar er aðeins verið að vinna með í mesta lagi 1000 stök. Fyrst er 1000 stökum skipt upp í tvo 500 staka lista, síðan þeim skipt upp í fjóra 250 staka lista, og svo framvegis. Því er mikilvægt að ekki þurfi að gera þetta mjög oft.

Ef listarnir skiptast alltaf í jafnstóra hluta er fjöldi skiptinga lágmarkaður. Miðað við 1000 stök í upphaflega listanum erum við komin með eins staks lista eftir um það bil 10 skiptingar. Þar sem heildarfjöldi aðgerða á hverju lagi Quicksort er um 1000 þá þýðir þetta að heildarfjöldi aðgerða við að raða 1000 staka lista er um 10.000.

Quicksort röðunaraðferðin er yfirleitt talin hraðvirkasta röðunaraðferðin og hún er það í langflestum tilfellum. Þó eru til kringumstæður þar sem aðrar röðunaraðferðir eru betri. Áður var minnst á að Quicksort er ekki best fyrir fá stök, en einnig má nefna tilfellið þegar inntakið er nálægt því að vera raðað (það er aðeins nokkur stök á röngum stöðum). Þá eru aðferðir eins og innsetningarröðun (á ensku "Insertion sort") hraðvirkari. Hið sama gildir ef inntakið er mjög stórt og kemst ekki fyrir í minni tölvunnar. Þá þarf að ná í einstök gildi af disk tölvunnar þar sem aðgangshraðinn er mun minni og því ekki hentugt að vera að hoppa mikið til og frá í gögnunum. Þar henta sérstakar útgáfur af samrunaröðun (á ensku "Merge sort"), sem ná í blokkir gagna af diskinum, raða þeim og sameina þær síðan öðrum röðuðum blokkum.

Nánari upplýsingar um röðunaraðferðir má finna í kennslubókum um gagnagrindur og reiknirit (flestar bækur sem hafa orðin "Data structures" og/eða "Algorithms" í titlinum).

Bók sem notuð er við kennslu í Háskóla Íslands um þetta efni er eftir Robert Sedgewick og heitir "Algorithms in C++: Third Edition, Parts 1-4".

Frekara lesefni af Vísindavefnum:...