Forskel mellem boble sortering og markering
Indhold
Sortering er en af de vigtigste opgaver i computerprogrammer, hvor elementerne i en matrix er arrangeret i en bestemt rækkefølge. Sortering gør søgningen lettere. Bobelsortering og udvælgelsessortering er de sorteringsalgoritmer, der kan differentieres gennem de metoder, de bruger til sortering. Boblesorter udveksler i det væsentlige elementerne, mens valgssortering udfører sorteringen ved at vælge elementet.
En anden betydelig forskel mellem de to er, at bobelsortering er en stabil algoritme, mens udvælgelsessortering er en ustabil algoritme. En algoritme anses for at være stabil elementerne med den samme nøgle, der forekommer i samme rækkefølge, som de opstod inden sortering i listen eller array. Generelt bruger de fleste stabile og hurtige algoritmer ekstra hukommelse.
- Sammenligningstabel
- Definition
- Vigtige forskelle
- Konklusion
Sammenligningstabel
| Grundlag for sammenligning | Boble sortering | Valgsortering |
|---|---|---|
| Grundlæggende | Det tilstødende element sammenlignes og byttes | Største element vælges og byttes med det sidste element (i tilfælde af stigende rækkefølge). |
| Bedste sagstidskompleksitet | På) | På2) |
| Effektivitet | ineffektiv | Forbedret effektivitet sammenlignet med boble sortering |
| stabil | Ja | Ingen |
| Metode | udveksling | Udvælgelse |
| Hastighed | Langsom | Hurtigt sammenlignet med boble sortering |
Definition af Bubble Sort
Boble sortering er den enkleste iterative algoritme, der fungerer ved at sammenligne hvert element eller element med elementet ved siden af det og bytte dem om nødvendigt. Med enkle ord sammenligner den det første og andet element på listen og bytter den, medmindre de er ude af specifik rækkefølge. Tilsvarende sammenlignes og udskiftes andet og tredje element, og denne sammenligning og bytte fortsætter til slutningen af listen. Antallet af sammenligninger i den første iteration er n-1, hvor n er talelementerne i en matrix. Det største element ville være på nth position efter den første iteration. Og efter hver iteration falder antallet af sammenligninger, og til sidst finder kun en sammenligning sted.
Denne algoritme er den langsomste sorteringsalgoritme. Den bedste sagskompleksitet (Når listen er i rækkefølge) af typen Bubble er af orden n (På)), og i værste fald er kompleksiteten På2). I det bedste tilfælde er det af orden n, fordi det bare sammenligner elementerne og ikke bytter dem. Denne teknik kræver også yderligere plads til at gemme den midlertidige variabel.
Definition af markering
Valgsortering har opnået lidt bedre ydelse og er effektiv end algoritme til boble-sortering. Lad os antage, at vi vil arrangere en matrix i stigende rækkefølge, så fungerer den ved at finde det største element og udveksle det med det sidste element, og gentage følgende proces i undermarraysne, indtil hele listen er sorteret.
- I boblesorteringen sammenlignes og byttes hvert element og dets tilstødende element om nødvendigt. På den anden side fungerer valgssortering ved at vælge elementet og bytte det bestemte element med det sidste element. Det valgte element kan være størst eller mindre afhængigt af rækkefølgen, dvs. stigende eller faldende.
- Kompleksiteten i værste tilfælde er den samme i begge algoritmer, dvs. O (n2), men bedste kompleksitet er anderledes. Boblesortering tager en rækkefølge af n tid, mens valgssortering bruger en rækkefølge på n2 tid.
- Boblesortering er en stabil algoritme, i modsætning hertil er valgssortering ustabil.
- Valgsorteringsalgoritme er hurtig og effektiv sammenlignet med boblesortering, der er meget langsom og ineffektiv.
Konklusion
Bubblesorteringsalgoritme anses for at være den mest enkle og ineffektive algoritme, men valgssorteringsalgoritmen er effektiv sammenlignet med boble sortering. Boblesorter bruger også ekstra plads til opbevaring af midlertidig variabel og har brug for flere swaps.
