내 quicksort 구현의 문제점은 무엇입니까?

Question

내 순진 퀵 알고리즘에 관한 단지 빠른 (하하하) 질문 : 시험 배열의 코드를 실행하면

#include <iostream> 

template <class T> 
void quicksort2(T array[] , int start, int end){ 
    int i = start; 
    int j = end; 
    int temp; 
    int pivot = (end - start)/2; 

    // Partioning 
    while(i <= j){ 

    while(array[i] < array[pivot]){ 
     i++; 
    } 
    while(array[j] > array[pivot]){ 
     j--; 
    } 

    if(i <= j){ 
     temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     i++; 
     j--; 
    } 
    } 

    // Sorting partions 
    if(start <= j){ 
    quicksort2(array , start , j); 
    } 
    if(end >= i){ 
    quicksort2(array , i , end); 
    } 
} 

, 보인다을 그 배열합니다 (이하 측의 왼쪽)가 정렬되고 오른쪽을 정렬하지 않고 무한 루프를 만듭니다.

코드를 실행하기 전에 약간의 경고가 표시되며 테스트 배열에서 코드를 실행하면 컴퓨터가 정지되는 경우가 있습니다.

어쨌든 도움 주셔서 감사합니다! 또한, 숙제가 아닙니다 (정렬 알고리즘을 사용하여 어떤 방면에서 배트를 배울 필요가 있습니까?)

Answer 1

질문에 대한 답변을 드리겠습니다.

시작 == 끝 부분에서 메서드가 호출되는 경우를 어떻게 처리합니까?

각 실행마다 피벗 주위에서 하위 섹션을 나눕니다. 따라서 각 재귀 실행에는 마지막 시간 길이의 1/2이 있습니다. 먼저 전반을 정렬 한 다음 처음 1/4을 정렬 한 다음 처음 1/8을 정렬합니다. 결국, start = end = 0 인 메소드를 호출하게됩니다. 0 - 0/2가 0 인 피벗을 만듭니다.

코드를 통해 케이스를 실행하면, 메소드가 자신과 하나의 항목을 정렬하려고하는 경우를 처리합니다. 무한 재귀 루프에서 멈출 때까지 충돌이 발생할 것입니다. ...

스택 오버플로.

Answer 2

'='을 사용하는 것이 좋습니다. 피벗 포인트와 비교할 때> = 및 < = 사용할 수 있다고 생각하지만 스왑을 수행 할 때는 필요하지 않습니다.

키커는 재귀 호출입니다. =를 사용하고 싶지는 않습니다. 무한 재귀의 원인이라고 생각합니다. 결국 j가 시작보다 작을 수 없으므로 결국 충돌 할 것입니다. 그래서 기본적으로 =와 비교하고, 제거하고, =없이 모든 비교를 추가합니다.