효과적인 Sorting! 정렬별 특징 Javascript

 

버블 정렬 Bubble Sort

이미지 출처는 클릭!

for (let i = 0; i < array.length; i++) {
  let swap;
  for (let j = 0; j < array.length - 1 - i; j++) {
    if (array[j] > array[j + 1]) {
    // 인자 하나를 계속 데리고 다니면서 하나씩 비교하면서 맞는 자리에 앉혀준다.
    swap = array[j];
    array[j] = array[j + 1];
    array[j + 1] = swap;
   }
}

  버블 정렬은 인접한 값에 대해서 비교하면서 정렬을 하기 때문에 구현하기가 쉽습니다. 그래서 코드가 직관적이지만 시간복잡도가  O(n²)나 걸리기 때문에 보다 다른 효율적인 방법이 더 우선순위에 올라가게 됩니다.

# 이와 비슷하게 선택 정렬(Selection Sort)가 있으며, 비교하는 값이 더 작은 값을 만나는 경우 해당 값의 인덱스로 값을 바꾼 다음에 비교를 계속 돌리는 형태입니다. 탐색을 시작한 인덱스에 비교 후 최종적으로 결정된 값을 설정하기 때문에 버블 정렬보다는 비교 횟수가 줄어들지만 동일한 시간 복잡도를 가집니다.

 

퀵 정렬 Quick Sort

이미지 출처는 클릭!

const pivot = [array[0]]; // 보통 첫 인자를 피벗으로 선정해서 기준을 세운다고 합니다.
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
  if (array[i] < pivot) {
    left.push(array[i]);
   // 기준보다 작으면 왼쪽으로 
  } 
  else if (array[i] > pivot) {
    right.push(array[i]);
  // 기준보다 크면 오른쪽으로
  } 
  else {
    pivot.push(array[i]);
    // 아니면 피벗 배열에 넣고 나중엔 세가지 배열을 합친다.
  }
}

기준값(피벗)에 의해서 구별하는 정렬 방법으로 분할하는 과정에서 logN의 시간이 걸리게 되고 전체적으로는 NlogN의 시간 복잡도를 가진다. 하지만 최악의 경우에는 O(n²)의 시간이 걸릴 수 있습니다.

 

힙 정렬 Heap Sort

이미지 출처는 클릭!

트리 형태로 봤을 때, 정렬이 진행되는 과정

let arrLength;

function swapping(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function Root(input, i) {
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  let max = i;

  if(left < arrLength && input[left] > input[max]) {
    max = left;
  }
  if(right < arrLength && input[right] > input[max]) {
    max = right;
  }
  if (max != i) {
    swap(input, i, max);
    heapRoot(input, max);
  }
}

function heapSort(input) {
  arrLength = input.length;

  for (let i = Math.floor(arrLength / 2); i >= 0; i--) {
    heapRoot(input, i);
  }

  for (let i = input.length - 1; i > 0; i--) {
    swap(input, 0, i);
    arrLength--;

    heapRoot(input, 0);
  }
}

메모리를 추가적으로 필요로 하지 않으면서 항상 O(NlogN) 이라는 시간복잡도를 가지는 효율적인 정렬법이라고 볼 수 있습니다. 퀵 정렬과 마찬가지로 최악의 경우 시간이 오래걸린다는 단점이 있지만 힙 정렬의 경우 항상 O(NlogN) 으로 보장된다는 장점이 있습니다. 그리고 데이터 상태에 따라서 다른 정렬법에 비해서 오히려 느리게 걸린다는 경우도 있어서 안전성면에서는 다소 낮은 모습을 보인다고 합니다.