삽입 정렬, 병합 정렬, 퀵 정렬

Pien·2022년 12월 4일

Algorithm

목록 보기

1/4

삽입 정렬

삽입 정렬은 단순 정렬 알고리즘으로 요소를 하나씩 취합한 다음 올바른 위치에 삽입하는 알고리즘이다.
삽입 배열의 0번째 인덱스를 원본 배열의 값과 비교해 0번째 인덱스 보다 큰 값이 나오면 그 앞 인덱스에 0번째 인덱스를 집어 넣는 방식이다.

function solution(sortArr, value){
  for(let i = 0; i<sortArr.length; i++){
    if(value < sortArr[i]){
      return i
    }
  }
  return sortArr.length
}

function sortSolution(arr) {
  let sortArr = [];
  
  while(arr.length != 0){
    let value = arr.shift();
    let index = solution(sortArr, value);
    sortArr.splice(index,0,value);
  }
  return sortArr
}
const arr = [1,3,2,4,5,6,1,9,8]
sortSolution(arr)
console.log(arr) //[ 1, 1, 2, 3, 4, 5, 6, 8, 9 ]

sortSolution 함수에서 새로운 배열을 선언하고, 기존 배열에서 shift() 메서드를 통해 하나씩 추출해 새로운 배열을 순회 하며 값을 비교 한다. 새로운 배열의 값이 추출 한 값보다 클 경우 새로운 배열의 값 앞 자리에 splice() 를 통해 추출한 값을 추가 한다.

장점

알고리즘이 단순하다.
배열이 정렬되어 있을 수록 속도가 빠르다.
안정 정렬이다. ( 중복된 값의 순서를 보장해 준다. )

단점

배열의 길이가 길수록 효율이 떨어진다.

병합 정렬

병합정렬은 배열의 길이가 1이 될 때 까지 분해 한 뒤, 재귀 함수를 통해 비교, 정렬을 결과 값이 나올 때 까지 반복 하는 알고리즘 이다.
배열의 길이가 1이 될 때 까지 재귀 함수를 실행 시키고, 그 뒤에 함수를 조립해 나가는 방법으로 작동한다.

function merge(left, right){
  let result = [];

  while (left.length && right.length){
    if (left[0] < right[0]){
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

function mergeSort(arr){
  if (arr.length <= 1){
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  return merge(mergeSort(left), mergeSort(right));
}

const arr = ["주황버섯", "슬라임", "파란버섯", "와일드보어", "스텀프", "강아지", "머쉬맘", "화이트팽"];
console.log(mergeSort(arr));
//[ '강아지', '머쉬맘', '스텀프', '슬라임', '와일드보어', '주황버섯', '파란버섯', '화이트팽' ]

병합정렬은 재귀함수를 2개를 같이 사용한다.
mergeSort 함수를 실행시키면 결과 값으로 merge 함수를 실행 시키는데, 인자가 mergeSort 함수다.
인자가 현재 함수를 가리키고 있기 때문에 재귀 함수가 실행 되며, 콜 스택이 쌓인다.
콜 스택은 mergeSort 함수의 탈출 조건인 배열의 길이가 1이하를 만족 할 때까지 쌓이며, 탈출 조건을 만족하면 더 이상 콜 스택이 쌓이지 않고 실행되기 시작한다.
merge 함수는 left, right 두 배열의 첫 번째 값을 비교해 더 낮은 값을 새로운 배열에 추가 한 뒤, 기존 배열에서 해당 값을 삭제 한다.
이렇게 콜 스택을 거슬러 올라가며, 재귀 함수의 실행이 모두 종료 됐을 경우, 우리는 정렬된 배열의 값을 얻을 수 있다.

장점

안정 정렬이다.
속도가 빠르다.

퀵 정렬

퀵 정렬은 분할 정복 방법을 통해 배열을 정렬 한다.
하나의 기준점을 정한 뒤, 기준점 보다 작은 값과 기준점 보다 큰 값 두가지 리스트를 나눈다.
위 방식을 재귀함수로 각자의 리스트의 길이가 1이나 0이 될 때 까지 반복한다.

function quickSort(arr){
    if (arr.length <= 1){
      return arr;
    }

    const pivot = arr[0]; //기준점
    const left = [];
    const right = [];

    for (let i=1; i<arr.length; i++){
      if(arr[i] < pivot){
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

const arr = ["주황버섯", "슬라임", "파란버섯", "와일드보어", "스텀프", "강아지", "머쉬맘", "화이트팽"];
console.log(quickSort(arr));
//[ '강아지', '머쉬맘', '스텀프', '슬라임', '와일드보어', '주황버섯', '파란버섯', '화이트팽' ]

배열에서 0번째 인덱스의 값을 기준점으로 잡고, 기준점 보다 작은 값은 left 배열에 기준점 보다 큰 값은 right 배열에 담아준다.
리턴 값은 재귀 함수를 통해 실행하게 되는데, 병합 정렬과 같이 배열의 길이가 1 이하를 만족 할 때 까지 콜 스택이 쌓이고, 배열의 길이가 1이하인 배열만 남았을 경우 실행 되어 결과 값을 합쳐 나가 정렬을 완성 시킨다.