En annen betydelig forskjell mellom de to er at boble sorteringen er stabil algoritme mens utvalgssort er en ustabil algoritme. En algoritme anses å være stabil elementene med samme nøkkel forekommer i samme rekkefølge som de skjedde før sortering i listen eller arrayen. Generelt bruker de fleste stabile og raske algoritmer ekstra minne.
Sammenligningstabel
Grunnlag for sammenligning | Bubblesort | Valg sortering |
---|---|---|
grunn~~POS=TRUNC | Tilgrensende element sammenlignes og byttes | Største element er valgt og byttet med det siste elementet (i tilfelle stigende rekkefølge). |
Beste tilfelle tid kompleksitet | På) | O (n 2 ) |
Effektivitet | Ineffektiv | Forbedret effektivitet sammenlignet med boble sorter |
Stabil | Ja | Nei |
Metode | utveksle | utvalg |
Hastighet | Langsom | Raskt i forhold til boble sortering |
Definisjon av Bubblesort
Boble sortering er den enkleste iterative algoritmen fungerer ved å sammenligne hvert element eller element med elementet ved siden av det og bytte dem om nødvendig. I enkle ord sammenligner det det første og andre elementet i listen og bytter det med mindre de ikke er i spesifikk rekkefølge. Tilsvarende sammenlignes og byttes andre og tredje element, og denne sammenligningen og bytte fortsetter til slutten av listen. Antall sammenligninger i den første iterasjonen er n-1 hvor n er tallelementene i en matrise. Det største elementet vil være på nte posisjon etter den første iterasjonen. Og etter hver iterasjon reduseres antall sammenligninger, og til slutt er det bare en sammenligning som foregår.
Denne algoritmen er den langsomste sorteringsalgoritmen. Den beste saken kompleksiteten (når listen er i orden) av typen Bubble er av rekkefølge n ( O (n) ), og verste fall kompleksiteten er O (n2) . I beste fall er det av orden n fordi det bare sammenligner elementene og bytter ikke dem. Denne teknikken krever også ekstra plass til å lagre den midlertidige variabelen.
Definisjon av utvalgssortering
Valg sort har oppnådd litt bedre ytelse og er effektiv enn boble sorteringsalgoritme. Anta at vi vil arrangere en rekkefølge i stigende rekkefølge, da fungerer den ved å finne det største elementet og utveksle det med det siste elementet, og gjenta følgende prosess på underarrayene til hele listen er sortert.
Viktige forskjeller mellom sortering av bobler og utvalg
- I sorten bobles hvert element og dets tilstøtende element sammen og byttes om nødvendig. På den annen side fungerer sorterings sortering ved å velge elementet og bytte det aktuelle elementet med det siste elementet. Det valgte elementet kan være størst eller minste, avhengig av rekkefølgen, dvs. stigende eller synkende.
- Den verste kompleksiteten er den samme i begge algoritmer, dvs. O (n2), men beste kompleksitet er forskjellig. Bubblesort tar en ordre av n tid mens utvalg sorterer bruker en ordre av n2 tid.
- Boble sortering er en stabil algoritme, i motsetning er utvalgssort ustabil.
- Valg sorteringsalgoritme er rask og effektiv sammenlignet med boble sortering som er veldig treg og ineffektiv.
Konklusjon
Boble sorteringsalgoritmen regnes for å være den mest enkle og ineffektive algoritmen, men utvalgssortalgoritmen er effektiv i forhold til boble sortering. Bubble sort bruker også ekstra plass til lagring av midlertidig variabel og trenger flere swaps.