정렬 알고리즘 (Sorting algorithm)

정렬 알고리즘에서 정렬은 바꾸어 나열하는 것을 의미합니다.
즉, 데이터를 큰 순서 또는 작은 순서로 바꾸어 나열하는 알고리즘입니다.
정렬을 영어로 표현하면 소트(Sort)이므로 소트 알고리즘이라고도 합니다.
정렬에는 작은 순서로 정렬하는 오름차순과 큰 순서로 정렬하는 내림차순이 있습니다.

앞서 탐색 알고리즘 부분에서도 언급했지만, 검색 엔진은 인터넷상에 있는 대량의 데이터 중에서
알고 싶은 정보가 게재되어 있는 웹 페이지를 탐색해 주는 프로그램입니다.
하지만 해당하는 웹 페이지가 수만에서 수십만 페이지나 발견되는 경우 또한 흔합니다.
따라서 이를 모두 읽는 것은 불가능합니다.
검색 엔진은 발견된 웹 페이지를 중요한 정보가 실려 있을 것 같은 순서대로 정렬하여 우리에게 제시해 줍니다.
대량의 정보를 알기 쉽게 정렬함으로써 더 사용하기 쉬워지는 것입니다.

정렬 알고리즘중 유명한 것이 4가지가 있는데 다음과 같습니다.

1. 단순 선택법 : 선택 정렬 (Selection Sort)
2. 단순 교환법 : 버블 정렬 (Bubble Sort)
3. 단순 산입법 : 삽입 정렬 (Insertion Sort)
4. 퀵 정렬 (Quick Sort)

단순 선택법 : 선택 정렬 (Selection Sort)

단순 선택법은 정렬되지 않은 데이터 중 가장 작은 데이터를 선택하여
맨 앞부터 순서대로 정렬해 나가는 알고리즘입니다.
선택 정렬 또는 단순히 선택법이라고 합니다.

let exploreIndex = 0;
let exploreArray = [];
const exampleArray = [12, 13, 11, 8, 10, 3, 1, 9];

// 배열을 다 정렬할떄까지 라운드 반복
while (exploreIndex !== exampleArray.length) {
  // 정렬을 할때마다 다 돌면서 할 필요는 없으니 필요한 부분만 복사
  exploreArray = exampleArray.slice(exploreIndex);
  // 제일 먼저 가장 작은 데이터를 선택한다.
  // (편의상 Math.min.apply 사용, 선형 탐색을 하든, 이진 탐색을 하든 찾으면 된다.)
  const minValue = Math.min.apply(null, exploreArray);
  // 작은 데이터가 있는 저장 공간을 찾은뒤
  const minValueIndex = exploreArray.findIndex(item => item === minValue);
  // 쉽게말해 최소값인데 더 뒤에 위치해 있다면
  if (minValueIndex != exploreIndex) {
    // 바꾸기
    // 데이터를 바꾸기 위해서는 한가지 저장공간이 더 필요하여 선언
    // exampleArray[exploreIndex]가 현재 라운드에서는 제일 작은 수가 위치해야 하는 곳이므로,
    // 기존에 있는 데이터 복사
    let tempDataStore = exampleArray[exploreIndex];
    // 복사해놨으니 해당 라운드 최저값을 현재 라운드에서 제일 작은 수가 위치해야 하는 곳이랑 교환
    exampleArray.splice(exploreIndex, 1, exploreArray[minValueIndex]);
    // 저장해놓은 데이터를 원래 최저값이 있던 곳으로 교환
    exampleArray.splice(minValueIndex + exploreIndex, 1, tempDataStore);
    // 저장소 초기화
    tempDataStore = null;
  }
  // 무한루프 방지 및 다음 라운드 진행
  exploreIndex++;
}

단순 선택법에 있어서 알고리즘의 핵시이 되고 있는 두 가지 처리는
탐색 범위의 최솟값 찾기라는 처리와 탐색 범위의 최솟값과 맨 앞의 데이터 교환하기라는 처리입니다.

구현이 쉽지만 처리 속도는 느리기 때문에 데이터가 많은 경우의 정렬에는 적합하지 않습니다.
선택 정렬의 빅오 표기법은 O(n2)입니다.
지수 알고리즘이기 때문에 데이터가 적을 경우에 사용합니다.

지수는 O(n2), 계승은 O(n!)

단순 교환법 : 버블 정렬 (Bubble Sort)

단순 교환법은 인접한 데이터를 교환하는 처리를 반복하여,
최종적으로는 모든 데이터를 오름차순 또는 내림차순으로 정렬하는 알고리즘입니다.

단순 교환법의 정렬 처리는 단순합니다.
오름차순으로 정렬하려면 뒤부터 비교하여 앞으로 오도록 교환하는 과정을 반복하면 되고,
내림차순의 경우는 이와 반대로 진행됩니다.

