[삼성 알고리즘] 정렬 알고리즘(버블, 선택, 삽입, 병합, 퀵) 3

안녕하세요~!

이번 포스팅은 정렬 알고리즘(버블, 선택, 삽입, 병합, 퀵)의 포스팅의 마지막 포스팅으로 퀵 알고리즘에 대해 포스팅을 진행하겠습니다.

 

시작에 앞서

 

Merge sort에 대한 내용은 아래 URL에서 참조하시면 됩니다.

https://bluemoon-1st.tistory.com/14?category=851281

 

Bubble, Insert, Select Sort에 대한 내용은 아래 URL에서 참조하시면 됩니다.

https://bluemoon-1st.tistory.com/13?category=851281

 

 

1. Quick Sort

먼저 퀵소트역시 지난번에 설명했던 Merge Sort와 같이 Divide & Conquer의 대표적인 알고리즘 입니다. Merge Sort의 경우 N/2 씩 Divide가 진행되었지만 Quick Sort의 경우 pivot을 이용해서 Divide가 진행되는 차이점을 가지고 있습니다. 그럼 pivot을 통해 어떻게 Divide & Conquer 작업이 일어나는지 아래 예시를 통해 설명을 진행하겠습니다.

 

 

위와 같이 처음 배열에서 Pivot을 하나 잡아 줍니다. 위 예시에서는 가장 좌측의 데이터를 Pivot으로 잡았지만 Pivot을 잡는 것은 자유롭게 잡아도 되며 Pivot을 잡는 방법에 따라 Quick Sort의 성능이 좌우될 수 있기 때문에 Pivot을 효과적으로 잡는 알고리즘 역시 중요합니다.

 

 

Pivot을 잡아 준 후에는 배열을 순환하면서 Pivot보다 작은 값과 큰 값으로 데이터를 나눠줍니다.

그 후 Pivot을 기준으로 나뉘어진 두 데이터 덩어리를 Divide하고 각각의 데이터에서 또 Pivot을 선정하면서 Divide를 진행합니다.

전체적인 Divide는 위 과정의 반복이기 때문에 기본적으로 재귀를 이용한 방법이 Quick Sort 구현 방법으로 많이 사용됩니다.

 

 

 

최종적으로 Divide가 되면 데이터를 모두 하나의 배열로 Conquer하면 이미 정렬이 되어있으므로 Conquer 때 추가적인 작업이 필요하지는 않습니다.

 

Quick Sort의 성능은 평균적으로 O(NlogN)으로 알려져있지만

최악의 경우(이미 정렬이 된 경우) 처음 N-1번, Pivot으로 쪼갠 후 N-2번, Pivot으로 쪼갠후(2) N-3번 ... 이 되기 때문에 1+2+3+..+N-2+N-1로 O(N^2)의 성능을 보이고 있습니다.

하지만 Quick Sort의 경우 Merge와 달리 추가적으로 배열 공간에 할당할 필요없이 연산이 가능하기 때문에 메모리 측면에서 효율적인 면을 보일 수 있고 최악의 경우 O(N^2)인 부분도 Pivot을 설정하는 방법에 따라 부분적으로 해결이 가능합니다.

 

C++에서 제공하는 STL Library의 sort() 함수 역시 기본적으로 Quick Sort를 이용한 변형함수로 평균적으로 메모리, 속도 측면에서 우수한 성능을 가지고 있다고 보셔도 무방합니다. 때문에 알고리즘 문제를 해결할 때 정렬문제가 많이 출제되는데 이 때, 특정 정렬알고리즘을 묻는 문제가아니라면 대부분의 경우 연산 도중 필요한 정렬은 Quick Sort로 해결이 가능하기 때문에 Quick Sort를 이용해보는 방법을 추천드립니다!!(물론 개인적으로는 C++ STL Libary Sort 쓰는 것이 가장 편하고 좋다고 생각합니다...)

 

이번 포스팅은 여기까지하고 마무리하겠습니다~!

감사합니다!