[자료구조] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

• 퀵 정렬은 평균적으로 가장 빠른 정렬 방법으로 알려져있다.
• 분할 정복(Divide and Conquer) 방법을 사용하는 정렬이다.

 

퀵 정렬은 피봇(pivot)이라는 값을 기준으로 리스트를 나누어 정렬한다.

피봇의 설정은 여러가지 방법이 있는데, 우리는 첫번째 값을 피봇으로 설정하는 비교적 간단한 방법을 사용하겠다.

 

연산 방법은 쉽게 말하자면

피봇을 기준으로 왼쪽으로 이동하며 피봇보다 작은 값을 찾고 low에 저장한다, 오른쪽으로 이동하며 피봇보다 큰 값을 찾아 high에 저장한다.

그리고 그 두 값의 위치를 바꾼다.

반복한다.

그리고 high가 low보다 앞에 있다면 종료한다. pivot과 high의 위치를 바꾼다.

 

글로는 설명이 어려울 거 같아 사진을 참조했다.

개념이 이해가 어렵다면 https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

 

위 블로그를 참고하면 좋을 거 같다.

 

피봇을 이용한 퀵 정렬은 삽입정렬에 비해 구현이 복잡한 편이다.

코드를 첨부할테니, 차근차근 작성해보기 바란다.

 

퀵 정렬(Quick Sort)

#include <stdio.h>

// 배열의 요소를 교환하는 함수
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 분할 함수
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 마지막 요소를 피벗으로 선택
    int i = (low - 1);  // 피벗보다 작은 요소들의 인덱스를 관리

    for (int j = low; j <= high - 1; j++) {
        // 현재 요소가 피벗보다 작거나 같으면
        if (arr[j] <= pivot) {
            i++;  // 작은 요소들의 인덱스를 증가
            swap(&arr[i], &arr[j]);  // 요소 교환
        }
    }
    swap(&arr[i + 1], &arr[high]);  // 피벗을 올바른 위치에 삽입
    return (i + 1);  // 피벗의 위치 반환
}

// 퀵 정렬 함수
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 분할 인덱스: 이 인덱스를 기준으로 배열이 두 부분으로 나누어짐
        int pi = partition(arr, low, high);

        // 분할 후, 좌우 부분 배열을 각각 재귀적으로 정렬
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

 

 

실행 결과