삽입 정렬

삽입 정렬에 대해 알아봅니다.

삽입 정렬

 

삽입 정렬

 

1. 삽입 정렬이란 무엇이고, 어떻게 이뤄지는가?

2. 코드로 살펴보기

 

1. 삽입 정렬이란 무엇이고, 어떻게 이뤄지는가?

 정렬된 요소를 왼쪽으로, 정렬 되지 않은 요소는 오른쪽에 있다고 가정한다. 오른쪽에서 정렬이 되지 않은 요소를 가져와 이미 정렬된 요소들과 비교하여 적절한 위치에 삽입한다.
 이중 반복문을 사용하며, 시간 복잡도는 항상 n^2이다. 따라서 배열의 길이가 늘어날수록 시간이 급격히 증가한다.

2. 코드로 살펴보기

function insertionSort(arr) {
  const len = arr.length;

  for (let i = 1; i < len; i++) {
  // 인덱스 0 요소는 이미 왼쪽에서 정렬되어 있다고 가정한다.
  
    const current = arr[i];
    // 이번 회차에서 정렬하고차 하는 요소

    let j = i - 1;
    // 이미 정렬된 요소의 가장 오른쪽부터 비교를 시작한다.

    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
      // 현재 비교하는 수가 정렬 요소의 수보다 작을 때, 정렬된 요소를 오른쪽으로 한칸 땡긴다.
      // 그리고 왼쪽 요소와 비교를 한번 더 진행한다.
    }

    arr[j + 1] = current;
    // 정렬된 요소 중에서 더 작은 수가 없을 경우, 현재 요소를 정렬된 요소의 인덱스로 집어 넣는다.
    
  }

  return arr;
}