[자료구조] quicksort algorithm 문제

 

 

int partition(record arr[], int low, int high) {
    char* pivot = arr[high].name; 
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {

        if (strcmp(arr[j].name, pivot) < 0) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

 

 

우리는 pivot을 배열의 맨 끝 요소로 둘 것이다. 그리고 pivot보다 큰 값은 pivot의 오른편에, pivot보다 작은 값은 pivot의 왼편에 배치해야 한다. 그래서 i=low-1이라는 변수를 두고, pivot보다 작은 값이 나올 때마다 i를 점진적으로 ++시키며 맨 앞자리로 옮겨 주었다.

 

 

마지막에는 pivot 값도 알맞은 곳(i+1번째)에 배치해 준 후, 해당 index를 반환값으로 돌려준다.

 

void quickSort(record arr[], int low, int high) {
    if (low < high) {

 
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

 

 

반환값으로 받은 index를 기준으로 다시 두 번의 quickSort 함수 호출을 수행한다. 이러한 과정이 반복되는 재귀 호출 덕분에 우리는 결론적으로 모든 파티션을 순회할 수 있고, 따라서 모든 요소를 돌아 올바른 정렬이 수행된다.

 

 

 

 

 

+ swap 함수

 

void swap(record* a, record* b) {
    record temp = *a;
    *a = *b;
    *b = temp;
}