정렬 알고리즘

정렬이란?
정렬 알고리즘의 종류
비교 기반이 아닌 알고리즘
비교 기반 알고리즘
마무리
참고 링크

정렬이란?

정렬이란 데이터를 특정 기준에 따라 순서대로 나열한 것 입니다.

정렬이 중요한 이유는 데이터를 정렬하면 이진 탐색을 할 수 있게 되기 때문입니다.

이진 탐색은 절반씩 탐색하므로 전체를 탐색하는 선형 탐색 보다 압도적으로 빠르게 원하는 자료를 찾을 수 있습니다.

대신, 이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 이로 인해, 정렬 알고리즘이 중요해졌고 다양한 정렬 알고리즘이 등장했습니다.

정리

정렬이란 데이터를 특정 기준에 따라 순서대로 나열한 것
정렬을 하면 이진 탐색이 가능해져 검색 속도를 올릴 수 있다.

정렬 알고리즘의 종류

정렬 알고리즘의 종류는 다양하며, 각각의 알고리즘은 그 특성과 성능이 다르므로 주어진 환경에 맞게 적절한 알고리즘을

선택하는게 중요합니다. 다음은 정렬 알고리즘의 종류들 입니다.

비교 기반이 아닌 알고리즘

계수 정렬 (Counting Sort) O(n + k)
기수 정렬 (Radix Sort) O(nk)

계수 정렬, 기수 정렬은 원소들간의 직접적인 비교를 사용하지 않습니다. 특정 환경에서는 비교 기반 정렬 알고리즘보다 빠를 수 있지만 입력 데이터에 따라 성능이 크게 달라집니다.

비교 기반 알고리즘

기초적인 정렬 알고리즘 - O(n^2)

버블 정렬 (Bubble Sort)
선택 정렬 (Selection Sort)
삽입 정렬 (Insertion Sort)

일반적으로 삽입 정렬, 선택 정렬, 버블 정렬 순으로 속도가 빠릅니다.

향상된 정렬 알고리즘 - O(n log n)

퀵 정렬 (Quick Sort)
병합 정렬 (Merge Sort)
힙 정렬 (Heap Sort)

이들은 평균적으로 O(n log n) 시간 복잡도를 가집니다.

하지만, 퀵 정렬은 최악의 상황에서는 O(n^2)의 시간 복잡도를 가집니다.

Java의 Arrays.sort() 사용하는 알고리즘 - O(n log n) 평균 시간

듀얼 피벗 퀵소트 (Dual Pivot Quick Sort) : 원시 타입 배열일 때 사용 (int[ ], long[ ], char[ ] 등등...)
팀소트 (TimSort) : 객체 배열일 때 사용 (Integer[ ], String[ ] 등등...)

2가지 알고리즘을 사용하는 이유는 데이터 유형에 따라 최적화된 알고리즘을 사용하기 위해서 입니다.

원시(primitive) 타입 배열은 메모리에 연속적으로 위치합니다. 이는 효율적인 데이터 이동과 접근이 중요한 듀얼 피벗 퀵소트와 잘 맞습니다.

객체 배열은 일반적으로 원시 타입보다 크기가 크고 복잡한 데이터 구조를 가집니다. 듀얼 피벗 퀵소트는 값의 복사와 이동에 비용이 많이 드는 크고 복잡한 객체에는 비효율적입니다. 반면 팀소트는 이미 부분적으로 정렬된 데이터를 효율적으로 처리하여 데이터 복사와 이동을 최소화합니다.

더 자세한 내용은 듀얼 피벗 퀵소트와 팀소트 글에서 다루도록 하겠습니다.