// 정렬할 배열
let exampleArray = [5, 3, 4, 1, 2];
// 정렬 완료한 인덱스를 표기할 숫자타입의 변수
let sortTargetIndex = 0;

// 정렬할 배열을 다 정렬완료 할때까지
while (sortTargetIndex < exampleArray.length - 1) {
  // 마지막 인덱스를 표시할 숫자타입의 변수
  let lastIndex = exampleArray.length - 1;
  // 마지막 인덱스를 정렬완료 할 때까지
  while (lastIndex > sortTargetIndex) {
    // 만약 오른쪽의 숫자보다 왼쪽의 숫자가 크다면
    if (!(exampleArray[lastIndex - 1] < exampleArray[lastIndex])) {
      // 교환해준다.
      let tempDataStore = exampleArray[lastIndex - 1];
      exampleArray.splice(lastIndex - 1, 1, exampleArray[lastIndex]);
      exampleArray.splice(lastIndex, 1, tempDataStore);
      tempDataStore = null;
    }
    // 교환했으니까 다음칸으로 넘어가기
    lastIndex--;
  }
  // 하나 완료했으니까 다음거 또 정렬하기
  sortTargetIndex++;
}

// => [ 1, 2, 3, 4, 5 ]

// 보다 직관적으로 이해하기 위해 과정을 console로 찍어보면

// exampleArray[lastIndex]인 2보다
// exampleArray[lastIndex-1]인 1이 작아서
// 정렬할 필요가 없으니 lastIndex--;로 패스
// [ 5, 3, 4, 1, 2 ]

// exampleArray[lastIndex]인 1보다
// exampleArray[lastIndex-1]인 4가 크기에
// 교환
// [ 5, 3, 4, 1, 2 ] => [ 5, 3, 1, 4, 2 ]

// exampleArray[lastIndex]인 1보다
// exampleArray[lastIndex-1]인 3이 크기에
// 교환
// [ 5, 3, 1, 4, 2 ] => [ 5, 1, 3, 4, 2 ]

// exampleArray[lastIndex]인 1보다
// exampleArray[lastIndex-1]인 5가 크기에
// 교환
// [ 5, 1, 3, 4, 2 ] => [ 1, 5, 3, 4, 2 ]

// lastIndex(0) === sortFinishIndex(0)으로
// 한 사이클 검사완료 하였으니
// sortTargetIndex를 0에서 1로 변경 (sortTargetIndex++;)
// [ 1, 5, 3, 4, 2 ]

// 이후는 반복..
// [ 1, 5, 3, 2, 4 ]
// [ 1, 5, 2, 3, 4 ]
// [ 1, 2, 5, 3, 4 ]
// [ 1, 2, 5, 3, 4 ]
// [ 1, 2, 3, 5, 4 ]

// 정렬 끝
// [ 1, 2, 3, 4, 5 ]

단순 교환법 자체는 이해하기 쉽지만,
실행속도가 보다시피 느리기 때문에,
대량의 데이터 정렬에 적합하지 않습니다.

단순 교환법, 즉 버블 정렬의 시간복잡도는 빅오표기로 O(n2)로 나타낼 수 있습니다.

단순 삽입법 : 삽입 정렬 (Insertion Sort)

삽입이라는 이름 그대로 요소를 하나씩 차례대로 올바른 위치에 삽입해나감으로써
최종적으로는 전체를 오름차순 또는 내림차순으로 정렬하는 알고리즘입니다.
이 것을 삽입 정렬, 기본 삽입법 또는 단순히 삽입법이라고도 합니다.

단순 삽입법은 단순 교환법(버블 정렬)과 같이 정렬 알고리즘 중에서는
비교적 간단한 알고리즘에 속합니다. 단순 교환법과 마찬가지로 정렬 속도는 빠르지 않지만
정렬을 하기 전에 데이터가 어느 정도 오름차순 또는 내림차순으로 되어 있으면
빠른 처리를 기대할 수 있습니다.

// 정렬할 배열
let exampleArray = [5, 3, 4, 1, 2];
// 데이터를 잠시 보관할 변수
let tempStore = null;

