cs50 pset3 Sortierfunktion

Question

Ich habe Probleme mit der Implementierung der Sortierfunktion auf pset3. Ich habe die GDB benutzt und festgestellt, dass meine Sortierfunktion nichts sortiert. Ich bin nicht sicher, ob es ein Syntaxproblem gibt, oder ob die Logik ein bisschen vermasselt ist.

void sort(int values[], int n) 
{ 
    for (int k = 0; k < n; k++) 
    { 
     for (int j = 0; j < n; j++) 
     { 
      if (values[k] >= values[j]) 
      { 
       int temp = values[k]; 
       values[k] = values[j]; 
       values[j] = temp; 
      } 
     } 
    } 
} 

Answer 1

Sie sind in der Nähe, aber Ihre Loops sind nicht ganz richtig - Änderung:

for (int k = 0; k < n; k++) 
{ 
    for (int j = 0; j < n; j++) 
    { 

zu:

for (int k = 0; k < n - 1; k++) 
{ 
    for (int j = k + 1; j < n; j++) 
    { 

Um zu verstehen, warum Sie diese Änderung vornehmen müssen, der Ansicht, dass die innere Schleife (j) müssen nur Elemente über Index k mit dem aktuellen Element bei Indexvergleichen 0. So ist die äußere Schleife (k) muss von 0 bis n - 2 (eins weniger als die letzte Element) iterieren, und für jede Außenschleifeniteration der inneren Schleife muss von k + 1 (erstes Element oberhalb k) zu n - 1 (das letzte Element) iterieren .

HINWEIS: purer Zufall scheint es, dass der ursprüngliche Code tut erscheinen korrekt zu arbeiten, auch wenn es auf den ersten Blick scheint, dass es nicht sollte. Ich habe es mit verschiedenen Rand Fällen getestet und obwohl es viele redundante Swaps führt, scheint das Endergebnis immer sortiert (überraschend, obwohl die Ausgabe in absteigend Reihenfolge ist, während der feste Code Ergebnisse in aufsteigend Reihenfolge erzeugt, wie erwartet). Kredit an Jonathan Leffler für die Aufdeckung dieser - siehe sein answer and demo program.

---

Ein weiterer kleiner Punkt - dieser Test:

 if (values[k] >= values[j]) 

sollte eigentlich nur sein:

 if (values[k] > values[j]) 

Es ist nicht falsch, wie es steht (der Code wird immer noch funktionieren) , aber es hat keinen Sinn, Elemente, die gleich sind, zu vertauschen, so dass es wie geschrieben etwas ineffizient ist.

Answer 2

Ich nahm Ihren Code und konvertierte in ein komplettes Programm. Es ist größer als ein MCVE, weil es Support-Code zum Mischen von Arrays und zum Drucken von Ergebnissen sowie eine main(), die diese natürlich ausführt.

#include <stdio.h> 
#include <stdlib.h> 

static int rand_int(int n) 
{ 
    int limit = RAND_MAX - RAND_MAX % n; 
    int rnd; 

    while ((rnd = rand()) >= limit) 
     ; 
    return rnd % n; 
} 

static void shuffle(int *array, int n) 
{ 
    for (int i = n - 1; i > 0; i--) 
    { 
     int j = rand_int(i + 1); 
     int tmp = array[j]; 
     array[j] = array[i]; 
     array[i] = tmp; 
    } 
} 

static void print_array(int n, int a[n]) 
{ 
    for (int i = 0; i < n; i++) 
     printf(" %d", a[i]); 
    putchar('\n'); 
} 

static void sort(int values[], int n) 
{ 
    for (int k = 0; k < n; k++) 
    { 
     for (int j = 0; j < n; j++) 
     { 
      if (values[k] >= values[j]) 
      { 
       int temp = values[k]; 
       values[k] = values[j]; 
       values[j] = temp; 
      } 
     } 
    } 
} 

int main(int argc, char **argv) 
{ 
    if (argc > 1) 
    { 
     long l = strtol(argv[1], 0, 0); 
     unsigned u = (unsigned)l; 
     printf("Seed: %u\n", u); 
     srand(u); 
    } 

    int data3[3] = { 3, 1, 2 }; 
    print_array(3, data3); 
    sort(data3, 3); 
    print_array(3, data3); 

    int data5[5] = { 0, 2, 6, 1, 5, }; 
    for (int i = 0; i < 5; i++) 
    { 
     shuffle(data5, 5); 
     print_array(5, data5); 
     sort(data5, 5); 
     print_array(5, data5); 
    } 

    int data9[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
    for (int i = 0; i < 9; i++) 
    { 
     shuffle(data9, 9); 
     print_array(9, data9); 
     sort(data9, 9); 
     print_array(9, data9); 
    } 

    return 0; 
} 

Der Shuffle-Code implementiert eine Fisher-Yates shuffle und ist basiert auf Code von einem answer von Roland Illig. Wenn sie ohne ein Seed-Argument aufgerufen wird, erzeugt sie jedes Mal dieselbe Ausgabe.

Code kompiliert und getestet auf macOS Sierra 10.12.1 mit GCC 6.2.0.

Ein Beispiel Ausgabe:

Seed: 123456789 
3 1 2 
3 2 1 
6 0 1 5 2 
6 5 2 1 0 
0 6 1 2 5 
6 5 2 1 0 
0 1 2 6 5 
6 5 2 1 0 
5 0 6 1 2 
6 5 2 1 0 
1 6 5 2 0 
6 5 2 1 0 
0 4 8 3 7 5 1 6 2 
8 7 6 5 4 3 2 1 0 
7 4 0 5 6 8 3 2 1 
8 7 6 5 4 3 2 1 0 
1 2 7 5 0 8 3 6 4 
8 7 6 5 4 3 2 1 0 
3 8 7 5 2 1 0 6 4 
8 7 6 5 4 3 2 1 0 
1 4 2 6 3 0 7 5 8 
8 7 6 5 4 3 2 1 0 
2 3 7 4 8 0 5 6 1 
8 7 6 5 4 3 2 1 0 
3 4 5 8 6 2 0 7 1 
8 7 6 5 4 3 2 1 0 
3 6 7 4 8 2 5 1 0 
8 7 6 5 4 3 2 1 0 
0 8 7 3 4 6 5 1 2 
8 7 6 5 4 3 2 1 0 

Dies zeigt die Daten in absteigender Reihenfolge jedes Mal sortiert werden, trotz unterschiedlicher randomisierten Eingänge.