버블 정렬(Bubble Sort)

var arr = [4, 2, 3, 1, 5]

// 헬퍼 함수
// O^2
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

// 1. 버블 정렬
// O^2
function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      // len - i - 1인 이유는, 뒷부분은 이미 정렬이 된 상태이기 때문
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}

console.log(bubbleSort(arr))