[Algorithm] Quick Sort

오늘 알아볼 내용은 Quick Sort이다.

 

왜 많고 많은 정렬 알고리즘(버블정렬, 삽입정렬, 힙정렬, 합병정렬, 등등....) 중에 하필 Quick Sort??

- 가장 많이 쓰는 정렬 알고리즘 중의 하나이기도 하고, 그만큼 꼭 알아야 하는 정렬 알고리즘 중에 하나이기 때문이다.

 

QuickSort 동작원리 [출처 - 위키백과]

 

Quick Sort의 동작 원리

- 기준 값(Pivot)을 정한 후에, 기준 값의 앞에는 기준 값보다 작은 모든 원소가 가고, 피벗 뒤에는 기준 값보다 큰 모든 원소들이 가게 된다. 이렇게 리스트를 둘로 나누고 나면, 분할된 두개의 리스트에서 같은 작업을 반복한다. 이 두개의 리스트가 0 또는 1이 될 때까지 진행한다.

 

즉, 운빨 알고리즘(?) 이라고 할 수 있다. 왜냐하면, 기준 값을 어떻게 고르는가에 따라서 알고리즘이 굉장히 효율적으로 동작하거나, 굉장히 비효율적으로 동작할 수 있기 때문이다. 그러므로, 기준 값을 '잘' 고르는 것이 굉장히 중요하다고 할 수 있다.

 

우리는 굳이 이 알고리즘을 구현할 필요가 없다. 왜냐하면? C++ 11의 Algorithm에서 Sort함수를 사용하면 되기 때문이다. 그러므로 간단하게 함수만 알아보고 마치도록 하겠다.

 

퀵소트 사용 예

sort(begin iterator, end iterator, 비교함수)

- 파라미터는 위와 같이 들어간다. 비교함수와 같은 경우, 오름차순/내림차순을 사용할 경우 굳이 구현할 필요 없이 greater나 less를 사용하면 된다. 이때, 비교함수의 경우 bool을 리턴해주는 형식이여야만 한다.

 

실행 결과

 

이렇게만 하면 아쉬우니까 간단하게 비교함수도 만들어보자.

비교함수 예

단순히 int형으로 비교함수를 만드는건 뭐 의미가 없을테니, 간단하게 멤버변수 두개있는 클래스로 조건을 주고 구현해봤다. 이렇게 하면 두 멍멍이가 이름이 같을 경우 age를 가지고 정렬, 이름이 다를 경우 name을 가지고 정렬하도록 하였다. 

결과

간단하게 오늘은 여기까지 알아보도록 한다.

 

-- 추가사항 있으면 다음에 다시 쓸게욧