Algorithm - Bubble, Selection, Insertion Sort

Sort

Built-In JavaScript Sort

• built-in sort 메서드는 선택적인 comparator 함수를 인자로 받음
• comparator 함수를 사용해서 어떻게 정렬할 것인지 JavaScript에 알림
• comparator 함수는 반환값을 기준으로 요소 한 쌍의 정렬 순서를 정함
  • 음수를 반환한 경우, 첫 번째 요소가 두 번째 요소 이전에 옴
  • 양수를 반환한 경우, 두 번째 요소가 첫 번째 요소 이전에 옴
  • 0을 반환한 경우, 첫 번째 요소와 두 번째 요소가 같음

function numberCompare(num1, num2) {
  return num1 - num2;
}

[6, 4, 15, 10].sort(numberCompare); // [4, 6, 10, 15]

function numberCompare2(num1, num2) {
  return num2 - num1;
}

[6, 4, 15, 10].sort(numberCompare2); // [15, 10, 6, 4]

function compareByLen(str1, str2) {
  return str1.length - str2.length;
}

['a', 'abc', 'abcde', 'aa'].sort(compareByLen); // ['a', 'aa', 'abc', 'abcde']

Bubble Sort

• 두 값을 비교해서 더 큰 값이 뒤로 가도록 자리를 바꾸고(swap), 모든 값이 정렬될 때까지 반복하는 정렬
• 두 값의 자리를 바꾸는 코드 예시

// ES5
function swap(arr, idx1, idx2) {
  var temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

// ES2015
function swap(arr, idx1, idx2) {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

Bubble Sort function

• i에 배열의 마지막 요소을 할당하고 배열 첫 번째 요소까지 순회함
  • 안쪽 루프를 다 돌 때마다 배열의 끝에서부터 정렬되므로 정렬된 요소를 비교하지 않기 위해서 바깥쪽 루프를 배열의 끝에서부터 처음 순으로 순회함
• 배열의 첫 번째에서 i - 1까지 j라는 변수로 내부 순회함
  • 비교해야 하는 요소의 갯수가 i개일 때 i - 1번 비교하기 위해서 안쪽 루프 변수 j의 최대값은 i - 1임
• arr[j]가 arr[j+1]보다 크면, 두 값의 자리를 서로 교환함
• 정렬된 배열을 반환함

// ES5
function bubbleSort(arr){
  for(var i = arr.length; i > 0; i--){
    for(var j = 0; j < i - 1; j++){
      console.log(arr, arr[j], arr[j+1]);
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;         
      }
    }
  }
  return arr;
}

// ES2016
function bubbleSort(arr){
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
  for (var i = arr.length; i > 0; i--) {
    for (var j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, i + 1);
      }
    }
  }
  return arr;
}

• 배열에서 정렬해야 될 요소가 없을 때 탈출 조건문 넣기

// ES5
function bubbleSort(arr){
  var noSwaps;
  for (var i = arr.length; i > 0; i--) {
    var noSwaps = true;
    for (var j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        noSwaps = false;
      }
    }
    if (noSwaps) break;
  }
  return arr;
}

// ES2016
function bubbleSort(arr){
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
  let noSwaps;
  for (var i = arr.length; i > 0; i--) {
    noSwaps = true;
    for (var j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        noSwaps = false;
      }
    }
    if (noSwaps) break;
  }
  return arr;
}

Bubble Sort - Big O Notation

• Bubble Sort's Big O Notation
  • O(N) (nearly sorted) ~ O(N^2) (no sorted) => O(N^2)

Selection Sort

• bubble sort와 비슷하지만, 작은 값부터 정렬된다는 점이 다름
  • 배열의 모든 요소를 순회한 후 가장 작은 값을 가진 요소와 배열의 첫 번째 요소의 자리를 바꿈(swap)
  • 정렬된 요소 다음 번째 요소와 나머지 요소들을 비교해서 가장 작은 값을 가진 요소와 정렬된 요소 다음 번째 요소를 자리 바꿈
  • 모든 값이 정렬될 때까지 이 과정을 반복함

Selection Sort function

• 배열의 첫 번째 요소의 index를 최소값의 index로 저장함
• 저장된 최소값보다 더 작은 값을 가진 요소가 나올 때까지 최소값과 배열의 요소들과 비교함
• 더 작은 값을 가진 요소를 찾은 경우, 더 작은 값의 index를 저장하고 더 작은 값과 배열의 나머지 요소들을 비교함
• 최소값의 index가 첫 번째 요소의 index가 아닌 경우, 최소값과 첫 번째 요소의 자리를 바꿈
• 배열이 모두 정렬될 때까지 다음 요소와 이 과정을 반복함

// ES5
function selectionSort(arr){
  for (var i = 0; i < arr.length; i++) {
    var lowest = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j;
      }
    }
    if (i !== lowest) {
      var temp = arr[i];
      arr[i] = arr[lowest];
      arr[lowest] = temp;
    }
  }
  return arr;
}

// ES2015
function selectionSort(arr){
  const swap = (arr, idx1, idx2) => [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  for (var i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j;
      }
    }
    if (i !== lowest) swap(arr, i, lowest);
  }
  return arr;
}

Selection Sort - Big O Notation

• Selection Sort's Big O Notation : O(N^2)
• Bubble Sort는 순회할 때 마다 가장 큰 값의 요소를 찾을 때까지 계속 swap하는 반면에, Selection Sort는 순회할 때 한번만 swap함

Insertion Sort

• 한 번에 한 요소씩 정렬된 배열의 요소를 끝에서부터 비교해서 작은 값을 가진 요소 다음에 삽입하면서 정렬함

Insertion Sort function

• 배열의 첫 번째 요소는 정렬되어 있다고 가정하므로, 배열의 두 번째 요소를 선택하면서 시작함
• 정렬된 배열의 첫 번째 요소와 배열의 두 번째 요소를 비교해서 첫 번째 요소가 더 크다면 두 요소의 자리를 바꿈(swap)
• 다음 요소와 배열의 나머지 요소들을 비교함
  • 배열의 요소가 다음 요소보다 큰 경우, 배열의 요소를 뒤로 한 칸 이동시킴
  • 배열의 요소가 다음 요소보다 작은 경우, 다음 요소를 배열의 요소 바로 뒤로 이동시킴
• 배열이 정렬될 때까지 반복함

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

Insertion Sort - Big O Notation

• Insertion Sort's Big O Notation : O(N^2)
• Sort Cost : Good (almost ordered) ~ (random order) ~ Worst (reverse order)
• 실시간으로 받은 데이터를 정렬해야할 때 Insert Sort가 유용함

Compare Bubble, Insertion, Selection Sort

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)

• Best Case for Bubble, Insertion, Selection Sort

  • Bubble Sort : nearly sorted data,
  • Insertion Sort : nearly sorted data,
  • Selection Sort : need to sort data continuosly

• Space Complexity for for Bubble, Insertion, Selection Sort

  • 배열을 새로 만들지 않고 기존 배열에서 조작하므로 공간복잡도가 O(1)임