Sort

Bubble sort, Select sort, Insertion sort

Bubble Sort

• 인접한 두 요소를 비교, 정렬하는 알고리즘

시간 복잡도

• O(n^2)

장점

• 구현이 간단함

단점

• 시간 복잡도가 O(n^2)
• 비효율적

코드

let arr = [2, 4, 6, 5, 1, 3];

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

console.log(bubbleSort(arr));

---

Selection Sort

• 배열을 한번 훑고 가장 작은 수를 맨 앞에 오게 하는 정렬

시간 복잡도

• O(n^2)

코드

let arr = [2, 4, 6, 5, 1, 3];
function selectionSort(arr) {
  let min;
  for (let i = 0; i < arr.length - 1; i++) {
    min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) min = j;
    }
    if (i !== min) {
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }
  return arr;
}

console.log(selectionSort(arr));

Insertion Sort

• 1회전을 할 때마다 인덱스가 증가하며 해당 인덱스까지 요소들이 정렬
• 기준점 인덱스는 1
• 기준점 인덱스 전 요소들을 비교하는 정렬 방식

시간 복잡도

• O(n^2)

코드

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