[Algorithm] Quick Sort 구현하기
업데이트(2018.04.19): C++ 정렬 코드 추가
Quick Sort를 구현해보자
환경
- Python
- C++
Quick Sort란?
원리
- pivot을 정하고 pivot보다 작은 값들을 pivot의 왼쪽 pivot보다 큰 값들은 pivot의 오른쪽으로 위치시키고 pivot의 왼쪽 값들과 오른쪽 값들을 각각 따로 또 재귀를 통해 분할정복한다.
특징
O(nlogn)의 성능을 보이는 정렬 알고리즘중에 하나로 최악에는O(n^2)의 성능을 보이지만 일반적으로 빠른 성능을 나타내기에 보편적으로 많이 쓰는 알고리즘 입니다.Divide and Conquer이라는 분할정복 방법으로 정렬을 진행하며 자세한 부분은 다음을 참고하시면 좋습니다.in-place sorting: 정렬 할 원소들을 위한 추가적인 메모리를 사용하지 않고 현재 메모리에서 정렬을 진행
복잡도
- 시간복잡도:
평균 O(nlogn),최악 O(n^2) - 공간복잡도:
O(logn)(in-place sorting의 경우!)
구현 코드(Python)
in-place sort
- 메모리를 아낄 수 있다.
- 하지만 코드가 조금 더 복잡하다.
def swap(A, i, j):
tmp = A[i]
A[i] = A[j]
A[j] = tmp
def quick_sort(A, left, right):
if left < right:
p = partition(A, left, right)
# p 기준으로 왼쪽 값들은 p보다 작고 오른쪽 값들은 p보다 큼
quick_sort(A,left, p-1)
quick_sort(A,p+1,right)
def partition(A, left, right):
import random
# 랜덤하게 pivot 생성
pivot_index = random.randint(left, right)
pivot_value = A[pivot_index]
# 피벗값과 right의 값을 swap
swap(A, pivot_index, right)
# store_index를 기준으로
# 왼쪽에 pivot_value보다 작은 값들 위치시킴
store_index = left
for i in range(left, right):
if A[i] < pivot_value:
swap(A, i, store_index)
store_index += 1
swap(A, right, store_index)
return store_index
# 테스트 코드
import random
A = [random.randint(0,100) for _ in range(0,10)]
print(A)
quick_sort(A, 0, len(A)-1)
print(A)
not-in-place sort
- 코드가 간결하다.
- 하지만 추가적인 메모리를 사용한다.
def quick_sort(A):
if(len(A)>1):
import random
pivot = A[random.randint(0, len(A)-1)]
greater = [i for i in A if i > pivot]
smaller = [i for i in A if i < pivot]
middle = [i for i in A if i == pivot]
return quick_sort(smaller) + middle + quick_sort(greater)
else:
return A
# 테스트 코드
import random
A = [random.randint(0,100) for _ in range(0,10)]
print(A)
A=quick_sort(A)
print(A)
구현 코드(C++)
in-place sort
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
using namespace std;
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int a[], int left, int right) {
srand(time(NULL));
// left ~ right 사이의 값을 랜덤으로 생성
int pivot_index = rand() % (right + 1 - left) + left;
int pivot_value = a[pivot_index];
swap(&a[pivot_index], &a[right]);
// store_index를 기준으로
// 왼쪽에 pivot_value보다 작은 값들 위치시킴
int store_index = left;
for (int i = left; i < right; i++) {
if (a[i] < pivot_value) {
swap(&a[i], &a[store_index]);
store_index += 1;
}
}
swap(&a[store_index], &a[right]);
return store_index;
}
void quick_sort(int a[], int left, int right) {
if (left < right) {
int p = partition(a, left, right);
quick_sort(a, left, p - 1);
quick_sort(a, p + 1, right);
}
}
int main() {
int a[5];
int len = sizeof(a) / sizeof(int); // 배열길이
// 랜덤함수를 위한 srand와 seed
srand(time(NULL));
// 배열 초기화
for (int i = 0; i < len; i++) {
// 1 ~ 50까지의 난수 생성
a[i] = rand() % 50 + 1;
}
// 정렬 전 출력
for (int i = 0; i < len; i++) {
cout << a[i] << ' ';
}
cout << '\n';
// 퀵정렬
quick_sort(a, 0, len - 1);
// 정렬 후 출력
for (int i = 0; i < len; i++) {
cout << a[i] << ' ';
}
cout << '\n';
return 0;
}