Teine märkimisväärne erinevus nende kahe vahel on see, et mulli sortimine on stabiilne algoritm, samal ajal kui valiku sortimine on ebastabiilne algoritm. Algoritm loetakse samaks võtmeks olevate elementide suhtes püsivaks, mis esinevad samas järjekorras kui need olid enne loendis või massiivis sorteerimist. Üldiselt kasutavad kõige stabiilsemad ja kiiremad algoritmid lisamälu.
Võrdluskaart
| Võrdluse alus | Bubble sort | Valiku sorteerimine |
|---|---|---|
| Põhiline | Külgnevat elementi võrreldakse ja vahetatakse | Suurim element valitakse ja vahetatakse viimase elemendiga (kasvavas järjekorras). |
| Parim juhtumikompleksi keerukus | O (n) | O (n 2 ) |
| Tõhusus | Ebatõhus | Parem tõhusus võrreldes mullide sortimisega |
| Stabiilne | Jah | Ei |
| Meetod | Vahetus | Valik |
| Kiirus | Aeglane | Kiire võrreldes mullide sortimisega |
Mullide sorteerimise mõiste
Bubble sort on lihtsaim iteratiivne algoritm, mis võrdleb iga üksust või elementi selle kõrval asuva elemendiga ja vajadusel vahetades neid. Lihtsamalt öeldes võrdleb see loendi esimest ja teist elementi ning vahetab selle, kui need ei ole konkreetses järjekorras. Samamoodi võrreldakse ja vahetatakse teist ja kolmandat elementi ning see võrdlemine ja vahetamine jätkub loendi lõppu. Võrdluste arv esimeses iteratsioonis on n-1, kus n on massiivi elemendid. Suurim element oleks pärast esimest iteratsiooni n. Ja pärast iga iteratsiooni väheneb võrdluste arv ja viimasel iteratsioonil toimub ainult üks võrdlus.
See algoritm on kõige aeglasem sorteerimisalgoritm. Bubble'i sorti parim juhtumite keerukus (kui järjestus on järjekorras) on järjekorras n ( O (n) ) ja halvimal juhul keerukus on O (n2) . Parimal juhul on see järjekorras n, sest see võrdleb elemente ja ei muuda neid. See meetod nõuab ajutise muutuja salvestamiseks lisaruumi.
Valiku määratlus Sorteeri
Valiku sort on saavutanud veidi parema tulemuse ja on efektiivsem kui mullide sorteerimise algoritm. Oletame, et me tahame järjestada massiivi kasvavas järjekorras, siis toimib see leides suurima elemendi ja vahetades selle viimase elemendiga ning korrates alljärgnevat protsessi alammaatriksides, kuni kogu nimekiri on sorteeritud.
Peamised erinevused mullide sorteerimise ja valimise vahel
- Mullide sorteerimisel võrreldakse iga elementi ja sellega külgnevat elementi ja vahetatakse vajaduse korral. Teisest küljest, valiku sorteerimine toimib, valides elemendi ja vahetades selle konkreetse elemendi viimase elemendiga. Valitud element võib olla suurim või väikseim sõltuvalt tellimusest, st kasvavalt või kahanevalt.
- Halvimal juhul on mõlema algoritmi puhul sama, st O (n2), kuid parim keerukus on erinev. Mullide sortimine võtab aega n korda, samas kui valiku sortimine tarbib n2 korda.
- Bubble sort on stabiilne algoritm, seevastu valiku sort on ebastabiilne.
- Valiku sorteerimise algoritm on kiire ja tõhus võrreldes väga aeglase ja ebatõhusa mullide sortimisega.
Järeldus
Bubble sort algoritmi peetakse kõige lihtsamaks ja ebaefektiivsemaks algoritmiks, kuid valiku sortimise algoritm on mulli sortimisega võrreldes tõhus. Bubble sort kasutab ka täiendavat ruumi ajutise muutuja salvestamiseks ja vajab rohkem vahetustehinguid.
