JavaScript/Algorithm

Sorting Algorithms_Selection/Insertion Sort

code10 2023. 4. 3. 00:21

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!