[알고리즘] 1. 정렬

in 알고리즘




1. 정렬 (Sorting)

  • 배열 내 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘
  • 뒤부터 정렬된다.
  • 거품 정렬 (Bubble Sort) : bubbleSort_1(), bubbleSort_2(), bubbleSort_3(), bubbleSort()
  • 선택 정렬 (Selection Sort) : selectionSort()
  • 삽입 정렬(Insertion Sort) : insertionSort()
  • 병합 정렬 (Merge Sort) : mergeSort()
  • 퀵 정렬 (Quick Sort) : quickSort()
  • 공통 함수 : swap(), ascending(), descending()
  • O(n2) : 거품, 선택, 삽입 정렬
  • O(nlogN) : 병합, 퀵 정렬



2. 거품 정렬 (Bubble Sort)


버블

  • 서로 인접한 두 원소를 비교하면서 정렬하는 알고리즘
  • 평균 시간 복잡도 : O(n2)
  • 인접한 값 비교 > 큰 값 교환
  • index N 만큼 반복
  • N이 n-1 까지 실행


3. 거품 정렬 구현하기

let swap = function (arr, idx_1, idx_2) {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

// 정렬한 부분까지 계속 정렬함
let bubbleSort_1 = function (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
};

// 이미 정렬한 부분은 탐색 x
let bubbleSort_2 = function (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
};

// 123465 의 경우 최초1회만 정렬하면 되는데 계속 탐색한다.
// 아래 코드로 해결 가능
let bubbleSort_3 = function (arr) {
  let swapped;
  for (let i = 0; i < arr.length - 1; i++) {
    swapped = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        swapped = true;
      }
    }
    if (!swapped) break;
  }
};

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

let array = [...init_array];
bubbleSort_1(array);
console.log(array); //[ 1, 2, 3, 4, 5, 6 ]

let array2 = [...init_array];
bubbleSort_2(array2);
console.log(array2); //[ 1, 2, 3, 4, 5, 6 ]

let array3 = [...init_array];
bubbleSort_3(array3);
console.log(array3); //[ 1, 2, 3, 4, 5, 6 ]



4. 거품 정렬 고차함수화

let ascending = function (x, y) {
  return x > y;
};

let descending = function (x, y) {
  return x < y;
};

let bubbleSort = function (arr, compare) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (compare(arr[j], arr[j + 1])) {
        swap(arr, j, j + 1);
      }
    }
  }
};

// test code 공용화
let init_array = [6, 5, 1, 3, 2, 4];
let array;

let sorting = [bubbleSort];
let order = [ascending, descending];
for (let i = 0; i < sorting.length; i++) {
  for (let j = 0; j < order.length; j++) {
    console.log(sorting[i].name, order[j].name);

    array = [...init_array];
    sorting[i](array, order[j]);
    console.log(array);
  }
}

// bubbleSort ascending
// [ 1, 2, 3, 4, 5, 6 ]
// bubbleSort descending
// [ 6, 5, 4, 3, 2, 1 ]



5. 선택 정렬 (Selection Sort)


선택

  • 최솟값을 찾아 데이터 영역의 가장 앞으로 이동하는 방식을 반복하여 전체 데이터 영역을 정렬하는 알고리즘
  • 앞부터 정렬된다.
  • 평균 시간 복잡도 : O(n2)



6. 선택 정렬 구현하기

let swap = function (arr, idx_1, idx_2) {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

let ascending = function (x, y) {
  return x > y;
};

let descending = function (x, y) {
  return x < y;
};

let selectionSort = function (arr, compare) {
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (compare(arr[min], arr[j])) min = j;
    }
    swap(arr, i, min);
  }
};

// test code 공용화
let init_array = [6, 5, 1, 3, 2, 4];
let array;

let sorting = [selectionSort];
let order = [ascending, descending];
for (let i = 0; i < sorting.length; i++) {
  for (let j = 0; j < order.length; j++) {
    console.log(sorting[i].name, order[j].name);

    array = [...init_array];
    sorting[i](array, order[j]);
    console.log(array);
  }
}

// selectionSort ascending
// [ 1, 2, 3, 4, 5, 6 ]
// selectionSort descending
// [ 6, 5, 4, 3, 2, 1 ]



7. 삽입 정렬 (Insertion Sort)


삽입

  • 이미 정렬된 데이터 영역과 비교하면서, 자신의 위치를 찾아 요소를 삽입하며 정렬하는 알고리즘
  • 배열의 크기를 하나씩 늘려가며 정렬하는 것
  • 평균 시간 복잡도 : O(n2)



8. 삽입 정렬 구현하기

let insertionSort = function (arr, compare) {
    // 앞에 2개 먼저 선택해서 정렬
  for (let i = 1; i < arr.length; i++) {
      // 추가하는 요소를 tmp 에 임시저장
    let tmp = arr[i];
    let j;
    // 추가 요소 바로 앞(배열의 맨끝)부터 비교하면서 앞으로 감
    for (j = i - 1; j >= 0; j--) {
      arr[j + 1] = arr[j];
      if (compare(tmp, arr[j])) {
        break;
      }
    }
    arr[j + 1] = tmp;
  }
};

