JavaScript 알고리즘 - 정렬(Sorting)

1. 선택 정렬

선택 정렬은 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법입니다. 앞으로 보내진 원소는 더이상 위치가 바뀌지 않습니다. 이러한 방법은 구현 난이도는 낮으나 비효율적인 정렬 알고리즘 중 하나입니다.

// 예시 코드 1
function solution(array) {
  for(let i = 0; i < array.length; i++) {
  	let minIndex = i;
    for(let j = i + 1; j < array.length; j++) {
    	if(array[minIndex] > array[j]) {
        	minIndex = j;
        }
    }
    let tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
  }
  return array
}

// 예시 코드 2
function solution1(arr) {
  let answer = [];
  let array = arr;
  // 원래 배열의 길이가 0이 될때까지
  while (array.length) {
    // array의 최소값을 answer에 push
    answer.push(Math.min(...array));
    // array의 최소값을 삭제
    for (let i = 0; i < array.length; i++) {
      if (array[i] === Math.min(...array)) {
        array.splice(i, 1);
        break;
      }
    }
  }
  return answer;
}

console.log(solution([5, 3, 4, 2, 1])); // [1, 2, 3, 4, 5]
console.log(solution1([5, 3, 4, 2, 1])); // [1, 2, 3, 4, 5]

2. 버블 정렬

버블 정렬은 인접한 두 원소를 확인하여 정렬이 안되어 있다면 서로 위치를 변경하여 정렬하는 방법입니다. 즉 한번의 단계가 수행되면 가장 큰 원소가 맨 뒤로 위치하게 됩니다. 선택 정렬과 유사하게 구현 난이도는 낮으나 시간 복잡도가 비효율적인 정렬 알고리즘 중 하나입니다.

// 예시 코드
function solution(array) {
	for(let i = array.length - 1; i > 0; i--) {
    	for(let j = 0; j < i; j++) {
        	if(array[j] > array[j+1]) {
              let tmp = array[j];
              array[j] = array[j + 1];
              array[j + 1] = tmp;
            }
        }
    }
  return array;
}

console.log(solution([5, 3, 4, 2, 1])); // [1, 2, 3, 4, 5]

3. 삽입 정렬

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법을 말합니다. 현재 원소가 삽입될 위치를 찾고 적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동하는 방식입니다. 시간 복잡도가 위의 두가지 정렬 방식과 비슷하게 비효율적이지만 처리속도는 상대적으로 더 빠르게 동작합니다.

function solution(arr) {
  for(let i = 1; i < arr.length; i++) {
    for(let j = i; j > 0; j--) {
      if(arr[j] < arr[j - 1]) {
        let tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
      } else break;
    }
  }
  return arr
}

console.log(solution([2, 1, 4, 3])); //[1, 2, 3, 4]

function solution(nums) {
  let n = nums.length;
  for (let i = 1; i < n; i++) {
    // 두번째 숫자부터 tmp에 할당
    let tmp = nums[i];
    let j;
    for (j = i - 1; j >= 0; j--) {
      // 앞에 숫자랑 비교 후 앞에 숫자가 작을때까지 비교해주기 앞에 숫자가 더 작다면 break
      if (nums[j] > tmp) nums[j + 1] = nums[j];
      else break;
    }
    nums[j + 1] = tmp;
  }
  return nums;
}

console.log(solution([2, 1, 4, 3])); //[1, 2, 3, 4]

4. 병합 정렬

병합 정렬은 위의 세가지 정렬 방식과 비교했을때 상대적으로 효율적으로 동작하는 정렬 알고리즘 입니다. 병합 정렬은 전형적인 분할 정복(divide and conquer) 알고리즘 입니다. 분할 정복은 일반적으로 재귀함수를 이용하여 구현하고, 더 이상 쪼갤 수 없는 크기가 될 때까지 계속해서 분할합니다. 분할 정복의 단점으로는 재귀 함수를 사용해 함수 호출 횟수가 많이 발생하고 이는 오버헤드로 이어집니다.

병합 정렬의 동작 방식은 우선 정렬할 배열을 부분 배열로 분할하고(분할) 부분 배열을 정렬합니다.(정복) 정렬된 부분 배열을 다시 하나의 배열로 병합합니다.(조합)

function merge(left, right) {
  const sortedArr = [];
  while (left.length && right.length) {
    //left[0]이 더작을 경우 같을때는 누가 먼저 들어가도 상관X
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  //left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
  //비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여줌
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const boundary = Math.ceil(arr.length / 2);
  //slice로 해주기 때문에 원본 arr은 손상 없음
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
  //요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
  //차근차근 merge(정렬해서 합치기)해주면 됨
  return merge(mergeSort(left), mergeSort(right));
}

const arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);
console.log(sortedArray); //[1, 2, 3, 4, 5, 6, 7]