[알고리즘] 퀵 정렬_원리

앞서 배운 선택 정렬 , 버블 정렬, 삽입정렬 알고리즘 모두 시간 복잡도 O(N ^ 2)를 가지는 알고리즘이다.

이러한 알고리즘은 데이터의 갯수가 10만 개만 넘어가도 일반적인 상황에서는 매우 사용하기 어려운 알고리즘이다.

​

퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬

-> 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤 배열을 반으로 나눈다.

​

퀵 정렬은 특정한 기준 값이 있는데 이를 피벗이라고 하며 피벗값을 기준으로 왼쪽과 오른쪽으로 나눈다.

퀵 정렬의 예

3 7 8 1 5 9 6 10 2 4

피벗 값(일반적으로 가장 앞에있는 값) : 3

3 2 8 1 5 9 6 10 7 4 <= 3부터 -> 검색했을 때 3보다 큰 7과 <- 검색했을 때 3보다 작은 2의 위치를 바꿈

3 2 1 8 5 9 6 10 7 4 <= 위와 같이 검색해서 8과 1의 위치를 바꿈

1 2 ​3​ 8 5 9 6 10 7 4 <= 위와 같이 검색했을 때 3보다 작은 1과 3보다 큰 8이 서로 인덱스가 엇갈렸을 때 3과 1의 위치를 바꿈

1 2 3 8 5 9 6 10 7 4 <= 1을 기준으로 다시 위와 같이 검색을 했을 때 1보다 작은 값이 없기때문에 1의 위치는 정해졌다.

1 2 3 8 5 9 6 10 7 4 <= 2를 기준으로 다시 검색해도 1외엔 없기 떄문에 위치가 정해졌다.

1 2 3 8 5 4 6 10 7 9 <= 8을 기준으로 검색하여 4와 9의 위치를 바꾸어 주었다.

1 2 3 8 5 4 6 7 10 9 <= 8을 기준으로 다시 검색해 10과 7의 위치를 바꾸어 주었다.

1 2 3 7 5 4 6 8 10 9 <= 8을 기준으로 다시 검색하였을 때 7과 10의 인덱스가 엇갈렸기 때문에 8과 7의 위치를 바꾸어준다.

이러한 방법으로 값을 정렬한다.

​

선택 정렬, 버블 정렬, 삽입 정렬로 1 2 3 4 5 6 7 8 9 10 정렬 시 -> N ^ 2 = 10 * 10 = 100

퀵 정렬로 정렬 시 1 2 3 4 5 => 5 * 5 = 25 => 25 + 25 = 50 -> 반으로 쪼갠다는 말은 2씩 계속해서 나눠 계산을 한다고 하여

6 7 8 9 10 => 5 * 5 = 25 N * logN

​

대표적으로 '분할 정복' 알고리즘으로 평균 속도가 O(N * log2N)입니다.

 

삽입 정렬의 시간 복잡도

O(N * logN)

 

※ log2N -> N이 1,000,000일 때 ? N : 20