[컴퓨터알고리즘] Quick sort(퀵소트) 알고리즘

Divide and Conquer 알고리즘의 quicksort알고리즘에 대해 알아보자!!!!!

(위키피디아 ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC를 참고하여 작성했습니다)

퀵소트는 정렬 알고리즘의 하나인데 평균적으로 시간 복잡도가 O(nlogn)으로 빨라서 자주 쓰인다!! (worst case에는 O(n^2))

기본 알고리즘은

1. 리스트 가운데에서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 하는데 아무거나 고르면 된다!! 근데 나는 제일 앞의 원소를 선택할것이다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 하는데 분할을 마친 뒤에 피벗은 더이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때 까지 반복한다.

사실 말만 봐서는 엥?? 스럽다!! 그래서 한번 그림으로 알아보자. 퀵소트의 목적은 pivot 값을 기준으로 pivot의 왼쪽에는 pivot보다 작은 값을 두고 오른쪽에는 pivot보다 큰 값을 두는것이다!!!!!

이런 배열이 있다고 가정하고 처음 시작이니까 pivot을 맨 앞 원소로 설정하고 맨 오른쪽을 right, 피벗 제외 제일 왼쪽을 left라고 하자. 이제 left -> right쪽으로 자리를 하나씩 옮겨가면서 피벗보다 큰 값이 있는지 찾고 right -> left쪽으로로 하나씩 옮겨가면서 피벗보다 작은 값이 있는지 확인해보자. (피벗의 왼쪽에 작은 값이, 피벗의 오른쪽에 큰 값이 있게 하기 위해서 이 조건을 만족하지 않는 애들을 찾아서 바꿔줄것이다!!!)

피벗(17)보다 큰 수 20을, 피벗보다 작은 수 7을 찾았다. 이제 얘네 둘을 교환해준다.

이제 다시 left -> right쪽으로 옮겨가면서 피벗보다 큰 값이 있는지 찾고 right -> left로 옮겨가면서 피벗보다 작은 값이 있는지 찾아보자!!! 이걸 계속 반복해 줄꺼다!!! 언제까지 하냐면 이 left와 right가 엇갈릴때까지!!!

허걱 근데 이번에 right와 left 둘이 엇갈려버렸다..!!!! 이러면 반복문이 종료되는거다. 그럼 이제 이 엇갈린 right(피벗보다 작은 수)와 pivot을 바꾸면 된다. 그러면 

원래 피벗(17)을 기준으로 피벗의 왼쪽에는 피벗보다 작은 값들이, 피벗의 오른쪽에는 피벗보다 큰  값들이 있게 된다. 그러면 이 피벗의 자리는 고정된거다. 더이상 이 피벗(17)의 자리는 바뀔일이 없다.

이제 이 왼쪽부분(리스트)에서 또 퀵소트를 진행하고 또 오른쪽 리스트에서도 퀵소트를 진행한다. 왼쪽 리스트의 범위는 0~right - 1 까지이고 오른쪽 리스트의 범위는 right + 1 ~ n(배열의 크기) - 1 까지이다. 

이렇게 쪼개진 리스트에서 다시 그들만의 리그를 시작해주자!!! 이러면 왼쪽 리스트가 다시 왼쪽리스트/ 오른쪽 리스트로 나뉠 거고 오른쪽 리스트도 다시 오른쪽리스트/왼쪽리스트로 나눠질것이다. 이걸 이 쪼개진 리스트의 크기가 1이하가 될때까지 진행해주면 끝이다.

이렇게 그림으로 퀵소트에 대해서 한번 알아봤다. 이제 코드를 보자!!

#include<iostream>
#include<algorithm>
using namespace std;

void quickSort(int* a, int start, int end) {
	if (start >= end) return;
	int pivot = start;
	int right = end;
	int left = start + 1;
	while (right >= left) { // 엇갈릴때까지 반복
		while (a[left] < a[pivot]) left++;
		while (a[right] > a[pivot]) right--;
		if (left < right) {
			int temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
		else break;
	}
	int temp = a[pivot];
	a[pivot] = a[right];
	a[right] = temp;; // 엇갈렸으니까 바꿈
	quickSort(a, 0, right - 1);
	quickSort(a, right + 1, end);
}

int main() {
	int a[7] = { 17, 9, 4, 20, 72, 109, 7 };
	for (int i = 0; i < 7; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';
	quickSort(a, 0, 6);
	for (int i = 0; i < 7; i++) {
		cout << a[i] << ' ';
	}
	return 0;
}