차이를 비교하고 이해해야 한다.
bubble sort, insertion sort, selection sort (merge sort 빼고)
점진적으로 본인의 위치를 찾아간다. 위로 뽀글뽀글 🧼
반복 순회하면서 왼쪽과 오른쪽을 바꿔간다.
length - 1 만큼 순회한다. 그치만 장담할 수 없다.
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(n^2) | O(n) | O(n^2) | O(1) |
(셀병합도 html도 먹히지 않는다.. 😢)
Average, Worth O(n^2): 왼쪽에서 오른쪽으로 순회 하면서 총 횟수는 n번이다.
n번 순회가 끝나기전에 sorting이 완료 되었다 하여도 한번도 순회를 해야 순회를 끝내야하는지를 파악한다.
function bubbleSort (arr) {
for (let i = 0; i < arr.length; i++) {
let isSwap = false;
for (let j = 1; j < arr.length; j++) {
if (arr[j - 1] > arr[j]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
isSwap = true;
}
}
if (!isSwap) return arr;
}
return arr;
}
console.log(bubbleSort([2,4,6,1,2,5]));
isSwap
으로 Best케이스일때의 O(n)을 구현
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
es6 Destructuring Assignment 사용
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(n^2) | O(n) | O(n^2) | O(1) |
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j;
for (j = i - 1; j >= 0 && arr[j] > key; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = key;
}
return arr;
}
console.log(insertionSort([1,5,6,2,6,7]));
왼쪽 -> 오른쪽까지 순회한다.
가장 작은 수를 찾는 순회이다.
자리를 기준으로 정렬한다.
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(n^2) | O(n^2) | O(n^2) | O(1) |
function selectionSort (arr) {
for (let i = 0; i < arr.length - 1; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if(arr[min] > arr[j]) min = j;
}
if(min !== i) [arr[min], arr[i]] = [arr[i], arr[min]];
}
return arr;
}
console.log(selectionSort([5,3,7,4,1,7]));
1. 범위를 잡는다.
2. 기준이 되는 원소(pivot)를 선택한다.
첫번째 원소
중간 원소
랜덤 원소
마지막 원소
3. 범위 내에서 pivot보다 작은 수와 큰 수를 정렬한다.
4. pivot은 중간으로 위치한다.
5. 모두 정렬될 때까지 반복된다.
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(nlog(n)) | O(nlog(n)) | O(n^2) | O(log(n)) |
Best: 항상 중간값을 계속 pivot으로 선택할 때가 best case다.
Worst: 최악의 경우는 항상 최대, 최소의 pivot을 선택 할 때이다.
stable하고 in place다
function quickSort(arr, pivotIndex, endIndex) {
let storeIndex = pivotIndex + 1;
for(let i = storeIndex; i <= endIndex; i++) {
if(arr[i] < arr[pivotIndex]) {
if(storeIndex !== i) {
[arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]];
}
storeIndex += 1;
}
}
if(storeIndex -1 !== pivotIndex) {
[arr[pivotIndex], arr[storeIndex - 1]] = [arr[storeIndex - 1], arr[pivotIndex]];
}
if(pivotIndex < storeIndex - 2) quickSort(arr, pivotIndex, storeIndex - 2);
if(storeIndex < endIndex) quickSort(arr, storeIndex, endIndex);
return arr;
}
console.log(quickSort([5,4,8,6,1,8], 0, 5));
합쳐나가는 sorting 이다.
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(n) |
Average, Best, Worst: 최대한 세세하게 나눈후 합쳐가는 뒤집어진 트리와 유사하다. 그래서 logn인데 여기다 원소의 갯수를 총 곱해서 n(logn)이다.
Divide and Conquer Algorithm Link