[AL] 삽입 정렬 (Insertion Sort), 선택 정렬(Selection Sort) - JavaScript

JMinkyoung·2022년 3월 28일

Algorithm

목록 보기

10/10

Insertion Sort 란

Insertion Sort(삽입 정렬)란 배열의 두번째 값 부터 시작하여 그 왼쪽의 값들과 비교하여 삽입할 위치를 결정하는 정렬 알고리즘이다.
배열의 모든 값들을 왼쪽에서부터 차례대로 이미 정렬된 값들과 비교하여 자신의 위치를 찾아서 삽입하는 과정을 거쳐서 정렬하게 된다.

다시 말해서 index=2의 값은 index=0,1값과 비교하고, index=3의 값은 index=0,1,2값과 비교하고 자신의 위치를 찾아 해당 index에 자신을 삽입하게 된다.

Insertion Sort 코드

const insertionSort = (arr) => {
  for(let i=1; i<arr.length; i++){	// 두번째 값 부터 비교 시작
  	let cur = arr[i];	// 기준 값을 비교를 위해 따로 빼놓음
    let left = i-1;
    while(left>=0 && arr[left] > cur){  // 왼쪽 값들과 비교 진행
      arr[left+1] = arr[left];
      arr[left] = cur;
      left--;
    }
  }
  return arr;
}

insertionSort([3,5,2,1,8,4]);
// [1, 2, 3, 4, 5, 8]

Insertion Sort 장단점

장점
- 중복된 값은 위치를 비교하지 않는 stable 정렬
- 대부분의 값이 정렬되어 있는 경우에는 효율적이다.
단점
- 데이터 값이 많으면 성능이 크게 떨어진다.
- 많은 데이터 이동이 발생한다.

Insertion Sort 시간 복잡도

Worst	Best	Avg
$n^2$ (역순으로 정렬되어 있는 경우)	$n$ (이동 없이 한번의 비교만 이루어짐)	$n^2$

Selection Sort 란

사진 출처

Selection Sort(선택 정렬)란 배열의 첫번째 값을 두번째 값부터 마지막 값까지 전부 비교하여 가장 작은 값을 첫번째 위치에 옮겨 놓고, 두번째 값을 세번째 값부터 마지막 값까지 전부 비교하여 가장 작은값을 두번째 위치에 옮겨 놓는다. 이 과정을 반복하여 배열을 정렬하는 알고리즘이다.

Selection Sort 코드

const selectionSort = (arr) => {
  for(let i=0; i<arr.length; i++){
    let minIdx = i;
    for(let j=i+1; j<arr.length; j++){ // 해당 사이클에서 최소값 찾음
      if(arr[minIdx]>arr[j]){
      	minIdx = j;
      }
    }
    // 초기에 설정한 index가 아니라면, 즉 최소값이 발견 되었다면 swap
    if(minIdx !== i) [arr[minIdx], arr[i]] = [arr[i], arr[minIdx]];
  }
  return arr;
}

selectionSort([3,5,2,1,8,4]);
// [1, 2, 3, 4, 5, 8]