처음에 비비교 정렬이라길래 비비고 만두를 떠올렸던 나를 반성하며....
비비교 정렬이란
비비교 정렬을 영어를 보면 non comparsion 말 그대로 요소(element)를 비교 하지 않고 정렬하는 알고리즘 입니다. 일반적으로 비교 기반 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)은 요소들을 서로 비교하여 정렬하는데, 각 비교에는 최소한 O(1) 이상의 시간이 소요됩니다. 이로 인해 비교 기반 알고리즘들의 시간 복잡도는 최소 O(n*log n)으로 됩니다.
그러나 비비교 알고리즘은 비교 연산을 하지 않으면서도 선형 시간에 정렬 문제를 해결하는 방법들을 포함하고 있습니다. 비비교 알고리즘들은 데이터에 대한 특정 가정이나 제한 조건을 활용하여 정렬을 수행합니다.
여러 비비교 알고리즘 중에서 가장 유명한 것은 "계수 정렬(Counting Sort)"과 "기수 정렬(Radix Sort)", "버킷 정렬(Bucket Sort)"이 있습니다.
계수 정렬(Counting Sort)
계수 정렬은 정수나 정수로 표현 가능한 자료들에 대해서만 동작하는 비교 알고리즘입니다. 데이터의 특성에 따라서 각 값을 카운트하고, 그 값을 누적하여 배열에 저장한 뒤, 정렬된 결과를 다시 배열에 넣는 방식으로 동작합니다. 계수 정렬은 데이터의 범위가 제한적일 때 효과적이며, 데이터의 크기에 비례하여 성능이 증가합니다.
기수 정렬(Radix Sort)
기수 정렬은 정렬할 데이터의 비교를 하지 않으면서 정렬하는 비비교 알고리즘 중 하나입니다. 기수 정렬은 데이터를 자릿수(또는 비트)에 따라서 정렬하는 데에 사용됩니다. 일반적으로 정수나 문자열과 같이 여러 자릿수가 있는 데이터를 정렬할 때 유용합니다. 각 자릿수를 기준으로 데이터를 버킷에 나누어 정렬하고, 가장 작은 자릿수부터 가장 큰 자릿수까지 반복하여 정렬을 완성합니다.
버킷 정렬(Bucket Sort)
버킷 정렬(Bucket Sort)은 비교 기반 정렬 알고리즘이 아닌 비교 알고리즘의 하나로, 입력 데이터를 여러 개의 버킷(bucket)으로 나눈 뒤, 각 버킷을 개별적으로 정렬하고 이를 다시 합쳐서 정렬된 결과를 얻어내는 방법입니다. 각 버킷은 개별적인 정렬 방법을 사용하여 정렬되기 때문에, 정렬된 데이터들을 합치는 단계가 간단하고 효율적으로 수행될 수 있습니다.
마치며
비비교 알고리즘들은 비교 기반 알고리즘보다 빠른 경우도 있지만, 대부분의 상황에서는 데이터의 특성에 따라서 성능이 달라집니다. 따라서 어떤 알고리즘이 가장 효율적인지를 판단하기 위해서는 주어진 데이터에 대한 특성과 제약 조건을 고려해야 합니다.
원래는 코드를 짜고 마무리 하는 게 일반적인데 기수 정렬, 버킷 정렬의 작동방식과 각각의 알고리즘을 활용하여서 코드를 짜볼 생각에 본 주제인 비비교 정렬에서 마칩니다.
