Soovitatav, 2022

Toimetaja Valik

Erinevus mullide sorteerimise ja valimise vahel Sorteeri

Sorteerimine on üks peamisi ülesandeid arvutiprogrammides, kus massiivi elemendid on paigutatud teatud järjekorras. Sorteerimine muudab otsingu lihtsamaks. Bubble sort ja Selection sort on sorteerimisalgoritmid, mida saab diferentseerida sorteerimiseks kasutatavate meetodite abil. Bubble sort vahetab põhiliselt elemente, samas kui valiku sortimine sorteerib elemendi valimise teel.

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 alusBubble sort
Valiku sorteerimine
PõhilineKülgnevat elementi võrreldakse ja vahetatakseSuurim element valitakse ja vahetatakse viimase elemendiga (kasvavas järjekorras).
Parim juhtumikompleksi keerukusO (n)O (n 2 )
TõhususEbatõhusParem tõhusus võrreldes mullide sortimisega
StabiilneJahEi
MeetodVahetusValik
KiirusAeglaneKiire 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.

Valiku sorteerimise korral ei ole sorteeritud ja sortimata massiiv mingit vahet ja tarbib n2 ( O (n2) ) järjekorras nii parimal kui ka halvimal juhul. Valiku sorteerimine on kiirem kui Bubble sort.

Peamised erinevused mullide sorteerimise ja valimise vahel

  1. 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.
  2. 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.
  3. Bubble sort on stabiilne algoritm, seevastu valiku sort on ebastabiilne.
  4. 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.

Top