퀵 정렬 예제

백준 2750번 수 정렬하기

문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

5
5
2
3
4
1

예제 출력

1
2
3
4
5

---

퀵 정렬을 사용한 정답

#define _CRT_SECURE_NO_WARNINGS
#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];  // pivot 요소를 배열의 마지막 요소로 선택
    int i = low - 1;  // i는 더 작은 요소의 인덱스

    for (int j = low; j < high; 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);  // 피벗 오른쪽 부분을 정렬
    }
}
int main()
{
	int arr[1000];
	int N;
	
	scanf("%d\n", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
        
	}
	
	quickSort(arr, 0, N-1);
	for (int i = 0; i < N; i++) {
		printf("%d\n", arr[i]);
	}
	
}