quick sort

Algorithm / 정렬 / Quick Sort (퀵 정렬)

퀵 정렬 function quickSort1(arr) { if (arr.length { [array[i], array[j]] = [array[j], array[i]]; }; let pivot = arr[start]; let swap_idx = start; // 마지막에 위치해야 할 인덱스 for (let i = start + 1; i arr[i]) { swap_idx++; swap(arr, swap_idx, i); } } swap(arr, start, swap_idx); return swap_idx; } function quickSort2(arr, left = 0, right = arr.length - 1) { if (left < right) {..

제코베 JS 100제 / 52 / quick sort

function quickSort(arr) { if (arr.length parseInt(n, 10)); console.log(quickSort(array)); 위의 코드에선 pivot을 배열의 가장 첫번째 값으로 잡았지만, 중간값으로 잡는게 좋다고 한다. quick sort는 정렬이 불필요한 배열이 들어와도 수행하게 되는데, 이 경우 최악의 경우로 O(n^2)의 시간 복잡도를 가지게 된다. 어떤 배열이 들어올지 미지수인 상태에서 quick sort를 구현하게 된다면, 그나마 최소나 최대값이 아닌 확률이 가장적은 중간값으로 pivot을 잡는것이다.