// 삽입 정렬의 이미 한개는 정렬되었다고 전제조건을 갖는다.
// 그렇지 않으면 비교할 대상이 없기 때문이다.
// 그래서 0이 아닌 1부터 시작을 한다.
// 0은 이미 정렬된 것!
// 정렬된 첫번째 칸을 제외하고 나머지를 순회하면서
for (let i = 1; i < exampleArray.length; i++) {
  // 비교의 대상의 값을 미리 임시 저장해놓는다.
  tempStore = exampleArray[i];
  // 또한 비교 대상의 인덱스도 저장해 놓는다.
  let targetIndex = i;
  // 0은 정렬되었으니까 0되면 종료
  // 비교 대상보다 정렬된 값이 크면
  while (targetIndex > 0 && exampleArray[targetIndex - 1] > tempStore) {
    // 정렬된 값을 비교 대상의 자리로 보낸다.
    exampleArray[targetIndex] = exampleArray[targetIndex - 1];
    // 한칸씩 왼쪽으로 비교대상 좁히기
    targetIndex--;
  }
  // 비교 대상보다 정렬된 값이 작거나 같으면 그대로 위치
  exampleArray[targetIndex] = tempStore;
}

단순 삽입법의 경우 단순이라는 이름이 붙어 있긴 하지만, 꽤 복잡한 느낌이 듭니다.
단순 삽입법은 요소를 하나씩 차례대로 올바른 위치에 삽입해 나감으로써
전체를 오름차순 또는 내림차순으로 정렬하는 알고리즘입니다.
정렬의 실행 속도는 그다지 빠르지 않기 때문에 데이터가 많은 경우에는 적합하지 않지만,
정렬을 하기 전에 데이터가 어느 정도 오름차순 또는 내림차순으로 되어 있으면
고속 처리를 기대할 수 있습니다.

위에서 알아본 3가지 중에서는 단순 삽입법이 평균적으로 가장 속도가 빠르다고 알려져 있습니다.
하지만 환경, 코딩, 데이터에 따라서 좌우되기 때문에 엄밀하게 보면
모든 것들 중에서 가장 빠르다고는 말할 수 없습니다.

단순 삽입법(삽입 정렬)의 빅오 표기법은 for loop 혹은
while loop를 2중첩으로 구현되어 O(n2)입니다.
공간 복잡도는 O(n)입니다.

퀵 정렬 : 퀵 소트 (Quick Sort)

퀵 정렬은 이름에서도 알 수 있듯이, 처리 속도가 가장 빠른 정렬 알고리즘입니다.
(진짜 재수가 나쁘지 않으면 말입니다..)
이 정렬은 대량의 데이터를 정렬할 때 자주 사용됩니다. 유명한 정렬 알고리즘 중에서도
실제로 사용되는 빈도가 높은 가장 중요한 알고리즘이기도 합니다.

퀵 정렬은 기준값을 선택한 후 그보다 작은 데이터 그룹과 큰 데이터 그룹으로 나눈다라는 처리를
반복 수행하여 데이터를 정렬하는 알고리즘입니다.
퀵 정렬의 처리를 보다 세분화해보면 다음과 같습니다.

1. 기준값을 경계로 대이터를 대소로 나누는 처리
2. 나눈 데이터에 대해 반복적으로 똑같은 작업 실행하기

// Not In Place 방법
function quickSort(array) {
  if (array.length < 2) {
    return array;
  }

  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]);
    }
  }

  return quickSort(left).concat(pivot, quickSort(right));
}

quickSort([5, 3, 7, 1, 9]);

/* ################################################## */

// Not In Place 방법

function quickSort(array, left = 0, right = array.length - 1) {
  // 빈배열이면 리턴
  if (left >= right) {
    return;
  }

  // 가운데 인덱스 구해서
  const mid = Math.floor((left + right) / 2);
  // 가운데를 기준으로 잡는다. (가운데를 기준으로 잡는게 좋다.)
  const pivot = array[mid];
  const partition = divide(array, left, right, pivot);

  quickSort(array, left, partition - 1);
  quickSort(array, partition, right);

  function divide(array, left, right, pivot) {
    console.log(
      `array: ${array}, left: ${array[left]}, pivot: ${pivot}, right: ${array[right]}`
    );

    while (left <= right) {
      while (array[left] < pivot) {
        left++;
      }

      while (array[right] > pivot) {
        right--;
      }

      if (left <= right) {
        let swap = array[left];
        array[left] = array[right];
        array[right] = swap;
        left++;
        right--;
      }
    }

    return left;
  }

  return array;
}

퀵정렬은

장점은 머지 소트보다 평균 2배이상 빠릅니다.
(진짜 재수가 나쁘지 않으면요..)
재수가 없을 확률이 희박합니다.

단점은 재수가 진짜 없으면, 느립니다. (물론 극복가능합니다.)
또, 같은 숫자들을 정렬할 경우 순서가 섞일 수 있습니다.
(순서가 중요한 경우 고려해봐야 합니다.)

시간 복잡도는 O(nlogn)이며, 최악의 시나리오는 O(n^2)입니다.
앞서 말씀드린 재수가 없는 경우이며, 이미 정렬된 배열을 첫번째 원소를 기준으로 하여
퀵정렬하는게 제일 Worst 시나리오입니다.