Sorting Algorithms_Selection/Insertion Sort

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스

Selection Sort 선택 정렬

Similar to bubble sort, but instead of first placing large values into sorted position, it places small values into sorted position

Selection Sort Pseudocode

• Store the first element as the smallest value you've seen so far.
• Compare this item to the next item in the array until you find a smaller number.
• If a smaller number is found, designate that smaller number to be the new "minimum" and continue until the end of the array.
• If the "minimum" is not the value (index) you initially began with, swap the two values.
• Repeat this with the next element until the array is sorted.

 

---

Insertion Sort 삽입 정렬

Builds up the sort by gradually creating a larger left half which is always sorted

Insertion Sort Pseudocode

• Start by picking the second element in the array
• Now compare the second element with the one before it and swap if necessary.
• Continue to the next element and if it is in the incorrect order, iterate through the sorted portion (i.e. the left side) to place the element in the correct place.
• Repeat until the array is sorted.

function insertionSort(arr) {
    for(var i = 1; i < arr.length; i++){
        let currentVal = arr[i];
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
            arr[j+1] = arr[j];
        }
        arr[j+1] = currentVal;
        console.log(arr);
    }
    return arr;
}

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

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      [array[j - 1], array[j]] = [array[j], array[j - 1]];
      j--;
    }
  }
  return array;
}

삽입 정렬이 유리한 다른 흥미로운 상황은,
온라인 알고리즘이라는 데이터가 있는 경우입니다. 데이터가 들어오는 대로 작동하는 알고리즘으로 새로운 데이터를 수신하므로 전체 배열을 한 번에 정렬할 필요가 없습니다. 어떤 숫자가 입력되더라도 필요한 위치에 놓을 수 있습니다. 라이브, 스트리밍 방식으로 들어온 데이터를 즉시 입력해야 하는 상황에 편리합니다.

---

Big O of Sorting Algorithms

Algorithm	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Bubble Sort	O(n)	O(n^2)	O(n^2)	O(1)
Insertion Sort	O(n)	O(n^2)	O(n^2)	O(1)
Selection Sort	O(n^2)	O(n^2)	O(n^2)	O(1)

 

Recap

• Sorting is fundamental!
• Bubble sort, selection sort, and insertion sort are all roughly equivalent
• All have average time complexities that are quadratic
• We can do better...but we need more complex algorithms!

 

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations