sorteringsalgoritm jämförelse

sorteringsalgoritmer är en viktig del av hanteringen av data. AtCprogramming.com, vi erbjuder handledning för att förstå de viktigaste ochvanliga tekniker. Varje algoritm har särskilda styrkor ochsvagheter och i många fall är det bästa att bara använda den inbyggda insorteringsfunktionen qsort. För tider när detta inte är ett alternativ eller du bara behöveren snabb och smutsig sorteringsalgoritm finns det en mängd olika val.

de flesta sorteringsalgoritmer fungerar genom att jämföra data som sorteras. I vissa fall kan det vara önskvärt att sortera en stor del av data (till exempel astruct som innehåller ett namn och en adress) baserat på endast en del av den data.Den del av data som faktiskt används för att bestämma den sorterade ordningen kallas nyckeln.
sorteringsalgoritmer bedöms vanligtvis av deras effektivitet. I detta fall avser effektivitet den algoritmiska effektiviteten eftersom storleken på ingången växer stor och baseras i allmänhet på antalet element som ska sorteras. De flesta av dealgoritmer som används har en algoritmisk effektivitet av antingen O(n^2) orO(n*log(n)). Några speciella fallalgoritmer(ett exempel nämns i Programmeringspärlor) kan sortera vissa datamängder snabbare än O(n*log (n)). Denaalgoritmer är inte baserade på att jämföra de objekt som sorteras och lita påtricks. Det har visats att ingen nyckeljämförelsealgoritm kan prestera bättreän O(n * log (n)).
många algoritmer som har samma effektivitet har inte samma hastighet påsamma ingång. Först måste algoritmer bedömas utifrån deras genomsnittliga fall, bästa fall och värsta fall effektivitet. Vissa algoritmer,som snabb sortering, fungerar exceptionellt bra för vissa ingångar, men hemskt för andra. Otheralgoritmer, såsom sammanslagningssortering, påverkas inte av ordningen för inmatningsdata.Även en modifierad version av bubble sort kan sluta i O (n) för de flestagynnsamma ingångar.
en andra faktor är ”konstant term”. Som big-O notation abstraherar bort manyof detaljerna i en process, det är ganska bra för att titta på bigpicture. Men en sak som släpps ut är konstanten framföruttrycket: till exempel är O(c*n) bara O(n). I den verkliga världen, theconstant, c, kommer att variera mellan olika algoritmer. En väl implementeradquicksort bör ha en mycket mindre konstant multiplikator än heap sort.
ett andra kriterium för att bedöma algoritmer är deras rymdbehov-behöver de skraputrymme eller kan matrisen sorteras på plats (utanytterligare minne utöver några variabler)? Vissa algoritmer kräver aldrigextra utrymme, medan vissa är lättast att förstå när de implementeras medextra utrymme (heap sort, till exempel, kan göras på plats, men konceptuelltdet är mycket lättare att tänka på en separat heap). Utrymmeskrav kan till och med bero på den datastruktur som används (sammanfoga Sortera på arrayer kontra sammanfoga Sortera länkade listor, till exempel).
ett tredje kriterium är stabilitet – bevarar sorten ordningen på tangenter med lika värden? De flesta enkla sorter gör just detta, men vissa sorter, till exempelbillig sort, gör det inte.
följande diagram jämför sorteringsalgoritmer på de olika kriterierna skisseras ovan; algoritmerna med högre konstanta termer visas först, men detta är helt klart ett implementeringsberoende koncept och bör endast tas som en grov guide när man väljer mellan olika typer av samma big-O-effektivitet.

td>

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	konstant	stabil	även en perfekt sorterad ingång kräver skanning av hela matrisen
insättningssortering	O(n^2)	O(n)	O(n^2)	konstant	stabil	i bästa fall (redan sorterad) kräver varje insats konstant tid
heap sortering	o(n*log(n))	o(n*log(n))	o(n*log(n))	konstant	instable	genom att använda input array som lagring för högen är det möjligt att uppnå konstant Utrymme
sammanfoga Sortera	o(n*log(n))	O(n*log(n))	O(n*log(n))	beror	stabil	på arrayer kräver merge sort o(n) utrymme; på länkade listor kräver merge sort konstant utrymme
Quicksort	o(n*log(n))	o(n*log(n))	o(n^2)	konstant	stabil	slumpmässigt att välja ett pivotvärde (eller blanda matrisen före sortering) kan hjälpa till att undvika värsta scenarier som en perfekt sorterad array.