[Sort] 퀵 졍렬

1. 소개

퀵정렬은 호어가 개발한 정렬 알고리즘입니다.

여타 정렬 알고리즘보다 속도가 빠르고 사용도 쉬워 가장많이 쓰이는 정렬입니다.

2. 장점 & 단점

속도가 빠르고 사용이 용이합니다.

불안정 정렬이라 최악의경우  O(n²)번의 비교를 수행하고, 평균적으로 O(nlog n) 번의 비교를 수행합니다.

3. 정렬 순서

< 시작하기전 알아야될것 >

right, left는 값을 찾는 주소

pivot은 값을 분류하기위한 기준점

left < Pivot < right 조건에 어긋나면 교환하고

right가 움직였다면 left가 움직임 ( right는 반대겠죵 )

- 정렬되지 않은 임의의수 6개가 있습니다.

 

- left 인덱스에 있는 값을 Pivot으로 잡겠습니다.

- right부터 움직입니다.

- 처음부터 조건 Out ! 교환

- 이제 left 가 움직일 차례 

- 조건 out!

- 교환

- right도 조건 OUT

- 교환

- left와 right가 일치할때 pivot을 삽입

-  오른쪽은 정렬완료 ( 코드상으론 어차피 들어가긴할텐데 달라질건 없음 ) 

- left 의 값 pivot get

- right 조건 찾는중

- 맞는 조건이없어서 둘이 만난곳 그대로 삽입

- 다시 left값을 피벗값으로

- right가 조건에 틀리니 교환

- left 조건 찾기

- left와 right 가 같아진곳에 pivot 삽입

- 마지막으로 left 있는곳에 pivot get

right 와 left가 만났으므로 pivot 그자리에 그대로 삽입

이렇게 정렬이 완료되었습니다.

아직도 모르겠다면

https://www.youtube.com/watch?v=S2c4zAGgVgI

전 이거보고 확실히 이해했어요 'ㅁ'

4.코드

s

#include <stdio.h>
 
// 1. 퀵 정렬
#if 1
 
void q_sort(int numbers[], int left, int right);
 
void QuickSort(int numbers[], int dataSize)
{
    q_sort(numbers, 0, dataSize - 1);
}
 
// left < pivot <  right
// 1. pivot 을 하나 잡는다. 
// 2. pivot == left, right를 잡는다.
// 3. right부터 시작해서 조건에걸릴떄까지 내려온다.
// ( 조건: 1_ left == right || 2_ right < pivot )
// 1_ 에 걸리면 Left도 똑같은 조건으로 돌껀데 어차피 거기서도 걸리니 마무리작업으로
// 2_ 에 걸리면 그자리에서 교환수행하고 Left를 출발시킴
// 4. 3번의 과정을 left == right 될때까지 수행한다.
// 4번이 끝나면 마무리작업을 실행한다.
// 5. 마무리작업 
// pivot의 값은 numbers[left] or numbers[right]에 넣어준다 ( 같기때문 )
// left의 인덱스를 pivot에 넣어준다 ( 이때 pivot은 index의 기능 ) ( 끝날떄 left의 값임 )
// l_hold와 r_hold의 값을 left, right에 넣어둠 ( 재귀함수를 이용해 풂 )
//  left(l_hold) 가 pivot(인덱스) 보다 작으면 재귀로 들어가 한번더 함 right자리(pivot-1)해서 q_sort실행
// right(r_hold) 가 pivot(인덱스) 보다 크면   재귀로 들어가 한번더 함 left자리(pivot+1)해서 q_sort실행
 
void q_sort(int numbers[], int left, int right)
{
    // left와 right가 같다면 리턴(재귀 탈출) 
    if (left == right) return;
    int pivot, l_hold, r_hold;
 
    // left와 right와 pivot의 값을 넣어준다
    l_hold = left;
    r_hold = right;
    pivot = numbers[left];
 
    // 왼쪽이 오른쪽이랑 같아질때까지 돈다.
    while (left < right)
    {
        // pivot이 numbers[right]보다 크지않거나 left가 right보다 작으면 right를 계속 내린다.
        while ((numbers[right] >= pivot) && (left < right))
            right--;
 
        // 다 내렸는데 둘이 같지얂다면 교환 
        if (left != right)
        {
            numbers[left] = numbers[right];
            left++;
        }
 
        // 왼쪽은 반대로 left를 올린다
        while ((numbers[left] <= pivot) && (left < right))
            left++;
 
        // 다내리면 마찬가지
        if (left != right)
        {
            numbers[right] = numbers[left];
            right--;
        }
    }
    // left와 right가 같아진다면
    // pivot에 left의 위치를 넣어주고
    // 첨에 들고있던 hold값들을 넣어준다.
    numbers[left] = pivot;
    pivot = left;
    left = l_hold;
    right = r_hold;
 
    // left가 pivot 보다 작으면 아래 재귀함수
    // right가 pivot 보다 크면 재귀함수 호출
    if (left < pivot)
        q_sort(numbers, left, pivot - 1);
    if (right>pivot)
        q_sort(numbers, pivot + 1, right);
 
 }
 
 
 
int main()
{
    int data[] = { 99, 51, 30, 22, 75, 1, 2, 18, 66 };
    int dataSize = sizeof(data) / sizeof(data[0]);
    int i;
    QuickSort(data,dataSize);
 
    for (int i = 0; i < dataSize; i++)
    {
        printf("%d ", data[i]);
    }printf("\n");
 
    return 0;
}