기본 정렬
정렬 알고리즘 시간 복잡도 비교
Name | Best | Avg | Worst | Run-time(정수 60,000개) 단위: sec |
---|---|---|---|---|
삽입 정렬 | n | n(2) | n(2) | 7.43 |
선택 정렬 | n(2) | n(2) | n(2) | 10.84 |
버블 정렬 | n(2) | n(2) | n(2) | 22.89 |
셀 정렬 | n | n(1.5) | n(2) | 0.056 |
퀵 정렬 | nlog2n | nlog2n | n(2) | 0.014 |
힙 정렬 | nlog2n | nlog2n | nlog2n | 0.034 |
병합 정렬 | nlog2n | nlog2n | nlog2n | 0.026 |
1. 삽입 정렬 (Insertion Sort)
출처: https://im-developer.tistory.com/133 [Code Playground]
- 왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여 알맞는 자리에 삽입하는 정렬 방법
Big O
- Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우
- Best Case: O(n): 이미 정렬이 되어있는 경우
장점
- 메모리 절약
- 구현하기가 매우 쉽고 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되므로 테스트로 사용
단점
- 자료의 개수가 많아질수록 성능이 매우 떨어짐
구현
const insertionSort = (array) => {
var i = 1, j, temp;
for (i; i < array.length; i++) {
temp = array[i]; // 새로운 숫자를 선택
for (j = i - 1; j >= 0 && temp < array[j]; j--) {
// 선택한 숫자를 이미 정렬된 숫자들과 비교 -> 넣을 위치 체크,
// 선택한 숫자가 정렬된 숫자보다 작으면
array[j + 1] = array[j]; // 한 칸씩 뒤로 밀어냄
}
array[j + 1] = temp; // 마지막 빈 칸에 선택한 숫자넣음
}
return array;
};
insertionSort([5, 6, 1, 2, 4, 3]); // [1, 2, 3, 4, 5, 6]
[저작자] Wikipedia 이미지 출처
2. 선택 정렬 (Selection Sort)
- 데이터 중 맨 앞 요소와 나머지 요소를 비교하여 맨 앞 요소가 더 크면 자리 변경
- 마지막 요소를 제외한 모든 요소가 반복
[저작자] Xybernetics 이미지 출처
const selectSort = (array) => {
for (let i = 0; i < array.length - 1; i++) {
for (let j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) [array[i], array[j]] = [array[j], array[i]];
}
}
return array;
};
const array = [1, 13, 5, 24, 94, 26, 223, 36, 45, 29];
console.log(selectSort(array)); // [1, 5, 13, 24, 26, 29, 36, 45, 94, 223]
3. 버블 정렬(bubble Sort)
- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환
- 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블정렬은 단순성에도 불구하고 거의 안씀
[저작자] Algorithm 앱의 Bubble Sort GIF 이미지 출처
const bubbleSort = (data) => {
for (let i = 0; i < data.length - 1; i++) {
let swap = false; // 변화 여부 체크
for (let j = 0; j < data.length - i - 1; j++) {
if (data[j] > data[j + 1]) {
[data[j], data[j + 1]] = [data[j + 1], data[j]]; // swap
swap = true;
}
}
if (!swap) break;
}
return data;
};
const data = [10, 73, 45, 34, 2, 32, 62, 1, 25, 6, 91];
console.log(bubbleSort(data)); // [1, 2, 6, 10, 25, 32, 34, 45, 62, 73, 91]
Author And Source
이 문제에 관하여(기본 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dev_jazziron/sort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)