Anbefalet, 2021

Redaktørens Valg

Forskel mellem sortering og sortering af bobler

Sortering er en af ​​de vigtigste opgaver i computerprogrammer, hvor elementerne i et array er arrangeret i en bestemt rækkefølge. Sortering gør søgning lettere. Sortering og valg af bobler er sorteringsalgoritmerne, som kan differentieres gennem de metoder, de bruger til sortering. Boble sortering udveksler hovedsagelig elementerne, mens sorterings sortering udfører sorteringen ved at vælge elementet.

En anden betydelig forskel mellem de to er, at boble sorter er stabil algoritme, mens valg sorter er en ustabil algoritme. En algoritme anses for at være stabil, elementerne med den samme nøgle forekommer i samme rækkefølge som de forekom før sortering i listen eller arrayet. Generelt bruger de fleste stabile og hurtige algoritmer ekstra hukommelse.

Sammenligningstabel

Grundlag for sammenligningBubble sort
Valg sort
GrundlæggendeTilgrænsende element sammenlignes og bytesStørste element er valgt og byttet med det sidste element (i tilfælde af stigende rækkefølge).
Bedste tilfælde tid kompleksitetPå)O (n2)
EffektivitetineffektivForbedret effektivitet i forhold til boble sorter
stabilJaIngen
MetodeudvekslingUdvælgelse
HastighedLangsomHurtig i forhold til boble sorter

Definition af boblesort

Bubble sortering er den enkleste iterative algoritme fungerer ved at sammenligne hvert element eller element med elementet ved siden af ​​det og bytte dem om nødvendigt. I enkle ord sammenligner det det første og det andet element i listen og bytter det, medmindre de er ude af en bestemt 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 i sidste ende er det kun en sammenligning, der finder sted.

Denne algoritme er den langsomste sorteringsalgoritme. Den bedste tilfælde kompleksitet (når listen er i orden) af typen Bubble er af rækkefølge n ( O (n) ), og værste tilfælde er kompleksiteten O (n2) . I bedste fald er det af rækkefølge n fordi det kun sammenligner elementerne og ikke bytter dem. Denne teknik kræver også ekstra plads til at gemme den midlertidige variabel.

Definition af valg sortering

Valg sort har opnået en smule bedre ydeevne og er effektiv end boble sort algoritme. Antag, at vi vil arrangere en array i stigende rækkefølge, så fungerer den ved at finde det største element og udveksle det med det sidste element, og gentag følgende proces på underarrayerne, indtil hele listen er sorteret.

I sorterings sortering gør det sorterede og usorterede array ingen forskel og bruger en ordre af n2 ( O (n2) ) i både bedste og værste tilfælde kompleksitet. Valg sortering er hurtigere end Bubble sortering.

Nøgleforskelle mellem sortering af bobler og valg af sortering

  1. I sorten bobles hvert element og dets tilstødende element sammen og byttes om nødvendigt. På den anden side virker sorterings sorter ved at vælge elementet og bytte det pågældende element med det sidste element. Det valgte element kan være størst eller mindste afhængigt af ordren, dvs. stigende eller faldende.
  2. Det værste tilfælde kompleksitet er det samme i både algoritmerne, dvs. O (n2), men den bedste kompleksitet er anderledes. Bubblesort tager en ordre af n tid, mens sortering sorterer bruger en ordre af n2 tid.
  3. Bubblesort er en stabil algoritme, derimod er sorterings sort ustabil.
  4. Valg sort algoritme er hurtig og effektiv i forhold til boble sorter, som er meget langsom og ineffektiv.

Konklusion

Bubble sorteringsalgoritmen anses for at være den mest enkle og ineffektive algoritme, men valg sorteringsalgoritmen er effektiv i forhold til boble sorter. Bubble sort bruger også ekstra plads til opbevaring af midlertidig variabel og har brug for flere swaps.

Top