[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;
}


참고자료

[Linux] 쉘 스크립트에서 멀티프로세스(혹은 스레드) 기능 사용하기

> 백그라운드로 명령어를 실행해서 병렬적으로 실행되는 멀티 프로세스 환경을 만들어보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)## 멀티프로세스? 병렬처리? 멀티스레드? 백그라운드 프로세스?- 여기서 진행할 방식...… Continue reading