Quicksort 알고리즘 액세스 위반 작성 위치

Question

아래의 퀵 정렬 알고리즘을 구현하는 데있어 잘못된 점이 무엇입니까? 디버그는 "액세스 위반 기록 위치"를보고합니다. 나는 그것을 발견 할 수 없다. 피벗의 위치를 ​​sort 및 partition 함수의 인수로 전달해야합니까? 이 코드는 대화 형 온라인 데모 인 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

다음과 같은 변경 사항이 당신을 대신합니다. for 루프에서 i가 <인지 확인해야합니다. < = 거기에 있다면, 어떤 상황에서는 진전을 보이지 않을 것입니다. 그러나 알고리즘이 모든면에서 올바른지 지금은 확인하지 않았습니다.

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