[Algorithm] 퀵정렬 Quick Sort

🌟 퀵정렬 Quick Sort

정의:

• 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법

• 전체리스트를 2개의 부분 리스트로 분할하고, 각 리스트로 다시 반복하는 분할정복법

원리:

1. 리스트 안에 있는 한 요소를 피벗으로 선택 (리스트의 가장 왼쪽 요소)

2. low, high 값을 지정

   • low는 피벗보다 큰 값 (인덱스가 증가하면서)
   • high는 피벗보다 작은 값 (인덱스가 감소하면서)

3. low,high 교차가 안 되면 low, high를 교환
   교차가 된다면 left, high를 교환
   

구현:

#include <stdio.h>
#define swap(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
int count;
int partition(int list[], int left, int right){	// pivot의 위치 선정
	int pivot, temp, low, high;
    low = left;
    high = right+1;
    pivot = list[left];
    do{
    	do{
        	low++;
        }while(list[low]<pivot);
        do{
        	high--;
        }while(list[high]>pivot);
        if(low < high){
        	swap(list[low], list[high], temp);
        }
    }while(low<high);
    swap(list[left], list[high], temp);
    return high;
}

void quicksort(int list[], int left, int right){
	if(left<right){
    	int q = partition(list, left, right);
        quicksort(list, left, q-1);	// pivot을 기준으로 잘라서 다시 호출
        quicksort(lisr, q+1, right);
    }
    count++;
}

int main(){
	int list[9] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
    quicksort(list, 0, 8);
    printf("%d ", count);
    for(int i=0; i<9; i++){
    	printf("%d ", list[i]);
    }
    return 0;
}

당신의 시간이 헛되지 않는 글이 되겠습니다.
I'll write something that won't waste your time.