(8)[Chapter5]정렬_퀵정렬(이론 + 코드), 작성중

 

Chapter5_2_퀵정렬_이론_코드구현.pdf

3.78MB

#내가 전까지 써왔던 Partition()의 퀵소트 코드

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#pragma warning (disable : 4996)
 
int Partition(int* arr,int start, int end) {
 
    //1_ random으로 pivot 선정하기
 
    int ridx = start + rand() % (end - start + 1);
 
    //2_ pivot과 마지막을 swap()
    int tmp = arr[ridx];
    arr[ridx] = arr[end];
    arr[end] = tmp;
 
    //3_ 비교 연산 시작
    int rose = start;
    int pivot = arr[end];//◆실수1 : ridx가 아닌 end임...
 
 
    for (int i = start; i < end; i++) {
        //pivot이 맨마지막 => scan 범위에서 제외한다.
        if (arr[i] <= pivot) {//scan 중 약자나 같은 놈 발견
            //=> ★rose와 i 원소 Swap
            //=> rose 증감
            tmp = arr[rose];
            arr[rose] = arr[i];
            arr[i] = tmp;//◆실수2
            rose++;
        }
    }
 
    //4_ scan 후 pivot이 있을자리가 rose로 정해짐
    tmp = arr[rose];
    arr[rose] = arr[end];
    arr[end] = tmp;
 
    //5_ rose (pivot 이 위치한 인덱스) 반환
    return rose;
}
 
//퀵소트 : 분할 정복
void QuickSort(int* arr, int start , int end) {
    //종료 조건
    if (start >= end) return;
    //Pivot index를 Partition으로 호출, 반화
    int index = Partition(arr, start, end);
 
    //분할 정복 재귀호출
    QuickSort(arr, start, index - 1);
    QuickSort(arr, index +1, end);
 
}
 
int main() {
 
    int N;
    int* parr = NULL;
 
    srand((unsigned)time(NULL)); //◆랜덤시드
 
    scanf("%d", &N);
 
    parr = (int*)malloc(sizeof(int) * N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &parr[i]);
    }
 
    QuickSort(parr, 0,N-1);
 
    for (int i = 0; i < N; i++) {
        printf(" %d", parr[i]);
    }
    printf("\n");
 
    free(parr);
 
    return 0;
}
 

 

##교재에서 나온 Partition()의 퀵소트 코드

 

//Partition
int Partition(int* arr, int start, int end) {
 
    //1_랜덤Pivot index 선정
    int ridx = start + rand() % (end - start + 1);
    //2_ 처음과 자리바꿈
    int tmp = arr[start];
    arr[start] = arr[ridx];
    arr[ridx] = tmp;
 
    int Pivot = arr[start];
    int left= start +1;
    int right = end;
 
    while (left <= right) {
        //left이동(Pivot보다 큰수가 나올때까지)
        while (left <= right && Pivot >= arr[left])left++;
        //right이동(Pivot보다 큰수가 나올때까지)
        while (left <= right && Pivot <= arr[right]) right--;
 
        if (left < right) {
            tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }
        else break;
    }
    tmp = arr[start];
    arr[start] = arr[right];
    arr[right] = tmp;
 
    return left;
}

 

##qsort() C언어 라이브러리 시용 코드

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}
 
int main() {
 
    int N;
    int* parr = NULL;
 
    srand((unsigned)time(NULL)); //◆랜덤시드
 
    scanf("%d", &N);
 
    parr = (int*)malloc(sizeof(int) * N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &parr[i]);
    }
 
    qsort(parr,N,sizeof(int),compare);
 
    for (int i = 0; i < N; i++) {
        printf(" %d", parr[i]);
    }
    printf("\n");
 
    free(parr);
 
    return 0;
}

##결론 : 교재방법이 훨씬 훨씬 더 시간복잡도에서 성능이 우수하다.

시간 복잡도 비교

메소드설명

<1번째 방법의 Partition>	피벗 선택이 end이고, 잘못된 피벗 선택으로 인해 효율성이 떨어질 수 있습니다.
<2번째 방법의 Partition>	피벗 선택이 start에서 랜덤하게 이루어지고, left와 right 포인터를 사용하여 분할합니다.

결론

<2번째 방법의 Partition>이 <1번째 방법의 Partition>보다 시간 복잡도 측면에서 더 우수합니다. 그 이유는 다음과 같습니다:

1. 피벗 선택의 일관성: <2번째 방법>은 start와 ridx를 교환하여 start를 피벗으로 사용합니다. 이 방식은 일반적으로 더 나은 분할을 제공할 수 있습니다.
2. 효율적인 Partition 과정: <2번째 방법>은 left와 right 포인터를 활용하여 분할 과정을 효율적으로 수행합니다. 이로 인해 평균적인 성능이 개선됩니다.
3. 최악의 경우 성능 보장: <2번째 방법>은 Partition 과정에서 while 루프를 사용하여 모든 원소를 한 번씩만 검사하므로 성능이 보장됩니다.