📝 정렬 알고리즘에 대해서
- 정렬 (sorting) 은 데이터들을 특정 순서에 따라 재배치하는 프로세스를 의미
- 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 등이 있다
-
단순 (구현이 간단) 하지만 비효율적인 알고리즘
📌 버블 정렬 (Bubble sort), 선택 정렬 (Selection sort), 삽입 정렬 (Insertion sort) -
복잡하지만 효율적인 알고리즘
📌 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
버블 정렬 (Bubble Sort)
-
가장 큰 값이 버블처럼 위로 올라가는 모양을 하게 되는 알고리즘
-
서로 인접한 두 원소를 검사하여 정렬 하는 알고리즘
-
버블 정렬은 중복된 데이터가 있을 경우, 데이터의 위치를 교환하지 않고 지나가기 때문에 stable 한 정렬이다.
-
첫번째 자료와 두번째 자료를, 두번째 자료와 세번째 자료를, 세번째와 네번째 자료를 ... 이런식으로 마지막-1 번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬
-
1회전을 수행하고나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외, 2회전을 수행하고나면 끝에서 두번째 자료까지는 정렬에서 제외된다.
-
n번째 정렬 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정
Big-O
- worst case : O(n^2) 정렬이 하나도 안되어 있는 경우
- best case : O(n) 이미 정렬이 되어있는 경우
버블 정렬의 경우 최악의 경우에 O(n^2) 의 시간 복잡도를 가진다.
왜냐면 각 자리를 찾기 위해 n번의 순회를 해야하고, n번의 회전 동안에 요소의 개수만큼 또 순회를 해야하기 때문이다.
그러나 이미 정렬이 되어있는 경우, 한번의 순회로 정렬 여부를 알 수 있다
버블 정렬의 장점
-
in place알고리즘으로, 메모리가 절약 된다는 장점이 있다
👉🏻in place란 자료를 정렬할 때 추가적인 메모리 공간이 필요한 게 아닌, 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻 -
구현하기 쉬운 장점. 만약 이미 정렬이 되어있는 데이터를 순회하는 경우에는 n번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트 용도로 사용될 수 있다
버블 정렬의 단점
- 버블 정렬의 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다
- 최악의 경우 시간 복잡도가 O(n^2) 까지 떨어지기 때문인데, 만약 데이터가 6개 뿐이라면 36번 순회를 해야하지만 데이터가 1000, 10000개 라면 .......
function bubbleSorting(arr) {
for (let i = 0; i < arr.length; i++) {
let swap;
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swap;
}
}
console.log(`${i}회전: ${arr}`);
if (!swap){
break;
}
}
return arr;
}
console.log(bubbleSorting([4, 2, 1, 5, 3]));
- i 가 0부터 arr.length 보다 작을 때까지 for 문을 돌린다
- 그 안에 j 가 arr.length - 1 -i 보다 작을 때까지 for 문을 돌린다
👉🏻arr.length - 1 - i는 일단arr[j]와arr[j+1]을 비교하기 위해 사용- 배열의 마지막 데이터를 포함하지 않아도 검색 대상에 포함되므로 마지막 1 을 빼주어야 한다
- 두번째로 각 회전 끝날 떄마다 마지막 데이터 정렬이 끝나기 때문에 i 를 빼주어야 한다
swap이라는 변수를 만들어,arr[j]와arr[j+1]을 비교해서arr[j]
가 더 크면 자리를 교환- 요소의 각 회전을 끝내고
swap변수가 undefined 상태라면 "정렬이 다 되어있다" 라는 뜻이므로 for 문 종료
