[기본문제풀이] quick_sort

풀이 일시 : 2020-07-28

​

퀵정렬

-> 피벗값을 설정하고 나눈다. 보통 첫번째 원소를 피벗으로 설정

-> 피벗값보다 큰 값을 왼쪽부터 찾고 피벗보다 작은값을 오른쪽부터 찾는다.

-> 피벗값보다 작은값,큰값찾으면 : 작은값의 인덱스가 큰 값의 인덱스보다 크면 값끼리자리바꿈

-> 피벗값보다 작은값,큰값찾으면 : 작은값의 인덱스가 큰 값의 인덱스보다 작으면 피벗과 작은값 자리바꿈.

시간복잡도는 O(N*logN)

​

문제 :

1 10 5 8 7 6 4 3 2 9 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오

 

풀이 :

#include <stdio.h>

int number = 10;
int data[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

void quickSort(int* data, int start, int end) { //*data 나 data[]나 ..
	if (start >= end) { //원소가 한개일 경우 정렬할 필요가없다
		return;
	}
	int key = start; //키는 첫번째 원소인덱스
	int i = start + 1; //i는 첫번째 원소인덱스 +1번째
	int j = end; //j는 end인덱스 동일
	int temp; //swap 위함

	while (i <= j) {//i와 j가 엇갈릴때까지 반복
		while (data[i] <= data[key] && i<=end) { //큰값을 왼쪽부터 찾는다. 크면 빠져나옴
			i++; //엇갈리기 위해 가는 과정 i를 ++해준다.
		}
		while (data[j] >= data[key] && j > start) { //작은 값을 오른쪽부터 찾는다. 작으면 빠져나옴
			j--; //엇갈리기 위해 가는 과정 j를 --해준다.
		}
		if (i > j) { //피벗과 작은값 SWAP. (엇갈린경우이다)
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else { //그대로 작은값이 오른쪽에 큰값이 왼쪽에 머물러있다면 둘이바꿈
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	quickSort(data, start, j-1); //키값 기준 왼쪽 (j자리가 곧 피벗자리가됐으니깐)
	quickSort(data, j + 1, end); //키값 기준 오른쪽
}

void show() {
	int i;
	for (i = 0; i < number; i++) {
		printf("%d", data[i]);
	}
}

int main() {
	quickSort(data, 0, number - 1);
	show();
	return 0;
}