알고리즘. 비교 정렬(Comparison Sort) 알아보기

🌟 비교 정렬이란?

데이터들 간에 상대적 크기 관계만 이용해 정렬하는 정렬 알고리즘을 말한다. 어떤 데이터든 다 가능! 숫자나 알파벳 등등.

버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 합병 정렬, 퀵 정렬 등이 여기에 해당됨!

그리고 Non-Comparison Sort가 있는데, 이건 정렬할 데이터에 대한 사전 지식을 이용한 것이다. Bucket Sort나 Radix Sort가 여기에 해당됨.

🌟 정렬의 하한

O(n²) 는 버블, 선택, 삽입, 퀵 정렬이고

O(nlogn)은 합병, 힙 정렬!

그리고 위보다 더 낮은 비교 정렬은 존재할 수 없다.

개발자의 기록습관