Quicksort-Algorithmus Zugriffsverletzung Schreibort

Question

Was ist falsch bei der Implementierung des Quicksort-Algorithmus unten. Das Debug meldet "Schreibort der Zugriffsverletzung". Ich kann es nicht finden. Sollte ich die Position des Pivots als Argument an die sort und partition Funktionen übergeben? Dieser Code basiert auf dieser interaktiven Online-Demo: http://me.dt.in.th/page/Quicksort.

#include <cstdio> 
#include <cstdlib> 
#include <cstdint> 
#include <utility> 

#define LIST_SIZE (UInt)10 

typedef uint64_t UInt; 

void print(UInt * list, UInt size) { 
    for (UInt i = 0; i < size; i++) 
     printf("%llu ", list[i]); 

    printf("\n"); 
} 

void fill(UInt * list, UInt size) { 
    for (UInt i = 0; i < size; i++) 
     list[i] = (UInt)std::rand(); 
} 

UInt partition(UInt * list, UInt left, UInt right) { 
    UInt p = list[left], t = left + 1; 

    for (UInt i = left + 1; i <= right; i++) { 
     if (list[i] < p) { 
      std::swap(list[i], list[t]); 
      t++; 
     } 
    } 

    std::swap(p, list[t]); 

    return t; 
} 

void sort(UInt * list, UInt left, UInt right) { 
    UInt p; 

    if (left < right) { 
     p = partition(list, left, right); 

     sort(list, left, p - 1); 
     sort(list, p + 1, right); 
    } 
} 

void quicksort(UInt * list, UInt size) { 
    sort(list, 0, size - 1); 
} 

int main(int argc, char ** argv) { 
    UInt list[LIST_SIZE]; 

    fill(list, LIST_SIZE); 
    print(list, LIST_SIZE); 
    quicksort(list, LIST_SIZE); 
    print(list, LIST_SIZE); 

    return 0; 
} 

Answer 1

Die folgende Änderung macht den Trick für Sie. In der for-Schleife müssen Sie nach i < nach rechts suchen. Wenn Sie eine < = dort machen, werden Sie unter bestimmten Umständen keinen Fortschritt machen. Allerdings habe ich nicht überprüft, ob der Algorithmus in jeder Hinsicht korrekt ist.

UInt partition(UInt * list, UInt left, UInt right) { 
    UInt p = list[left], t = left + 1; 

    for (UInt i = left + 1; i < right; i++) { 
     if (list[i] < p) { 
      std::swap(list[i], list[t]); 
      t++; 
     } 
    } 

    std::swap(p, list[t]); 

    return t; 
}