Wat is de beste sorteertechniek om de volgende array te sorteren en als er duplicaten zijn, hoe hiermee om te gaan:
int a= {1,3,6,7,1,2};
En wat is de beste sorteertechniek van allemaal?
void BubbleSort(int a[], int array_size)
{
int i, j, temp;
for (i = 0; i < (array_size - 1); ++i)
{
for (j = 0; j < array_size - 1 - i; ++j )
{
if (a[j] > a[j+1])
{
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
Antwoord 1, autoriteit 100%
In C kunt u de ingebouwde opdracht qsortgebruiken:
int compare( const void* a, const void* b)
{
int int_a = * ( (int*) a );
int int_b = * ( (int*) b );
if ( int_a == int_b ) return 0;
else if ( int_a < int_b ) return -1;
else return 1;
}
qsort( a, 6, sizeof(int), compare )
zie: http://www.cplusplus.com/reference/clibrary/cstdlib /qsort/
Om het tweede deel van uw vraag te beantwoorden: een optimaal (op vergelijking gebaseerd) sorteeralgoritme is er een dat werkt met O(n log(n))-vergelijkingen. Er zijn er meerdere die deze eigenschap hebben (inclusief snel sorteren, samenvoegen sorteren, heap sorteren, enz.), maar welke u moet gebruiken, hangt af van uw gebruik.
Als een kanttekening, je kunt het soms beter doen dan O(n log(n)) als je iets weet over je gegevens – zie het wikipedia-artikel op Radix Sorteren
Antwoord 2, Autoriteit 22%
In uw specifieke geval is de snelste soort waarschijnlijk de beschreven in dit antwoord . Het is precies geoptimaliseerd voor een array van 6 inten en gebruikt sorteernetwerken. Het is 20 keer (gemeten op x86) sneller dan bibliotheek QSort. Sorteernetwerken zijn optimaal voor een soort van reeksen van vaste lengte. Omdat ze een vast sequentie van instructies zijn, kunnen ze zelfs gemakkelijk door hardware worden geïmplementeerd.
Over het algemeen is er veel sorteeralgoritmen geoptimaliseerd voor een gespecialiseerde zaak. De algoritmen van het algemene doeleinden zoals heap Sort of Quick Sorteren zijn geoptimaliseerd voor het sorteren van een reeks items. Ze leveren een complexiteit van O (N.LOG (N)), N zijn het aantal items om te sorteren.
De bibliotheekfunctie QSort () is zeer goed gecodeerd en efficiënt in termen van complexiteit, maar gebruikt een oproep aan een vergelijkbare functie die door de gebruiker wordt verstrekt en deze oproep heeft een vrij hoge kosten.
Voor het sorteren van zeer grote hoeveelheid datasalgoritmen moet ook zorgen voor het zorgen voor het wisselen van gegevens van en naar schijf, dit is het soort soorten geïmplementeerd in databases en uw beste gok als u dergelijke behoeften hebt, is om data’s in een database te plaatsen en gebruik de ingebouwde soort.
Antwoord 3, Autoriteit 11%
hangt af van
Het hangt af van verschillende dingen. Maar in het algemeen algoritmen met behulp van een verdeling-en-overwinning / Dichotomische benadering zal goed presteren voor sorteerproblemen terwijl ze interessante gemiddelde-casecomplexiteiten presenteren.
Basisprincipes
Om te begrijpen welke algoritmen het beste werken, hebt u basiskennis nodig van algoritmen complexiteit en BIG-O NOTATIE , zodat u begrijpt hoe ze beoordelen in termen van Gemiddelde case, beste case-case-scenario’s . Indien nodig moet u ook aandacht besteden aan de sorteren van de stabiliteit van het algoritme .
Bijvoorbeeld, meestal is een efficiënt algoritme Quicksort. Als u echter Quicksort een perfect geïnverteerde lijst geeft, dan zal het slecht presteren (een eenvoudige selectie sorteert u in dat geval beter!). Shell-sorteer zou meestal meestal een goede aanvulling zijn op Quicksort als u een pre-analyse van uw lijst uitvoert.
Bekijk het volgende, voor “geavanceerde zoekopdrachten” met behulp van Divide and Conquer-benaderingen:
En deze meer straighForward-algoritmen voor minder complexe:
Verder
Het bovenstaande zijn de gebruikelijke verdachten bij de slag, maar er zijn talloze anderen.
Zoals aangegeven door R. in de opmerkingen en door kriss in zijn antwoord, wil je misschien een kijkje nemen op HeapSort, wat een theoretisch betere sorteercomplexiteit biedt dan een quicksort (maar in praktische situaties niet vaak beter zal presteren). Er zijn ook varianten en hybride algoritmen(bijv. TimSort).
Antwoord 4, autoriteit 9%
Ik wil graag enkele wijzigingen aanbrengen:
In C kunt u het ingebouwde commando qsortgebruiken:
int compare( const void* a, const void* b)
{
int int_a = * ( (int*) a );
int int_b = * ( (int*) b );
// an easy expression for comparing
return (int_a > int_b) - (int_a < int_b);
}
qsort( a, 6, sizeof(int), compare )
Antwoord 5, autoriteit 6%
De beste sorteertechniek hangt in het algemeen af van de grootte van een array. Samenvoegen sorteren kan het beste van alles zijn, omdat het een betere ruimte- en tijdcomplexiteit beheert volgens het Big-O-algoritme (dit past beter bij een grote array).