분류 전체보기
-
버블 정렬(Bubble Sort)알고리즘 2021. 12. 13. 20:56
특징 '붙어있는 두 개의 데이터를 비교해서 크기가 순서대로가 아니면 바꾼다'는 아이디어에서 시작된 알고리즘입니다. 가장 앞에서 뒤로 비교-교환을 수행하면 큰 숫자가 오른쪽으로 이동하는 모습을 볼 수 있습니다. 이 모습이 수면 위로 거품이 올라오는 것과 흡사해서 버블(거품)정렬이라 불립니다. 선택 정렬과 마찬가지로 데이터를 비교-교환하며 정렬되기 때문에 비교 정렬로 분류됩니다. 효율 시간복잡도 - O(N2) 선택 정렬과 시간복잡도는 같지만, 실제 수행 시간이 더 깁니다. 이는 선택 정렬에 비해 교환(swap)이 더 자주 수행되기 때문입니다. 이때문에 정렬 알고리즘 중 가장 비효율적이라고 평가됩니다. 최선, 평균, 최악의 경우 모두 시간 복잡도가 동일합니다(무조건 2개의 데이터를 비교하므로). 공간복잡도 -..
-
선택 정렬(Selection Sort)알고리즘 2021. 12. 13. 20:33
특징 '가장 작은 것을 선택해서 가장 앞으로 이동시킨다'는 아이디어로 만들어진 알고리즘 데이터를 비교하며 가장 작은 것을 선택하고, 이를 가장 앞의 것과 교환(swap)해서 이동시킵니다. 그 다음 데이터부터 위 과정을 반복합니다. 교환(swap)하는 과정에서 임시 변수가 필요합니다. 교환하는 형태로 정렬이 진행되기 때문에 임시 변수를 제외하고는 추가적인 공간이 필요하지 않습니다. 효율 시간복잡도 - O(N2) 비교 연산의 횟수: (N-1) + (N-2) + (N-3) + ... + 1 = N * (N - 1) / 2 최선, 평균, 최악의 경우의 시간복잡도가 동일합니다. 공간복잡도 - O(N) 구현 function selectionSort(input) { for (let i = 0; i < input.le..