Innhold

• Sammenligningstabell
• Definisjon av Bubble Sort
• Definisjon av utvalgssortering
• Konklusjon

Sortering er en av hovedoppgavene i dataprogrammer der elementene i en matrise er ordnet i en bestemt rekkefølge. Sortering gjør søk lettere. Boblesortering og utvalgssortering er sorteringsalgoritmene som kan differensieres gjennom metodene de bruker for sortering. Boble-sortering utveksler i det vesentlige elementene, mens utvalgssortering utfører sorteringen ved å velge elementet.

En annen betydelig forskjell mellom de to er at boblesortering er stabil algoritme mens valgsortering er en ustabil algoritme. En algoritme anses for å være stødig elementene med samme nøkkel som forekommer i samme rekkefølge som de skjedde før sortering i listen eller arrayen. Vanligvis bruker de fleste stabile og raske algoritmer ekstra minne.

1. Sammenligningstabell
2. Definisjon
3. Viktige forskjeller
4. Konklusjon

Sammenligningstabell

Grunnlag for sammenligning	Boble sortering	Utvalgssortering
grunn~~POS=TRUNC	Tilstøtende element blir sammenlignet og byttet	Største element er valgt og byttet med det siste elementet (i tilfelle stigende rekkefølge).
Beste sakstidskompleksitet	På)	På2)
Effektivitet	Ineffektiv	Forbedret effektivitet sammenlignet med boble sortering
Stabil	Ja	Nei
Metode	utveksle	utvalg
Hastighet	Sakte	Rask sammenlignet med boble sortering

Definisjon av Bubble Sort

Boble sorter er den enkleste iterative algoritmen som fungerer ved å sammenligne hvert element eller element med elementet ved siden av og bytte dem om nødvendig. Med enkle ord sammenligner den det første og andre elementet i listen og bytter den med mindre de er utenfor spesifikk rekkefølge. Tilsvarende blir andre og tredje element sammenlignet og byttet, og dette sammenligning og bytte går videre til slutten av listen. Antall sammenligninger i den første iterasjonen er n-1 der n er tallelementene i en matrise. Det største elementet vil være i n.posisjon etter den første iterasjonen. Og etter hver iterasjon reduseres antall sammenligninger, og til slutt finner bare en sammenligning sted.

Denne algoritmen er den tregeste sorteringsalgoritmen. Den beste sakskompleksiteten (når listen er i orden) av typen Bubble er av orden n (På)), og i verste fall er kompleksiteten På²). I beste fall er det av orden n fordi det bare sammenligner elementene og ikke bytter dem. Denne teknikken krever også ekstra plass for å lagre den midlertidige variabelen.

Definisjon av utvalgssortering

Utvalgssortering har oppnådd litt bedre ytelse og er effektiv enn algoritme for boble sortering. Anta at vi ønsker å arrangere en matrise i stigende rekkefølge, så fungerer den ved å finne det største elementet og bytte det med det siste elementet, og gjenta følgende prosess på delarrayene til hele listen er sortert.

Når det gjelder utvalg, gjør ikke den sorterte og usorterte matrisen ingen forskjell og forbruker en rekkefølge på n² (På²)) i både beste og verste tilfelle kompleksitet. Valgssortering er raskere enn Bubble-sortering.

1. I boble-sorteringen blir hvert element og det tilstøtende elementet sammenlignet og byttet om nødvendig. På den annen side fungerer utvalgssortering ved å velge elementet og bytte det bestemte elementet med det siste elementet. Det valgte elementet kan være størst eller minste avhengig av rekkefølgen, dvs. stigende eller synkende.
2. I verste fall er kompleksiteten den samme i begge algoritmene, dvs. O (n²), men beste kompleksitet er annerledes. Boble sortering tar en rekkefølge på n tid mens utvalgssortering bruker en rekkefølge på n² tid.
3. Boblesortering er en stabil algoritme, derimot er valgsortering ustabil.
4. Valgssorteringsalgoritme er rask og effektiv sammenlignet med boble sortering som er veldig treg og ineffektiv.

Konklusjon

Boble sorteringsalgoritme anses å være den mest enkle og ineffektive algoritmen, men utvalgssorteringsalgoritmen er effektiv sammenlignet med boble sortering. Boble sortering bruker også ekstra plass for lagring av midlertidig variabel og trenger flere bytter.