✅선택
Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것
시간 복잡도 : O(N * N)
공간복잡도 : 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)
- 장점 : 버블정렬과 같이 단순하다. 버블 정렬에 비해 비교하는 횟수가 적다. 정렬하고자하는 배열안에서 교환이 이뤄지기 땜에 메모리공간을 필요로 하지 않는다.
- 단점: 비효율적이다. 불안정 정렬이다.
✅삽입
2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입
최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.
시간복잡도 : 최악의 경우 선택정렬과 같이 O(n^2)이다. 최선의 경우에는 O(n)
이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.
장점: 알고리즘이 단순하며 이미 정렬이 되어 있을 경우 매우 효율적입니다. 제자리 정렬이라 메모리를 낭비하지 않습니다. 안정정렬이고 선택정렬과 버블 정렬에 비해 상대적으로 빠릅니다.단점: 평균과 최악의 시간 복잡도가 O(N^2)으로 비효율적이며 배열의 길이가 ㅣㄹ어질 수록 비효율적입니다.
✅버블
버블 정렬은 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬입니다. 버블 정렬은 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에 전체 원소의 개수가 n개 라고 할 때, 총 n-1 번 순회하면 정렬이 끝납니다
시간 복잡도 : O(N * N)
장단점: 일단 개념이 단순해서 편함, 근데 비교작업이 너무 많아서 연산시간이 오래 걸린는 것이 단점.성능개선 방법?: 1회전, 2회전, 3회전... 을 하면서 교환횟수를 카운트 한다. 만약 교환횟수가 0 이면 정렬이 완료되었다는 의미로 끝내기.
✅병합
분할 정복 방법을 통해 구현, 요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로 퀵 정렬 같은 경우에는 피벗을 통해 정렬을 하는데, 영역을 쪼개는거고 합병 정렬은 영역을 쪼갤 수 있을 만큼 쪼개고 정렬하는 방식이다. 합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.
💡 퀵정렬로 링크드리스트를 정렬하려면 성능이 좋지않음 임의접근이기 때문이다. 이 링크드 리스트는 삽입, 삭제에서 유용하지만 접근 연산에서 비효율적이기때문에 임의로 접근하는 퀵소트 사용하면 오버헤드 발생하게 됨.
시간복잡도 : 합병 단계 k번 * 각각의 단계에서 연산 횟수 2N = O(kN)이 된다. N = 2^k, k = logN이므로 합병 정렬의 시간복잡도는 O(kN) = O(NlogN)이 된다.
✅퀵
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략인 분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 병합정렬과 다르게 퀵정렬은 비균등하게 분할한다.
시간 복잡도 : 정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순 정렬되어있으면 O(n^2)에 대한 시간복잡도를 가진다. 최선의 경우, 평균의 경우에는 O(nlog₂n)
장점: 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.단점: 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.- 개선 방법 : 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간복잡도
O(nlog₂n)으로 개선할 수 있다.
