๐ก ๋ชจ๋ ์ ๋ ฌ์ ๊ธฐ๋ฒ์ ์ดํดํ์ฌ ์์ผ๋ก ํ ์ ์๋ ๊ฒ์ด ๋ชฉํ
์ ๋ ฌ(Sorting)
์ด๋ ๋ฐฐ์ด ๋ด ์์๋ค์ ์ผ์ ํ ์์๋๋ก ์ด๊ฑฐํ๋ ์๊ณ ๋ฆฌ์ฆ
๋ํ ์ ๋ ฌ ๊ธฐ๋ฒ :
๋ฒ๋ธ ์ ๋ ฌ(Bubble Sort)
์ ํ ์ ๋ ฌ(Selection Sort)
์ฝ์
์ ๋ ฌ(Insertion Sort)
ํฉ๋ณ ์ ๋ ฌ(Merge Sort)
ํต ์ ๋ ฌ(Quick Sort)
์๋ก ์ธ์ ํ ๋ ์์๋ฅผ ๋น๊ตํ๋ฉด์ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ
์๊ฐ ๋ณต์ก๋ : O(n^2)
๊ฐ๊น์ด ๋ ์๋ฅผ ๋น๊ตํด ํฐ ์์ ์ธ๋ฑ์ค๋ฅผ ๋ค๋ก ๋ฏธ๋ค์ค.
๊ฐ์ฅ ๋จ์ํ๊ฒ ๊ตฌํํ๋ฉด ์๋์ ๊ฐ์ด ๋๋ค.
function bubbleSort(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);
}
}
}
return arr;
}
let swap = function (arr, idx_1, idx_2) {
let tmp = arr[idx_1];
arr[idx_1] = arr[idx_2];
arr[idx_2] = tmp;
}
console.log(bubbleSort([6, 5, 1, 3, 2])); // [1,2,3,5,6]
์ธ๋ฑ์ค ์กฐ์ ์ผ๋ก ์ต์ ํ (
i = step ์ = ์ ๋ ฌ๋ ๊ฐ์
์ด๋ฏ๋ก ๋ค์ step์์ ๋์ง ์์๋ ๋๋ค. )
function bubbleSort(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);
}
}
}
return arr;
}
let swap = function (arr, idx_1, idx_2) {
let tmp = arr[idx_1];
arr[idx_1] = arr[idx_2];
arr[idx_2] = tmp;
}
console.log(bubbleSort([6, 5, 1, 3, 2])); // [1,2,3,5,6]
์ธ๋ฑ์ค ์กฐ์ ๋ฐ swapped flag๋ฅผ ํตํด step์ swap ์ํฌ ์๊ฐ ์์ผ๋ฉด ์ ๋ ฌ์ ๋ฉ์ถ๋ค. (
swap์ ์ํ๋ค = ์ ๋ ฌ ๋๋ค
)
function bubbleSort(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;
}
return arr;
}
let swap = function (arr, idx_1, idx_2) {
let tmp = arr[idx_1];
arr[idx_1] = arr[idx_2];
arr[idx_2] = tmp;
}
console.log(bubbleSort([6, 5, 1, 3, 2])); // [1,2,3,5,6]
์ต์ข ๋ฆฌํํ ๋ง ๋ฒ์ , ๋ฒ๋ธ ์ ๋ ฌ์ ์ค๋ฆ์ฐจ์ ๋ด๋ฆผ์ฐจ์์ ๊ณ ์ฐจํจ์๋ฅผ ์ฌ์ฉํด ๊ตฌํํ๋ค.
const swap = (arr, idx_1, idx_2) => {
let tmp = arr[idx_1];
arr[idx_1] = arr[idx_2];
arr[idx_2] = tmp;
};
const ascending = (x, y) => {
return x > y;
};
const descending = (x, y) => {
return x < y;
};
const bubbleSort = (arr, compare) => {
let isSwapped;
for (let i = 0; i < arr.length - 1; i++) {
isSwapped = false;
for (let j = 0; j < arr.length - i - 1; j++) {
if (compare(arr[j], arr[j + 1])) {
swap(arr, j, j + 1);
isSwapped = true;
}
}
if (!isSwapped) break;
}
};
input = [6, 1, 4, 5, 2, 3];
bubbleSort(input, ascending)
console.log(input);
์ต์๊ฐ
์ ์ฐพ์ ๋ฐ์ดํฐ์ ๊ฐ์ฅ ์์ผ๋ก ์ด๋์ํค๋ ๋ฐฉ์์ ๋ฐ๋ณตํ๋ ์ ๋ ฌ
์๊ฐ ๋ณต์ก๋ : O(n^2)
๋งจ ์์ ์ธ๋ฑ์ค ๋ถํฐ ์ต์๊ฐ์ ์ฐพ์์ swapํด์ค
์ต์ข ๋ฆฌํํ ๋ง ๋ฒ์ , ์ ํ ์ ๋ ฌ์ ์ค๋ฆ์ฐจ์ ๋ด๋ฆผ์ฐจ์์ ๊ณ ์ฐจํจ์๋ฅผ ์ฌ์ฉํด ๊ตฌํํ๋ค. ( swap ํจ์์ ๊ต์ฒด๊ฐ i๋ฒ ์ด๋ฃจ์ด์ง )
const swap = (arr, idx_1, idx_2) => {
let tmp = arr[idx_1];
arr[idx_1] = arr[idx_2];
arr[idx_2] = tmp;
};
const ascending = (x, y) => {
return x > y;
};
const descending = (x, y) => {
return x < y;
};
const selectionSort = (arr, compare) => {
let minIdx;
for (let i = 0; i < arr.length - 1; i++) {
minIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (compare(arr[minIdx], arr[j])) minIdx = j;
}
swap(arr, i, minIdx);
}
};
input = [6, 1, 4, 5, 2, 3, 12, 7, 20, 23, 18];
selectionSort(input, ascending);
console.log(input);
์ด๋ฏธ ์ ๋ ฌ๋ ์์ญ๊ณผ ๋น๊ตํ๋ฉด์ ์์ ์ ์์น๋ฅผ ์ฐพ์ ์์๋ฅผ ์ฝ์ ํ๋ฉฐ ์ ๋ ฌ
์๊ฐ ๋ณต์ก๋ : O(n^2)
๋ ๋ฒ์งธ ์ธ๋ฑ์ค ๋ถํฐ ์์ํ์ฌ ์์ ์ธ๋ฑ์ค ์์์ ๊ฐ๋ณด๋ค ์์ผ๋ฉด shiftํ๊ณ ๊ฐ์ ๋ฃ๋๋ค. ์ด ๊ฒ์ ๋ฐ๋ณตํ๋๊ฒ ์ฝ์ ์ ๋ ฌ
for break
์กฐ๊ฑด : ์ ๋ ฌ๋์ด์๋ ์์๋ค๋ณด๋ค ํฌ๊ธฐ๊ฐ ํฌ๋ฉด ๋ฉ์ถค (์ค๋ฆ์ฐจ์)
์ ๋ ฌ๋์ด์๋ ์์๋ค๋ณด๋ค ํฌ๊ธฐ๊ฐ ์์ผ๋ฉด ๋ฉ์ถค (๋ด๋ฆผ์ฐจ์)
const swap = (arr, idx_1, idx_2) => {
let tmp = arr[idx_1];
arr[idx_1] = arr[idx_2];
arr[idx_2] = tmp;
};
const ascending = (x, y) => {
return x > y;
};
const descending = (x, y) => {
return x < y;
};
const insertionSort = (arr, compare) => {
for (let i = 1; i < arr.length; i++) {
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;
}
};
input = [6, 1, 4, 5, 2, 3, 12, 7, 20, 23, 18];
insertionSort(input, ascending);
console.log(input);
ํ๋์ ๋ฐฐ์ด์ ๋ ๊ฐ์ ๊ท ๋ฑํ ํฌ๊ธฐ๋ก
๋ถํ
ํ๊ณ ,๋ถ๋ถ ์ ๋ ฌ
ํ ๋ค์ ํฉ์น๋ฉด์์ ์ฒด๋ฅผ ์ ๋ ฌ
ํ๋ ์๊ณ ๋ฆฌ์ฆ
์๊ฐ ๋ณต์ก๋ : O(n log n)
๋ฐฐ์ด์ length๊ฐ 1์ผ ๋ ๊น์ง ๋ถํ ํ ํ ๋ณํฉํ๋ฉฐ ํฌ๊ธฐ ์์ผ๋ก ์ ๋ ฌํ๋ค.
n-way ํฉ๋ณ ์ ๋ ฌ์ ๊ฐ๋ ์ ๋ค์๊ณผ ๊ฐ๋ค.
์ ๋ ฌ๋์ง ์์ ๋ฐฐ์ด์ ๊ฐ๊ฐ ํ๋์ ์์๋ง ํฌํจํ๋ n๊ฐ์ ๋ถ๋ถ๋ฆฌ์คํธ๋ก ๋ถํ ํ๋ค. (ํ๋์ ์์๋ง ์๋ ๋ฐฐ์ด์ ์ ๋ ฌ๋ ๊ฒ๊ณผ ๊ฐ์ผ๋ฏ๋ก)
๋ถ๋ถ๋ฆฌ์คํธ๊ฐ ํ๋๋ง ๋จ์ ๋๊น์ง ๋ฐ๋ณตํด์ ๋ณํฉํ๋ฉฐ ์ ๋ ฌ๋ ๋ถ๋ถ๋ฆฌ์คํธ๋ฅผ ์์ฑํ๋ค. ๋ง์ง๋ง ๋จ์ ๋ถ๋ถ๋ฆฌ์คํธ๊ฐ ์ ๋ ฌ๋ ๋ฆฌ์คํธ์ด๋ค.
ํํฅ์ 2-way ํฉ๋ณ ์ ๋ ฌ์ ๋ค์๊ณผ ๊ฐ์ด ์๋ํ๋ค.
์กฐ๊ฑด๋ถ : ๋ฐฐ์ด ๊ธธ์ด๊ฐ 1 ์ดํ์ด๋ฉด ์ด๋ฏธ ์ ๋ ฌ๋ ๊ฒ์ผ๋ก ๋ณธ๋ค.
๋ถํ (divide)
: ์ ๋ ฌ๋์ง ์์ ๋ฐฐ์ด ์ ๋ฐ์ผ๋ก ์๋ผ(๋ฐ์ฌ๋ฆผ-toFixed
) ๋น์ทํ ํฌ๊ธฐ์ ๋ ๋ถ๋ถ ๋ฐฐ์ด๋ก ๋๋๋ค.์ ๋ณต(conquer)
: ๊ฐ ๋ถ๋ถ ๋ฐฐ์ด์ ์ฌ๊ท์
์ผ๋ก ํฉ๋ณ ์ ๋ ฌ์ ์ด์ฉํด ์ ๋ ฌํ๋ค.๊ฒฐํฉ(combine)
: ๋ ๋ฐฐ์ด์ ๋ค์ ํ๋์ ์ ๋ ฌ๋ ๋ฐฐ์ด๋ก ํฉ๋ณํ๋ค.const ascending = (x, y) => {
return x > y;
};
const descending = (x, y) => {
return x < y;
};
const mergeSort = (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[k++] = right[j++];
return arr;
};
input = [6, 1, 4, 5, 2, 3, 12, 7, 20, 23, 18];
mergeSort(input, ascending);
console.log(input);
ํน์ ๊ฐ(pivot)์ ๊ธฐ์ค์ผ๋ก ์ผ๊ณ ํฐ ์ซ์์ ์์ ์ซ์๋ฅผ ๋ถํ ํ์ฌ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ
์๊ฐ ๋ณต์ก๋ : O(n log n)
ํต ์ ๋ ฌ์ ๋ถํ ์ ๋ณต(divide and conquer) ๋ฐฉ๋ฒ์ ํตํด ๋ฆฌ์คํธ๋ฅผ ์ ๋ ฌํ๋ค.
ํต ์ ๋ ฌ๋ ๋ถํ /์ ๋ณต ๋ฐฉ๋ฒ์ ํตํด ๊ตฌํํ๋ค.
์ฌ๊ท
const swap = (arr, idx_1, idx_2) => {
let tmp = arr[idx_1];
arr[idx_1] = arr[idx_2];
arr[idx_2] = tmp;
};
const ascending = (x, y) => {
return x > y;
};
const descending = (x, y) => {
return x < y;
};
const quickSort = (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);
}
};
input = [6, 1, 4, 5, 2, 3, 12, 7, 20, 23, 18];
quickSort(input, ascending);
console.log(input);
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋ค์ํ ๊ธฐ๋ฒ๋ค์ ์์ ๋ฅผ ํตํด ์ดํดํด ๋ณด์๋ค.
ํฉ๋ณ์ ๋ ฌ
๊ณผ ํต ์ ๋ ฌ
์ ๋ถํ ์ ๋ณต ์ด๋ก (์ฌ๊ท)์ ์กฐ๊ธ ๋ ์ดํดํด์ผ ํ๋ฒ์ ์ดํด๊ฐ ๊ฐ๋ฅํ ๊ฒ ๊ฐ๋ค.