알고리즘 퀵 정렬(Quick Sort)

문제

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

 

알고리즘 종류

• Selection sort (내부 : 교환)
• Bubble Sort (내부 : 교환)
• Insertion Sort (내부 : 삽입)
• Quick Sort (내부 : 교환)
• Shell Sort (내부 : 삽입)
• Merge Sort (내부 : 병합)
• Heap Sort (내부 : 선택)
• Radix Sort (내부 : 분배)

 

퀵 정렬 알고리즘이란?

퀵 정렬 알고리즘의 가장 큰 특징은, 이전에 배웠던 선택 정렬, 버블 정렬, 삽입 정렬과 다르게 빠른 알고리즘이라는 것입니다.

퀵 정렬은 '분할 정복' 알고리즘으로 평균 속도가 O(Nlog2N)입니다.

 

- 분할 정복 (divide and conquer)방법이란?

1. 문제를 작은 2개의 문제로 분리하고 각각을 해결합니다.

2. 결과를 모아서 원래의 문제를 해결하도록 합니다.

 

- 퀵 정렬 방법

1. 리스트 안에 있는 한 요소를 선택합니다. 이렇게 고른 원소를 (pivot)이라고 합니다.

2. 피벗을 기준으로 피벗보다 작은 요소들을 모두 피벗의 왼쪽으로 옮기고, 피벗보다 큰 요소들을 모두 피벗의 오른쪽으로 옮깁니다.

3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬합니다.

4. 리스트들이 더 이상 분할이 불가능할 때까지 반복합니다.

 

퀵 정렬 단계

- 분할(Divide) : 피벗을 기준으로 비균등하게 2개의 부분배열로 분할한다.

- 정복(Conquer) : 부분 배열을 정렬한다. 

- 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

 

퀵 정렬 알고리즘

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

void main() {
	vector<int> target = { 1, 5, 8, 10, 7, 6, 3, 2, 9, 4 };
	int n = target.size();
	int temp;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j > 0; j--) {
			if (target[j] < target[j - 1]) {
				temp = target[j - 1];
				target[j - 1] = target[j];
				target[j] = temp;
			}
			else
				break;
		}

		// i번째 정렬 결과 출력
		for (int c = 0; c < n; c++) {
			cout << target[c] << " ";
		}
		cout << endl;
	}
}

 

  위의 소스코드는 서로인접한 값 array[j] 와 array [j+1] 를 비교해서 더 작은값을 앞으로 보내는 과정을 가집니다.

 

삽입 정렬(bubble sort) 알고리즘의 특징

장점

- 구현이 간단하다

- O(n^2)인 선택 정렬이나 버블 정렬과 같은 알고리즘에 비해 안정적이고 빠른 정렬이다.

 

단점

- 배열이 길어지면 효율이 점차 떨어진다.

 

삽입 정렬의 시간복잡도

최고 O(N)

이동없이 1번씩 비교할 경우

 

최저 O(N^2)

n-1, n-2, n-3, ... , 2, 1 번 = n(n-1)/2

T(n) = O(n^2)

 

정렬 알고리즘	최고	평균	최저	Run-time
삽입 정렬	n	n^2	n^2	7.438
선택 정렬	n^2	n^2	n^2	10.842
버블 정렬	n^2	n^2	n^2	22.894
셸 정렬	n	n^1.5	n^2	0.056
퀵 정렬	nlog2n	nlog2n	n^2	0.014
힙 정렬	nlog2n	nlog2n	nlog2n	0.034
병합정렬	nlog2n	nlog2n	nlog2n	0.026