티스토리 뷰
1. 버블정렬 (Bubble Sort)
시간복잡도 : 최악 O(N^2) / 최선 O(N^2) / 평균 O(N^2)
버블 정렬은 현재 값과 바로 뒤에 있는 값을 비교하여 차례대로 정렬해주는 정렬이다.
중복 값이 있을 때 중복값의 순서가 바뀌지 않는 stable 정렬이다.
코드
오름차순
const before_list = [7, 6, 4, 4, 25, 3, 9, 5];
console.log(`기존 리스트 : ${before_list}`);
function bubble_sort(array) {
for(let i=0; i<array.length; i++) {
for(let j=0; j<array.length-1-i; j++) {
if(array[j] > array[j+1]) {
const compare_number = array[j];
array[j] = array[j+1];
array[j+1] = compare_number;
}
}
console.log(`${i + 1}회 : ${array}`);
}
return array;
}
const sorted_list = bubble_sort(before_list);
console.log(`정렬 후 리스트 : ${sorted_list}`);결과 - 정렬이 안된 리스트를 넣어줬을 때
결과 - 정렬이 된 리스트를 넣어줬을 때
처음엔 7을 기준으로 버블 정렬이 일어나지만, 7이 25와 만나고 난 뒤로부턴 7은 해당자리에 고정돼 있고 25와 뒤 숫자들의 비교가 일어나 25가 맨 끝으로 정렬되게 된다.
후에 다른 작은 숫자들과 비교하면서 숫자들은 자기 자리를 찾아간다.
다만 이렇게 정렬 했을 때 이미 정렬이 된 이후에도 불필요한 탐색이 일어난다.
따라서 compare_number를 let에 할당해주고 더이상 비교할 compare_number가 없으면 for문을 break시킴으로써 불필요한 탐색을 줄일 수 있다.
수정한 코드
수정한 코드에서 플래그를 넣어주면 무의미한 루프를 반복하지 않기 때문에 정렬이 돼 있는 코드는 1회에서 끝난다.
function new_bubble_sort(array) {
for(let i=0; i<array.length; i++) {
let compare_number;
for(let j=0; j<array.length-1-i; j++) {
if(array[j] > array[j+1]) {
compare_number = array[j];
array[j] = array[j+1];
array[j+1] = compare_number;
}
}
console.log(`${i + 1}회 : ${array}`);
if(!compare_number) {
break;
}
}
return array;
}
결과
정렬이 안된 리스트를 넣어줬을 때
탐색이 8회 -> 6회로 줄었다.
결과 - 정렬이 이미 된 리스트를 넣어줬을 때
8회 -> 1회로 줄었다
내림차순은 if 문 안의 연산자를 바꿔주면 된다.
내림차순
function reverse_bubble_sort(array) {
for(let i=0; i<array.length; i++) {
let compare_number;
for(let j=0; j<array.length-1-i; j++) {
if(array[j] < array[j+1]) {
compare_number = array[j];
array[j] = array[j+1];
array[j+1] = compare_number;
}
}
console.log(`${i + 1}회 : ${array}`);
if(!compare_number) {
break;
}
}
return array;
}
결과
2. 삽입정렬 (Insertion Sort)
시간복잡도 : 최악 O(N^2) / 최선 O(N) / 평균 O(N^2)
Bubble Sort와 마찬가지로 stable정렬이다.
삽입 정렬은 오른 쪽 요소를 왼쪽 요소들과 비교하면서 알맞은 자리에 삽입하는 정렬 방식이다.
코드 - 오름차순
const before_list = [7, 6, 4, 3];
console.log(`정렬전: ${before_list}`);
function insertion_sort(array) {
for(let i=1; i<array.length; i++) {
let current_number = array[i];
let left = i-1;
while(left >= 0 && array[left] > current_number) {
array[left + 1] = array[left];
left--;
}
array[left + 1] = current_number;
console.log(`${i}번째: ${array}`);
}
return array;
}
const sorted_list = insertion_sort(before_list);
console.log(`정렬후: ${sorted_list}`);
결과
코드 - 내림차순
const before_list = [3, 4, 6, 7];
console.log(`정렬전: ${before_list}`);
function insertion_sort(array) {
for(let i=1; i<array.length; i++) {
let current_number = array[i];
let left = i-1;
while(left >= 0 && array[left] < current_number) {
array[left + 1] = array[left];
left--;
}
array[left + 1] = current_number;
console.log(`${i}번째: ${array}`);
}
return array;
}
const sorted_list = insertion_sort(before_list);
console.log(`정렬후: ${sorted_list}`);
결과
3. 선택정렬 (Selection Sort)
시간복잡도: 최악 O(N^2) 최선 O(N^2) / 평균 O(N^2)
리스트 중 최소 값을 찾아 선택한 후 맨 앞에 위치한 값과 바꾼다.
이후 맨 앞 값을 제외한 후 최소 값을 찾아 반복한다.
중복된 값이 있으면 정렬 전과 정렬 후의 순서가 바뀔 수도 있는 unstable한 정렬이다.
코드 - 오름차순
const before_list = [7,6,5,4,3,2,1];
console.log(`정렬전: ${before_list}`);
function selection_sort(array) {
for(let i=0; i<array.length; i++) {
let min_index = i;
let swap_number;
for(let j=i+1; j<array.length; j++) {
if(array[min_index] > array[j]) {
min_index = j;
}
}
swap_number = array[min_index];
array[min_index] = array[i];
array[i] = swap_number;
console.log(`${i}번째 : ${array}`);
}
return array;
}
const sorted_list = selection_sort(before_list);
console.log(`정렬후: ${sorted_list}`);
결과
이미 정렬이 되었음에도 계속 탐색을 하는 결과가 나타난다.
불필요한 탐색을 없애기 위해 현재 탐색값의 자리가 바뀌지 않으면 정렬이 다 된 것으로 판별, break하는 구문을 추가했다.
수정한 코드
function new_selection_sort(array) {
for(let i=0; i<array.length; i++) {
let min_index = i;
let swap_number;
for(let j=i+1; j<array.length; j++) {
if(array[min_index] > array[j]) {
min_index = j;
}
}
swap_number = array[min_index];
array[min_index] = array[i];
array[i] = swap_number;
console.log(`${i}번째 : ${array}`);
if(swap_number == array[min_index]) {
break;
}
}
return array;
}
결과
4. 병합정렬 (Merge Sort)
시간복잡도: 모두 O(n log n)으로 동일
n크기의 data를 크기1이 될때까지 n/2씩 나누어 부분집합으로 만든 후, 두 부분집합을 병합해 나가는 알고리즘이다.
더...그림을 그릴 수가 없어서 움짤로 설명을 잘해둔 블로그를 참고했다.
https://todaycode.tistory.com/54
합병 정렬(=병합 정렬) 이란?
1. 합병 정렬 1-1. 합병 정렬? 병합 정렬? 1-2. 합병 정렬이란? 1-3. 움짤로 보는 예시 1-4. 글로 보는 예시 1-5. 소스코드 1-6. 합병 정렬의 시간 복잡도 1-7. 합병 정렬은 얼마나 빠를까? 1. 합병 정렬 1-1.
todaycode.tistory.com
코드
const before_list = [3,1,7,4,5,6,8,2];
console.log(`정렬전: ${before_list}`);
// shift랑 unshift, spread 연산때문에 개고생함
function merge(left, right) {
console.log(`\n 받아온 left:${left} 받아온 right:${right}`)
const merge_list = [];
while(left.length && right.length) {
if(left[0] >= right[0]) {
merge_list.push(right.shift());
}
else {
merge_list.push(left.shift());
}
}
// if(!left) {
// merge_list.concat(right);
// }
// else {
// merge_list.concat(left);
// }
console.log([...merge_list, ...left, ...right]);
return [...merge_list, ...left, ...right];
}
function merge_sort(array) {
console.log(`\n현재 array: ${array}`);
if(array.length === 1) {
return array;
}
const mid = Math.ceil(array.length / 2);
const left = array.slice(0, mid);
const right = array.slice(mid);
console.log(`left: ${left}, right: ${right}`);
return merge(merge_sort(left), merge_sort(right));
}
const sorted_list = merge_sort(before_list);
console.log(`정렬후: ${sorted_list}`);
shift, unshift 메소드가 계속 헷갈리고... spread연산으로 하면 깔끔하게 정리 됐을 텐데 concat메소드를 이용한답시고 코드가 더러워졌다.
결과
5. 퀵정렬 (Quick Sort)
시간 복잡도: 최악 O(N^2) / 최선 O (n log₂ n) / 평균 O(n log₂ n)
피봇을 설정한 후, 피봇 보다 작은 숫자는 왼쪽, 큰 숫자는 오른쪽으로 정렬하여 나눠진 숫자에 대해 다시 피봇을 설정하고 반복한다.
코드
const before_list = [3,1,7,4,5,6,8,2];
console.log(`정렬전: ${before_list}`);
function quick_sort(array) {
if(array.length <= 1) {
return array;
}
const pivot = []; // 피봇 설정
const left = [];
const right = [];
pivot.push(array.shift());
while(array.length) { // array안의 숫자가 없을 때까지 반복
if (array.length === 1) {
pivot > array[0] ? left.push(array[0]) : right.unshift(array[0]);
if(array[0] === pivot) {
pivot.push(array[0]);
}
break;
}
const low = array.shift();
const high = array.pop();
pivot > low ? left.push(low) : right.unshift(low);
pivot < high ? right.unshift(high) : left.push(high);
if(low === pivot) {
pivot.push(low);
}
if(high === pivot) {
pivot.push(high);
}
}
return [...quick_sort(left), ...pivot, ...quick_sort(right)];
}
const sorted_list = quick_sort(before_list);
console.log(`정렬후: ${sorted_list}`);
low와 high가 크면 서로 바꿔줘야 하는 알고리즘 때문에 unshift연산을 사용했는데...그냥 바꿔줄 필요 없이 계속 분할 정복만 해도 코드가 실행된다.
수정한 코드
const before_list = [3,1,7,4,5,6,8,2];
console.log(`정렬전: ${before_list}`);
function quick_sort(array) {
if(array.length <= 1) {
return array;
}
const pivot = array[0]; // 피봇 설정
const left = [];
const right = [];
for(let i=1; i<array.length; i++) {
array[i] <= pivot ? left.push(array[i]) : right.push(array[i]);
}
return [...quick_sort(left), pivot, ...quick_sort(right)];
}
const sorted_list = quick_sort(before_list);
console.log(`정렬후: ${sorted_list}`);
위 코드에서 pivot은 배열이 아니기 때문에 iterable연산이 불가능하고, 따라서
...pivot (x)
pivot (o)으로 배열을 연결해준다.
결과
'Algorithm' 카테고리의 다른 글
| [SQL] 문법 공부 (0) | 2023.02.15 |
|---|---|
| [알고리즘] JS 배열 복사 / 얕은 복사, 깊은 복사 (0) | 2022.09.08 |
| [알고리즘] leetcode 8월 (0) | 2022.08.30 |