정렬 알고리즘 (Sorting algorithm)

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++;
}

// 정렬할 배열
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 ]

// 정렬할 배열
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;
}

// 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;
}