버블정렬이란?
가장 큰 값이 버블처럼 위로 올라가는 모양을 하게 되는 알고리즘입니다
Big O
-
Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우
-
Best Case: O(n): 이미 정렬이 되어있는 경우
버블 정렬은 최악의 경우에 O(n^2)의 시간 복잡도를 가진다. 왜냐하면 각 자리를 찾기 위해서 n번의 순회를 해야하며 n번의 회전 동안에 요소의 개수만큼 또 순회를 해야하기 때문이다. 그러나 이미 정렬이 되어있는 경우에는 한 번의 순회로 정렬 여부를 알 수 있다
장점
- 버블 정렬은
in place알고리즘이기 때문에 메모리가 절약된다는 장점이 있다. - 구현하기 매우 쉽다는 장점도 있다.
in place란?
자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻이다.
단점
- 버블 정렬의 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점이다. 왜냐면 최악의 경우 O(n^2)이 소요되기 때문이다.
Stable
- 버블 정렬은 중복 데이터가 있을 경우 데이터의 위치를 교환하지 않고 지나가기 때문에 stable한 정렬이다. 여기서 stable이라는 뜻은 중복 데이터가 있는 경우에 기존 중복 데이터의 순서가 정렬이 다 끝난 이후에도 유지되는 정렬을 말한다.
1.버블정렬
function bubbleSort(arr) {
let noSwaps;//변수선언
for (let i = arr.length; i > 0; i--) {
noSwaps = true;
//i라는 변수를 통해 배열의 마지막 지점에서 시작지점까지 순회하는 반복문을 만듭니다
for (let j = 0; j < i - 1; j++) {
//j라는 변수를 통해 시작점부터 i - 1 까지 순회하는 이중 반복문을 만듭니다
if (arr[j] > arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
//배열의 j번째 요소가 j + 1번째 요소보다 크면, 두 개의 위치를 바꿉니다 (Swap)
->js엔 따로 swap이라는 것이 없어서 따로 할당을 해주는 과정이다
noSwaps = false;
//만약 Inner Loop 에서 Swap이 발생하지 않는다면, 모두 정렬된 것이므로 반복문을 종료합니다
}
}
if (noSwaps) break;
}
return arr;
}
2.Insertion Sort
삽입 정렬은 왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여 알맞은 자리에 삽입하는 형식의 정렬 방법이다.
function insertionSort (array) {
for (let i = 1; i < array.length; i++) {
let cur = array[i]; //3
let left = i - 1; //1
//4,0
while (left >= 0 && array[left] > cur) { // 5//5
array[left + 1] = array[left]; //arr[1] = 5 //left = 1/ arr[2]=5
left--; //0
console.log(left)}
array[left + 1] = cur;
console.log(`${i}회전: ${array}`);
}
return array;
}
console.log(insertionSort([5, 4, 3, 2, 1]))
1회전: 4,5,3,2,1
2회전: 3,4,5,2,1
3회전: 2,3,4,5,1
4회전: 1,2,3,4,5
[ 1, 2, 3, 4, 5 ]
3. Selection Sort
선택 정렬은 매우 단순한 정렬 알고리즘으로 구현하기 매우 쉬운 알고리즘이다. 선택 정렬 알고리즘은 이렇게 진행된다.
먼저 주어진 리스트 중에 최소값을 찾는다.
그 값을 맨 앞에 위치한 값과 교환한다.
이제 맨 앞을 제외하고 다시 순회하며 최소값을 찾는다.
그 값을 맨 앞 위치 바로 다음 위치와 교체한다. ... 반복
버블 정렬이 각 회전이 끝날 때마다 맨 마지막 데이터의 위치가 정해졌던 것과 반대로
선택 정렬은 n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해진다.
다음의 그림을 보면 이해가 쉽다.
function selectionSort (array){
for (let i = 0; i < array.length; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[minIndex] > array[j]) {
minIndex = j;
}
}
if (minIndex !== i) {
let swap = array[minIndex];
array[minIndex] = array[i];
array[i] = swap; }
console.log(`${i}회전: ${array}`);
}
return array;
}
console.log(selectionSort([5, 4, 3, 2, 1]));
선택정렬은 데이터가 정렬된 상태에서도 계속해서 순회하며 최소값을 찾기에 비효율적이다.
참고자료
https://velog.io/@young_mason/Algorithm-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-Sorting-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Basic%ED%8E%B8
https://im-developer.tistory.com/133