/ test code 공용화
let init_array = [6, 5, 1, 3, 2, 4];
let array;

let sorting = [insertionSort];
let order = [ascending, descending];
for (let i = 0; i < sorting.length; i++) {
  for (let j = 0; j < order.length; j++) {
    console.log(sorting[i].name, order[j].name);

    array = [...init_array];
    sorting[i](array, order[j]);
    console.log(array);
  }
}

// insertionSort ascending
// [ 1, 2, 3, 4, 5, 6 ]
// insertionSort descending
// [ 6, 5, 4, 3, 2, 1 ]



9. 병합 정렬 (Merge Sort)


병합

  • 하나의 배열을 두 개의 균등한 크기로 분할하고, 부분 정렬하며, 이를 다시 합하면서 전체를 정렬해가는 알고리즘
  • 평균 시간 복잡도 : O(nlogN)



10. 병합 정렬 구현하기

let mergeSort = function (arr, compare) {
  if (arr.length === 1) return arr;

  let m = (arr.length / 2).toFixed(0);
  let left = mergeSort(arr.slice(0, m), compare);
  let right = mergeSort(arr.slice(m), compare);

  let i = 0,
    j = 0,
    k = 0;
  while (i < left.length && j < right.length) {
    arr[k++] = compare(left[i], right[j]) ? right[j++] : left[i++];
  }
  while (i < left.length) arr[k++] = left[i++];
  while (j < right.length) arr[i++] = right[j++];

  return arr;
};


// test code 공용화
let init_array = [6, 5, 1, 3, 2, 4];
let array;

let sorting = [mergeSort];
let order = [ascending, descending];
for (let i = 0; i < sorting.length; i++) {
  for (let j = 0; j < order.length; j++) {
    console.log(sorting[i].name, order[j].name);

    array = [...init_array];
    sorting[i](array, order[j]);
    console.log(array);
  }
}

// mergeSort ascending
// [ 1, 2, 3, 4, 5, 6 ]
// mergeSort descending
// [ 6, 5, 4, 3, 2, 1 ]



11. 퀵 정렬 (Quick Sort) 🤔


퀵

  • 특정한 값(pivot)을 기준으로 큰 숫자와 작은 숫자를 분할하여 정렬하는 알고리즘
  • 평균 시간 복잡도 : O(nlogN)
  • 다양한 방식이 있지만 여기서는 qsort 방식



22. 퀵 정렬 구현하기

let quickSort = function (arr, compare, s = 0, e = arr.length - 1) {
  let start = s;
  let pivot = arr[e];

  for (let i = s; i <= e; i++) {
    if (compare(pivot, arr[i])) {
      swap(arr, start, i);
      start++;
    }
  }
  swap(arr, start, e);

  if (start - 1 > s) quickSort(arr, compare, s, start - 1);
  if (start + 1 < e) quickSort(arr, compare, start + 1, e);
};


// test code 공용화
let init_array = [6, 5, 1, 3, 2, 4];
let array;

let sorting = [mergeSort];
let order = [ascending, descending];
for (let i = 0; i < sorting.length; i++) {
  for (let j = 0; j < order.length; j++) {
    console.log(sorting[i].name, order[j].name);

    array = [...init_array];
    sorting[i](array, order[j]);
    console.log(array);
  }
}

// quickSort ascending
// [ 1, 2, 3, 4, 5, 6 ]
// quickSort descending
// [ 6, 5, 4, 3, 2, 1 ]



13 성능 측정

bubble_sort 1,2,3

function benchmark(arr, callback) {
  let start = Date.now();

  callback(arr);
  return Date.now() - start;
}

let init_array = []
let max = 30000;
for (let i = 0; i < max; i++) {
  init_array.push(Math.round(Math.random() * max));
}

let array = [...init_array]
console.log("bubbleSort_1: " + benchmark(array, bubbleSort_1) + "ms") //bubbleSort_1: 1977ms

array = [...init_array]
console.log("bubbleSort_2: " + benchmark(array, bubbleSort_2) + "ms") //bubbleSort_2: 1431ms

array = [...init_array]
console.log("bubbleSort_3: " + benchmark(array, bubbleSort_3) + "ms") //bubbleSort_3: 1391ms



나머지 정렬

 = [...init_array];
    console.log(
      sorting[i].name,
      order[j].name,
      benchmark(array, sorting[i], order[j]) + "ms"
    );
  }
}

// bubbleSort ascending 1410ms
// bubbleSort descending 4917ms
// selectionSort ascending 329ms
// selectionSort descending 2961ms
// insertionSort ascending 192ms
// insertionSort descending 1693ms
// mergeSort ascending 22ms
// mergeSort descending 24ms
// quickSort ascending 9ms
// quickSort descending 11ms
  • 내림차순이 실행 시간이 훨씬 오래 걸린다.