Quick Sort

오랜만에 알고리즘 문제를 풀게 되어서 기쁘게 생각한다. 꾸준히 해야하는데 생각보다 쉽지 않다.

 

 

Quick Sort 란

 

• Charles Antony Richard Hoare 가 고안한 정렬 알고리즘이다.
• 퀵 정렬은 최악의 경우엔 O(n^2)의 시간복잡도를 가지지만 평균적으로 매우 빠른 수행 시간(O(n log n)을 자랑한다.
• 매 단계에서 적어도 1개의 원소가 자기 자리를 찾기 때문에 이후 정렬 갯수가 줄어든다.
• 이 때문에 퀵 정렬은 다른 O 알고리즘에 비해 훨씬 빠르게 동작한다. => quick sort 라는 이름의 기원!!
• 원소들 중 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기와는 달라질 수 있어 불안전 정렬에 속한다.

 

 

---

알고리즘

 : divide and conquer 분할 정복을 통해 리스트를 정렬한다.

 

1. 리스트 가운데서 하나의 원소를 고르고 이를 pivot 이라고 한다.

2. 피벗보다 작은 원소들은 피벗의 왼쪽에, 큰 원소들은 피벗의 오른쪽에 가도록 피벗을 기준으로 리스트를 둘로 나눈다. (divide)

3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 과정을 반복한다.

    (탈출 조건 : 리스트의 크기가 0이나 1이 될 때까지)

 

재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소는 자리를 찾기 때문에 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

 

 

---

코드 구현

 

문제 : 정수를 요소로 갖는 배열을 입력 받아 오름차순으로 정렬하여 리턴해야 한다. 

조건 : 퀵 정렬을 구현해야 하며 arr.sort 사용은 금지된다.

 

pseudocode

1. 먼저, 배열의 길이가 1과 같거나 작게 될 경우 배열을 바로 리턴한다.

2. 리스트 가운데 하나의 원소를 고르고 pivot 이라고 한다. : 첫번째 인덱스를 pivot으로 정했다.

3. 배열 안에서 pivot을 제외한 모든 요소를 탐색해서 pivot보다 작으면 left, 크면 right라는 배열에 넣는다.

        -> let left = []; let right = [];

        -> 이 과정은 인덱스가 arr.length보다 작을 때까지 반복한다.

4. left와 right에 값이 모두 넣어졌으면 각각의 배열에 대해 quickSort를 재귀하도록 해서 다시 정렬한다.

5. left, pivot, right를 합쳐서 리턴한다.

 

 

const quickSort = function(arr) {
  if(arr.length <= 1) {
    return arr;
  }
  
  let pivot = arr[0];
  let left = [];
  let right = [];
  
  for(let i = 1; i < arr.length; i++){
    if(arr[i] <=pivot) {
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
    
  let leftSorted = quickSort(left);
  let rightSorted = quickSort(right);
  
  return [...leftSorted, pivot, ...rightSorted]
}