Sortieren eines Arrays in C?

Question 1

Welches ist die beste Sortiertechnik, um das folgende Array zu sortieren, und wenn es Duplikate gibt, wie man damit umgeht:

int a= {1,3,6,7,1,2};

Und welches ist die beste Sortiertechnik von allen?

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;
            }
        }
    }
}

Question 2

In C können Sie das eingebaute verwenden qsort Befehl:

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 )

sehen: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

Um den zweiten Teil Ihrer Frage zu beantworten: Ein optimaler (vergleichsbasierter) Sortieralgorithmus ist einer, der mit O (n log (n)) Vergleichen ausgeführt wird. Es gibt mehrere, die diese Eigenschaft haben (einschließlich Schnellsortierung, Zusammenführungssortierung, Heap-Sortierung usw.), aber welche Sie verwenden sollten, hängt von Ihrem Anwendungsfall ab.

Als Randnotiz können Sie es manchmal besser machen als O(n log(n)), wenn Sie etwas über Ihre Daten wissen – siehe Wikipedia-Artikel auf Radix-Sortierung

Question 3

In Ihrem speziellen Fall ist die schnellste Sortierung wahrscheinlich die in dieser Antwort beschriebene. Es ist genau auf ein Array von 6 Ints optimiert und verwendet Sortiernetzwerke. es ist 20 mal (gemessen auf x86) schneller als Bibliothek qsort. Sortiernetzwerke sind optimal für Arrays mit fester Länge. Da es sich um eine feste Abfolge von Anweisungen handelt, können sie sogar einfach durch Hardware implementiert werden.

Im Allgemeinen gibt es viele Sortieralgorithmen, die für einen speziellen Fall optimiert sind. Die Allzweckalgorithmen wie Heap Sort oder Quick Sort sind für das Sortieren einer Reihe von Elementen an Ort und Stelle optimiert. Sie ergeben eine Komplexität von O(n.log(n)), wobei n die Anzahl der zu sortierenden Elemente ist.

Die Bibliotheksfunktion qsort() ist sehr gut codiert und effizient in Bezug auf die Komplexität, verwendet jedoch einen Aufruf einer vom Benutzer bereitgestellten Vergleichsfunktion, und dieser Aufruf hat ziemlich hohe Kosten.

Zum Sortieren sehr großer Datenmengen müssen sich Algorithmen auch um das Austauschen von Daten auf und von der Festplatte kümmern. Dies ist die Art der Sortierung, die in Datenbanken implementiert ist, und wenn Sie solche Anforderungen haben, ist es am besten, Daten in eine Datenbank zu stellen und zu verwenden Art eingebaut.

Question 4

Beruht

Es hängt von verschiedenen Dingen ab. Aber im Allgemeinen Algorithmen mit a Teile und herrsche / dichotomisch Der Ansatz eignet sich gut für Sortierprobleme, da er interessante Komplexitäten für durchschnittliche Fälle aufweist.

Grundlagen

Um zu verstehen, welche Algorithmen am besten funktionieren, benötigen Sie Grundkenntnisse Komplexität der Algorithmen und Big-O-Notationdamit Sie verstehen können, wie sie in Bezug auf bewertet werden Durchschnittsszenarien, Best-Case- und Worst-Case-Szenarien. Darauf müssten Sie ggf. auch achten Stabilität des Sortieralgorithmus.

Ein effizienter Algorithmus ist zum Beispiel Quicksort. Wenn Sie Quicksort jedoch eine perfekt invertierte Liste geben, wird es schlecht funktionieren (eine einfache Auswahlsortierung wird in diesem Fall besser funktionieren!). Shell-Sort wäre normalerweise auch eine gute Ergänzung zu Quicksort, wenn Sie eine Voranalyse Ihrer Liste durchführen.

Sehen Sie sich das Folgende für “erweiterte Suchen” mit Teilen-und-Herrschen-Ansätzen an:

Zusammenführen, sortieren

Und diese einfacheren Algorithmen für weniger komplexe:

Blasensortierung

Des Weiteren

Die oben genannten sind die üblichen Verdächtigen, wenn Sie anfangen, aber es gibt unzählige andere.

Wie von R. in den Kommentaren und von Kriss in seiner Antwort darauf hingewiesen, möchten Sie vielleicht einen Blick darauf werfen HeapSort, das theoretisch eine bessere Sortierkomplexität bietet als ein Quicksort (aber in der Praxis nicht oft besser abschneidet). Es gibt auch Varianten u hybride Algorithmen (z.B TimSort).

Question 5

Ich möchte einige Änderungen vornehmen: In C können Sie die eingebaute verwenden qsort Befehl:

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 )

Question 6

Die allerbeste Sortiertechnik hängt im Allgemeinen von der Größe eines Arrays ab. Merge Sort kann das Beste von allen sein, da es gemäß dem Big-O-Algorithmus eine bessere Raum- und Zeitkomplexität verwaltet (dies eignet sich besser für ein großes Array).