삽입 정렬(Insertion Sort)

📌 삽입 정렬

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 최선의 경우는 O(n)의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2)의 시간복잡도를 갖게 된다.

👀 Example

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

insertionSort([2,1,9,76,4])

시간 복잡도

• Best: O(n)
• Worst: O(n^2)
• Average: O(n^2)