정렬 알고리즘

퀵 정렬

• 중심축을 정하고
• 그 중심축을 기준으로 작으면 front, 크면 rear에 배치
• 재귀적으로 front와 rear를 각각 반복
• front와 rear의 길이가 1이 될 때까지(크기가 작아 나눌 수 없을 때까지) 반복하면 정렬이 완성됨 -> 탈출 조건

const quickSort = function (arr, callback = (n) => n) {
  // 이 부분이 재귀 종료 조건(탈출 조건)
  if (arr.length <= 1) { return arr; }
  
  // 기준점은 [0] 또는 (arr.length-1) 또는 (arr.length/2)
  let mid = arr[0]; // 기준점을 잡음
  let front = [];
  let rear = [];
  
  // 기준점을 [0]으로 잡았으므로, 1번부터 시작
  for (let i = 1; i < arr.length; i++) {
    if (callback(arr[i]) >= callback(mid)) {
      rear.push(arr[i]);
    } else {
      front.push(arr[i]);
    }
  }
  
  // 재귀로 front와 rear를 돌려준다
  const frontSort = quickSort(front, callback);
  const rearSort = quickSort(rear, callback);
  
  // 재귀로 돌린 결과를 합쳐서 리턴한다
  return [...frontSort, mid, ...rearSort];
}

합병 정렬(병합 정렬, merge sort)

• 분할
• 병합

계수 정렬(counting sort)

링크텍스트

기수 정렬(radix sort)

링크텍스트

• 각 자리수 정렬을 할 때에 계수 정렬을 이용한다