[Programming] Quick Sort, Sort Algorithms #01

Quick Sort, Sort Algorithms

---

한국에서는 퀵 소트, 퀵 정렬 또는 빠른 정렬이라고 불리는 대표적인 자료구조(Data Structure) 알고리즘이다. Quick sort에 대한 설명은 포스트 하나에서 자세하게 다루기 어려운 관계로 포스트를 여러 개로 나누어서 소개를 하려고 한다. 이번 포스트에서는 간단하게 Quick sort에 대해서 알아보도록 하겠다.

Quick sort란?

한국에서는 퀵 소트 또는 퀵 정렬이라고 불리는 대표적인 자료구조(Data Structure) 알고리즘이다. Quick sort에 대한 설명은 포스트 하나에서 자세하게 다루기 어려운 관계로 포스트를 여러 개로 나누어서 소개를 하려고 한다. 이번 포스트에서는 Quick sort에 대한 근본적인 원리를 살펴봄으로써 Quick sort가 어떤 식으로 사용되고 활용되는지에 대해 이해해보는 시간을 가져보겠다.

Quick sort라고 하면 말 그대로 빠른 정렬이라는 의미를 가지고 있다. Quick sort가 빠르게 정렬된다는 것은 사실 복잡하지 않고 단순하고 반복적으로 정렬이 이루어지기 때문이다. 따라서 Quick sort는 Data Strucutre에서 Recursive Algorithm이라고도 불리는데, 반복적인 알고리즘이라는 의미를 가지고 있다. (한국에서도 이렇게 알려주는지는 모르겠다.) Quick sort에 대해서 한 줄로 이야기하자면 기준 값을 정하고 해당 기준값과 비교하여 데이터 값의 정렬이 이루어진다. 예를 들어, 0부터 4까지 숫자가 Random 하게 배열되어 있다고 가정했을 때 , 가운데 숫자가 2일 경우 2를 기준으로 앞과 뒤에 배치된 숫자의 크기를 비교해가면서 정렬이 이루어진다. 여기서 2라는 숫자와 앞의 숫자와 비교하고 또 2라는 숫자와 뒤의 숫자를 비교하는 과정이 반복적으로 발생하기 때문에 Quick sort를 Recursive Algorithm이라고 부르는 것이다. 아래의 그림을 보면 이해하기 훨씬 수월할 것이다.

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

 

Quick sort의 단계는 Piviot에 따라서 달라질 수 있다.

여기서 유의할 점은 위의 방식이 Quick sort의 모든 방식을 의미하는 것은 아니다. Quick sort에 대해서는 워낙 기본적이고 실제로 간단하지만 활용도가 높은 자료구조이다 보니 Quick sort에 대한 정보는 인터넷에서 쉽게 찾을 수 있다. 다만 영상이나 교육 자료를 찾아보다 보면 Quick sort가 한 가지 방법이 아닌 다양한 방법으로 정렬을 보여주고 있다. Quick sort는 기준값 즉 Pivot(한국말로는 피벗, 영어로는 피빗)를 어디에 잡느냐에 따라서 Quick sort가 이루어지는 단계의 차이가 발생한다. 한마디로 Quick sort는 기준값을 지정하고 양 옆의 숫자를 비교하고 이를 반복적으로 수행하여 정렬이 이루어진다는 개념은 동일하지만 기준값을 어디에 잡느냐에 따라서 Quick sort가 이루어지는 단계의 차이가 발생하다. 이러한 단계적 차이가 발생한다는 것은 같은 Quick sort를 사용할지라도 Pivot에 따라서 정렬되는 속도의 차이가 존재한다. 이를 평균 속도 값으로 O(n log n)라고 하며, Wrost case인 최악의 경우는 O(n^2)이라고 한다. (BIG-O 표기법)

 

Pivot이란?

Quick sort에서 Pivot(한국에서는 피벗, 미국에서는 피빗)은 쉽게 생각해서 기준값이라고 보며 된다. Pivot이라는 의미는 회전축, 중심점이라는 의미를 내포하고 있는데 Quick sort에서도 Pivot을 기준으로 Swap이 이루어진다는 점을 생각하면 이해하기가 훨씬 쉽다.

 

Quick sort의 장단점

다음 포스트에서 보다 더 구체적인 Quick sort에 대해서 다뤄보겠지만 Quick sort의 장점을 간략히 소개하자면 코드가 짧다는 것이다. (코드가 왜 짧은지에 대해서는 다음 포스트에서 살펴보도록 하겠다.) 반면에 Quick sort의 경우 Pivot에 따라서 처리 속도, 즉 Time complexity가 달라질 수 있기 때문에 이에 대한 보안점을 유의하여 Quick sort를 활용해야 한다.