✍️ 정렬(Sorting)
정렬(Sorting)이란? 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것
자료를 탐색할 때 정렬되어 있다면 효율적으로 탐색할 수 있다.
비교 횟수가 많아도 이동 횟수가 적다면 효율적이다.
✍️ 선택 정렬(selection sort)
선택 정렬(selection sort)이란? 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬
시간 복잡도: O(n^2)
값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있으므로 unstable하다.
✍️ 삽입 정렬(insertion sort)
삽입 정렬(insertion sort)이란? 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정 반복
최선의 경우 시간 복잡도: 이미 정렬되어 있는 경우 O(n)이다.
최악의 경우 시간 복잡도: 역순으로 정렬되어 있는 경우 O(n^2)이다.
평균의 경우 시간 복잡도: O(n^2)
✍️ 버블 정렬(bubble sort)
버블 정렬(bubble sort)이란? 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환
시간 복잡도: O(n^2)
✍️ 쉘 정렬(shell sort)
삽입 정렬이 어느 정도 정렬된 리스트에서 빠른 것에 착안한 정렬이다.
삽입 정렬은 요소들이 이웃한 위치로만 이동하므로 많은 이동에 의해서만 요소가 제자리를 찾아가지마 쉘 정렬은 요소들이 멀리 떨어진 위치로 이동할 수 있으므로 보다 적게 이동하여 제자리를 찾을 수 있다.
쉘 정렬의 중요한 아이디어는 gap을 줄여가면서 점차 정렬을 하는 것이다.
최악의 경우 시간 복잡도: O(n^2)
평균적인 경우 시간 복잡도: O(n^1.5)
✍️ 합병 정렬(merge sort)
하나가 될 때까지 계속 분할하고 merge할 때 sort한다.
시간 복잡도: O(n*log(n))
✍️ 퀵 정렬(quick sort)
평균적으로 가장 빠른 정렬 방법이다. 분할정복을 사용하는데 리스트를 2개의 부분리스트로 비균등 분할하고 각각의 부분리스트를 다시 퀵 정렬한다.
최선의 경우 시간 복잡도: 거의 균등한 리스트로 분할되는 경우 O(n*log(n))이다.
최악의 경우 시간 복잡도: 극도로 불균등한 리스트로 분할되는 경우 O(n^2)이다.
✍️ 힙 정렬(heap sort)
- 정렬해야 할 n개의 요소들을 최대 힙에 삽입
- 한번에 하나씩 요소를 힙에서 삭제하면서 저장
- 삭제되는 요소들은 값이 감소되는 순서(최대 힙일 경우)
힙 정렬이 유용한 경우에는 가장 큰 값 몇개만 필요할 때이다.
시간 복잡도: O(n*log(n))
✍️ 정렬 알고리즘 시간 복잡도 비교
