[자료구조 멘토링] 정렬 이론 (feat.Python)

1. 정렬이란?

정렬이란 데이터를 특정 기준으로 순서대로 정리하는 과정이다.

정렬 알고리즘은 시간 복잡도와 공간 복잡도에 따라 성능이 결정된다.

정렬 알고리즘	평균 시간 복잡도	특징
선택 정렬	O(n**2)	단순하지만 비효율적
삽입 정렬	O(n**2)	대부분 정렬된 데이터에 적합
버블 정렬	O(n**2)	모든 인접 요소를 반복적으로 비교하여 교환 (비효율적)
퀵 정렬	O(n log n)	빠르고 효율적
병합 정렬	O(n log n)	안정적인 정렬, O(n)의 추가 공간이 필요함
힙 정렬	O(n log n)	최대 힙 또는 최소 힙을 활용하여 정렬

 

파이썬의 sort() 및 sorted()는 팀 정렬 알고리즘을 사용한다. 팀 정렬 알고리즘은 병합 정렬과 삽입 정렬의 조합이다.

 

1. 선택 정렬

배열에서 가장 작은 요소를 찾아,첫 번째 위치로 이동시키는 방식

https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

 

2. 삽입 정렬

현재 요소를 적절한 위치에 삽입하는 방식 

https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html

3. 버블 정렬

인접한 두 요소를 비교하여 큰 값을 뒤로 보내는 방식

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

4. 퀵 정렬

피벗을 기준으로 작은 값과 큰 값을 분할하여 정렬

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

 

5. 병합 정렬

리스트를 반으로 나누고, 각각 정렬한 후 병합하는 방식

https://ko.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/overview-of-merge-sort

6. 힙 정렬

힙 자료구조를 이용하여 최소값 또는 최대값을 정렬하는 방식 

 

아래는 최대 힙에서 11이 빠졌을 때의 정렬 방식

https://gyoogle.dev/blog/algorithm/Heap%20Sort.html