퀵 정렬(Quick Sort)

퀵 정렬(quick sort) 알고리즘의 개념

• ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발한 정렬 알고리즘
• 불안정 정렬/ 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
  • 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할
• 분할 정복(divide and conquer) 방법
  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결
  • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.

과정 설명
1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot)
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
* 리스트의 크기가 0이나 1이 될 때까지 반복한다.

퀵 소트(Quick Sort) C++ 코드

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

int paritition(vector<int>& v, int left, int right)
{
	
	int pivot = v[left];//피벗의 위치는 가장 왼쪽에서 시작
	int low = left + 1;
	int high = right;

	while (low <= high) // 교차되기 전까지 반복한다 
	{
		while (low <= right && pivot >= v[low]) // 피벗보다 큰 값을 찾는 과정 
		{
			low++; // low를 오른쪽으로 이동 
		}
		while (high >= (left+1) && pivot <= v[high])// 피벗보다 작은 값을 찾는 과정
		{
			high--; // high를 왼쪽으로 이동
		}
		if (low <= high) // 교차되지 않은 상태이면 스왑 과정 실행 
		{

			int temp = v[low];
			v[low] = v[high];
			v[high] = temp;


		}


	}
	// 피벗과 high가 가리키는 대상을 교환 
	int temp = v[left];
	v[left] = v[high];
	v[high] = temp;

	// 옮겨진 피벗의 위치정보를 반환 
	return high;



}

void QuickSort(vector<int>& v, int left, int right)
{
	if (left < right)
	{
		int q = paritition(v, left, right);  // 둘로 나누어서
		QuickSort(v, left, q - 1); // 왼쪽 영역을 정렬한다.
		QuickSort(v, q + 1, right); // 오른쪽 영역을 정렬한다.

	}

}

int main()
{
	vector<int> v = { 5,4,3,2,1 };
	QuickSort(v, 0, v.size()-1);
	for (auto& e : v)
	{
		cout << e;

	}


	return 0;
}