DAA 선형 시간 정렬 - DAA 튜토리얼

소개

정렬은 요소를 숫자 또는 알파벳 순서와 같은 특정 순서로 배열하는 컴퓨터 과학의 필수 작업입니다. 다양한 정렬 알고리즘이 개발되었으며 각각 시간 및 효율성 지표가 있습니다. 선형 시간 정렬은 중요한 이점이 있는 정렬 알고리즘의 하위 집합입니다. 주어진 요소 집합을 선형 시간으로 정렬할 수 있으며 런타임은 입력 크기에 따라 선형적으로 증가합니다.

가장 잘 알려진 선형 시간 정렬 알고리즘은 내림차순 정렬입니다. 계산 정렬은 입력 요소의 범위가 알려져 있고 상대적으로 작을 때 특히 효율적입니다. 이렇게 하면 다른 많은 정렬 알고리즘에서 시간이 많이 걸리는 작업인 요소를 비교할 필요가 없습니다. 입력 영역 지식을 사용하여 계산 정렬은 선형 시간 복잡도를 달성합니다. 숫자 정렬은 먼저 입력 배열을 스캔하여 각 요소의 개수를 결정합니다. 그런 다음 이 숫자를 사용하여 정렬된 결과 테이블에서 요소의 올바른 위치를 계산합니다. 알고리즘은 다음 단계로 구성됩니다.

범위를 결정하려면 입력 배열의 최소값과 최대값을 식별하십시오.
범위 크기와 0으로 초기화된 워크시트를 만듭니다.
입력 배열을 반복하고 발견된 각 요소를 증가시킵니다.
각 요소의 올바른 위치를 얻기 위해 누적 합계를 계산하여 워크시트를 수정합니다.
입력 배열과 동일한 크기의 출력 배열을 만듭니다.
입력 배열을 다시 이동하여 워크시트를 기준으로 출력 배열의 올바른 위치에 각 요소를 배치합니다.
이제 결과 테이블에는 정렬된 요소가 포함됩니다.

내림차순 정렬의 가장 큰 장점은 O(n)의 선형 시간 복잡도를 달성하므로 큰 입력 크기에 매우 효율적이라는 것입니다. 그러나 그 적용 가능성은 입력 요소의 선택이 미리 알려져 있고 상대적으로 작은 시나리오로 제한됩니다.

퀵소트(quicksort)나 병합(merge)과 같은 다른 정렬 알고리즘은 일반적으로 O(n log n)의 시간 복잡도를 가지며, 이는 많은 실제 응용 프로그램에서 효율적이라고 간주됩니다. 수치 정렬과 같은 선형 시간 정렬 알고리즘은 입력의 특정 제약 조건이나 속성으로 인해 선형 시간 복잡도를 사용할 수 있는 경우 대안을 제공합니다.

역사

선형 시간 정렬 알고리즘은 컴퓨터 과학에서 풍부한 역사를 가지고 있습니다. 선형 시간 순서의 발전은 20세기 중반으로 거슬러 올라갈 수 있으며, 과학자와 수학자들의 기여는 상당했습니다. 최초의 선형 시간 정렬 알고리즘 중 하나는 Harold H. Seward가 1954년에 제안한 버킷 정렬입니다. 버킷 정렬은 입력 요소를 한정된 수의 버킷으로 나눈 다음 각 버킷을 별도로 정렬합니다. 이 알고리즘은 입력 요소의 분포가 상대적으로 균일한 경우 선형 시간 복잡도를 갖습니다.

1959년에 Kenneth E. Iverson은 선형 시간 복잡도를 달성하는 기수 알고리즘을 도입했습니다. 기수는 숫자나 부호를 기준으로 요소를 가장 중요하지 않은 것부터 가장 중요한 것까지 정렬합니다. 숫자 또는 버킷 정렬과 같은 강력한 정렬 알고리즘을 사용하여 각 숫자 위치의 요소를 정렬합니다. 기수 정렬은 펀치 카드와 초기 컴퓨터 시스템 시대에 인기를 끌었습니다. 그러나 가장 잘 알려진 선형 시간 정렬 알고리즘은 1954년 Harold H. Seward와 Peter Elias가 도입한 열거형이며 나중에 1961년 Harold H. 'Bobby' Johnson이 독립적으로 재발견했습니다. 수치 정렬은 상당한 주목을 받았습니다.

이는 입력 요소의 범위가 알려져 있고 상대적으로 작을 때 특히 효과적입니다. 선형 시간 정렬의 역사는 다른 전문 알고리즘의 개발과 함께 계속되었습니다. 예를 들어, 1987년 Hanan Samet는 다차원 데이터에 대한 선형 시간 정렬 알고리즘인 이진 분포 트리 정렬을 제안했습니다. 수년에 걸쳐 연구자들은 특정 시나리오와 제약 조건에 초점을 맞춰 선형 스케줄링 알고리즘을 계속 연구하고 개선해 왔습니다. 더 많은 시나리오에서 효율성을 위해 퀵 정렬 및 병합과 같은 알고리즘이 더 널리 사용되지만 선형 시간 정렬 알고리즘은 특정 상황에서 선형 시간 복잡성을 활용할 수 있는 경우 귀중한 대안을 제공합니다. 일반적으로 선형 시간 정렬의 역사는 비교 기반 정렬 알고리즘의 한계를 극복하고 대용량 데이터 세트를 선형 시간으로 정렬할 수 있는 효율적인 알고리즘을 찾는 것이 특징입니다. 다양한 연구자들의 기여로 이러한 전문적인 분류 기술을 개발하고 이해할 수 있는 길을 열었습니다.

선형 시간 정렬의 유형

여러 가지 선형 시간 정렬 알고리즘이 있습니다. 두 가지 주요 유형은 개수 기반 알고리즘과 기수 기반 알고리즘입니다. 다음 유형에 따라 분류된 가장 일반적인 선형 시간 정렬 알고리즘은 다음과 같습니다.

계산 기반 알고리즘

개수 기반 정렬:Counting-Based는 비비교 정렬 알고리즘입니다. 입력 배열에서 각 특정 요소의 발생 횟수를 계산하고 이 정보를 사용하여 정렬된 출력 배열에서 각 요소의 올바른 위치를 결정합니다. 개수 기반 정렬에서는 입력 요소가 정수이거나 정수에 추가될 수 있다고 가정합니다.

기수 기반 알고리즘

기수 정렬:Radix Sort는 숫자나 문자를 기준으로 요소를 정렬하는 비비교 기반 정렬 알고리즘입니다. 가장 중요한 숫자부터 가장 중요한 숫자까지 요소의 각 숫자 또는 부호를 계산합니다. 근진 정렬에서는 입력 요소가 정수 또는 문자열이라고 가정합니다.버킷 정렬:버킷 정렬은 요소를 범위나 분포에 따라 고정 그룹으로 나누는 기수 정렬의 변형입니다. 각 세그먼트는 다른 정렬 알고리즘을 사용하거나 재귀적으로 bin 정렬을 사용하여 개별적으로 정렬됩니다.MSD(최상위 숫자) 기수 정렬:MSD 기수 정렬은 가장 중요한 요소를 기준으로 요소 정렬을 시작하는 기수 정렬의 변형입니다. 현재 숫자 값을 기준으로 요소를 하위 그룹으로 재귀적으로 나누고 모든 숫자가 계산될 때까지 각 하위 그룹에 MSD 기수 정렬을 적용합니다.LSD(최하위 숫자) 기수 정렬:LSD Radix Sort는 가장 중요하지 않은 요소를 기준으로 요소 정렬을 시작하는 또 다른 변형입니다. 각 숫자를 기준으로 요소를 가장 오른쪽에서 가장 왼쪽으로 재귀적으로 정렬하여 정렬된 결과를 생성합니다. 개수 기반 및 루트 기반 정렬 알고리즘은 모두 범위 또는 표현 구조(예: 숫자 또는 문자)와 같은 입력 요소의 특정 속성을 활용하여 선형 시간 복잡도를 달성합니다. 단, 입력 데이터의 특성에 따라 적용 여부가 달라질 수 있습니다.

선형 시간 정렬의 장점

숫자 정렬과 같은 선형 시간 정렬 알고리즘은 특정 시나리오에서 여러 가지 이점을 제공합니다.

큰 입력 크기에 효율적:선형 시간 정렬 알고리즘의 시간 복잡도는 O(n)입니다. 이는 실행 시간이 입력 크기에 따라 선형적으로 증가함을 의미합니다. 이는 일반적으로 O(n log n)의 시간 복잡도를 갖는 퀵 정렬 또는 병합 알고리즘과 같은 비교 기반 정렬 알고리즘에 비해 대규모 데이터 세트에 대해 매우 효율적입니다.비교 작업 없음:열거 정렬과 같은 선형 시간 정렬 알고리즘은 기본 비교에 의존하지 않고 대신 범위나 분포와 같은 입력 요소에 대한 특정 속성이나 정보를 사용합니다. 이 기능은 복잡한 객체나 비용이 많이 드는 비교 작업과 같이 비교 비용이 높을 때 유리합니다.특정 입력 속성에 대한 적합성:선형 시간 정렬 알고리즘에는 입력 요소에 대한 특정 요구 사항이나 가정이 있는 경우가 많습니다. 예를 들어 정렬 순서를 계산하려면 입력 요소의 범위를 미리 알아야 합니다. 이러한 조건이 충족되면 선형 시간 정렬 알고리즘은 일반 정렬 알고리즘에 비해 상당한 성능 이점을 제공할 수 있습니다.안정적인 정렬:숫자 정렬 및 기수 정렬을 포함한 많은 선형 시간 정렬 알고리즘은 본질적으로 안정적입니다. 일관성이란 중복된 키나 값이 있는 요소가 정렬된 출력에서 상대적 순서를 유지한다는 것을 의미합니다. 이는 여러 속성이 있는 개체나 레코드를 정렬하거나 동일한 값의 요소의 원래 순서를 유지하는 것이 필수적인 경우 매우 중요할 수 있습니다.사용의 용이성:열거 정렬과 같은 선형 시간 정렬 알고리즘은 더 복잡한 비교 기반 정렬 알고리즘에 비해 상대적으로 구현하기 쉬운 경우가 많습니다. 이해하고 디버깅하기가 더 쉬우므로 단순성과 명확성이 요구되는 상황에 적합합니다.

선형 시간 정렬의 단점

선형 스케줄링 알고리즘에는 장점이 있지만 특정 제한 사항과 단점도 있습니다.

입력 요구 사항 제한:선형 시간 정렬 알고리즘에는 입력 요소에 대한 특정 요구 사항이나 가정이 있는 경우가 많습니다. 예를 들어 정렬 순서를 계산하려면 입력 요소의 범위를 미리 알아야 합니다. 이러한 제한은 이러한 조건이 충족되는 상황에 대한 적용 가능성을 제한합니다. 범위가 광범위하거나 알 수 없는 경우 메모리 요구 사항이 실용적이지 않거나 사용 가능한 리소스를 초과할 수 있습니다.추가 공간 요구사항:숫자 정렬과 같은 일부 선형 시간 정렬 알고리즘에는 다른 배열이나 데이터 구조를 저장하기 위한 추가 공간이 필요합니다. 필요한 공간은 입력 요소 수에 비례하는 경우가 많습니다. 이는 메모리 사용량이 문제가 될 때, 특히 대규모 데이터 세트나 제한된 메모리 리소스를 처리할 때 단점이 될 수 있습니다.다양성 부족:선형 시간 정렬 알고리즘은 특정 시나리오 또는 제약 조건에 맞게 설계된 특수 알고리즘입니다. 일반적인 정렬 작업이나 다양한 입력 분포에 더 적합하고 효율적이어야 할 수도 있습니다. 퀵 정렬이나 병합과 같은 비교 기반 정렬 알고리즘은 더 다양하며 더 넓은 범위의 입력 범위를 처리할 수 있습니다.작은 범위 또는 희박한 데이터에는 비효율적입니다.열거형과 같은 선형 시간 정렬 알고리즘은 입력 요소의 범위가 작고 조밀하게 분산될 때 가장 효율적입니다. 범위가 광범위하거나 데이터가 희박한 경우(즉, 고유한 값이 몇 개만 있는 경우) 알고리즘은 입력 범위의 비어 있거나 희박하게 채워진 부분을 처리하는 시간과 노력을 절약할 수 있습니다.특정 데이터 유형으로 제한됩니다.열거형 정렬과 같은 선형 시간 정렬 알고리즘은 주로 음수가 아닌 정수 또는 키-값 개체를 정렬하도록 설계되었습니다. 부동 소수점 숫자, 문자열 또는 복잡한 데이터 구조와 같은 다른 데이터 유형을 정렬하는 데 적합하지 않을 수 있습니다. 다양한 데이터 유형이나 사용자 정의 비교 기능을 처리하기 위해 선형 시간 정렬 알고리즘을 적용하려면 추가 전처리 또는 수정이 필요할 수 있습니다.

정렬 알고리즘을 선택할 때 입력 데이터의 세부 사항과 정렬 문제의 요구 사항을 신중하게 고려하는 것이 중요합니다. 선형 스케줄링 알고리즘은 특정 시나리오에서 이점을 제공하지만 때로는 가장 적절하거나 효율적인 선택일 때도 있습니다.

선형 시간 정렬 알고리즘의 응용

선형 시간 정렬 알고리즘은 효율적이며 다양한 분야에 많이 적용됩니다. 다음은 선형 시간 순서의 몇 가지 일반적인 응용 프로그램입니다.

작은 범위의 정수 정렬:카운트 정렬 및 기수 정렬과 같은 선형 시간 정렬 알고리즘은 값 범위가 다음과 같은 경우 정수 배열을 정렬하는 데 이상적입니다. 이러한 알고리즘은 입력 데이터에 대한 가정을 통해 선형 시간 복잡도를 달성하고 비교 기반 정렬을 우회할 수 있도록 합니다.문자열 정렬:선형 시간 정렬 알고리즘을 적용하여 문자열을 효율적으로 정렬할 수도 있습니다. 길이나 문자와 같은 문자열의 고유한 속성을 취함으로써 Radix Sort와 같은 알고리즘은 문자열을 정렬할 때 선형 시간 복잡도를 달성할 수 있습니다.데이터베이스 기능:정렬은 선형 시간 정렬 알고리즘의 필수 기능으로 특정 열이나 필드를 기반으로 대규모 데이터 세트를 효율적으로 정렬할 수 있습니다. 이를 통해 쿼리 처리 속도가 빨라지고 데이터베이스 작업 성능이 향상됩니다.히스토그램 만들기:히스토그램은 다양한 통계 및 데이터 분석 작업에 필수적입니다. 수치 정렬과 같은 선형 시간 정렬 알고리즘은 데이터 세트에서 요소의 발생을 효율적으로 계산하여 히스토그램을 생성할 수 있습니다.외부 정렬:외부 정렬 기술은 데이터가 메모리에 완전히 들어갈 수 없는 경우에 사용됩니다. 외부 기수 정렬(External Radix Sort) 또는 외부 계산 정렬(External Counting Sort)과 같은 선형 시간 정렬 알고리즘은 디스크나 기타 외부 저장 장치에 저장된 대규모 데이터 세트를 효율적으로 정렬할 수 있습니다.이벤트 일정:선형 시간 정렬 알고리즘은 시작 또는 종료 시간을 기준으로 이벤트를 예약할 수 있습니다. 이벤트를 오름차순으로 정렬하면 충돌, 겹치는 기간을 식별하거나 다음 사용 가능한 기간을 쉽게 찾을 수 있습니다.로그 파일 분석 중:로그 파일 분석은 시스템 관리 및 디버깅의 일반적인 작업입니다. 선형 시간 정렬 알고리즘을 사용하면 타임스탬프를 기준으로 로그를 정렬할 수 있으므로 패턴, 이상 징후를 식별하거나 특정 이벤트를 더 쉽게 검색할 수 있습니다.데이터 압축:정렬은 다양한 데이터 압축 기술에서 필수적인 역할을 합니다. BWT(Burrows-Wheeler Transform) 또는 MTF(Move-To-Front Transform)와 같은 알고리즘은 선형 시간 순서를 사용하여 데이터를 재배열하여 압축 효율성을 향상시킵니다. 이는 선형 시간 정렬 알고리즘을 적용한 몇 가지 예일 뿐입니다.

C++에서 선형 시간 정렬 구현

다음은 선형 시간 정렬 알고리즘인 Counting Sort를 구현하는 프로그램의 예입니다.

 #include #include using namespace std; void countingSort(vector&amp; arr) { // Find the maximum element in the array int max_val = *max_element(arr.begin(), arr.end()); // Create a count array to store the count of each element vector count(max_val + 1, 0); // Count the occurrences of each element for (int num : arr) { count[num]++; } // Compute the prefix sum for (int i = 1; i <count.size(); i++) { count[i] +="count[i" - 1]; } create a sorted output array vector output(arr.size()); place the elements in order for (int i="arr.size()" 1;>= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // Copy the sorted elements back to the original array for (int i = 0; i <arr.size(); i++) { arr[i]="output[i];" } int main() vector arr="{4," 2, 8, 3, 1}; sort the array using counting countingsort(arr); print sorted cout << 'sorted array: '; for (int num : arr) ' endl; return 0; < pre> <p> <strong>Sample Output</strong> </p> <pre> Sorted array: 1 2 2 3 3 4 8 </pre> <p>This indicates that the input array has been sorted in ascending order using the Counting Sort algorithm, resulting in the sorted array [1, 2, 2, 3, 3, 4, 8].</p> <p>In this C++ program, the counting sort function takes a reference to the vector arr and runs the counting sort routine. It finds the table&apos;s maximum value to determine the worksheet&apos;s size. It then counts each element&apos;s occurrence and calculates the worksheet&apos;s prefix sum. Then, it creates a result vector and puts the elements in order according to the worksheet. Finally, it copies the sorted elements back into the original array. In the primary function, the example array {4, 2, 2, 8, 3, 3, 1} is sorted by the enumeration sort algorithm and printed as a sorted matrix. Note that the program uses libraries to work with vectors and find the maximum element of an array using the max_element function.</p> <hr></arr.size();></count.size();>

이는 입력 배열이 Counting Sort 알고리즘을 사용하여 오름차순으로 정렬되어 정렬된 배열 [1, 2, 2, 3, 3, 4, 8]이 되었음을 나타냅니다.

이 C++ 프로그램에서 계수 정렬 함수는 벡터 arr에 대한 참조를 가져와 계수 정렬 루틴을 실행합니다. 워크시트의 크기를 결정하기 위해 테이블의 최대값을 찾습니다. 그런 다음 각 요소의 발생 횟수를 계산하고 워크시트의 접두사 합계를 계산합니다. 그런 다음 결과 벡터를 생성하고 워크시트에 따라 요소를 순서대로 배치합니다. 마지막으로 정렬된 요소를 원래 배열에 다시 복사합니다. 기본 함수에서 예제 배열 {4, 2, 2, 8, 3, 3, 1}은 열거형 정렬 알고리즘에 따라 정렬되고 정렬된 행렬로 인쇄됩니다. 프로그램은 라이브러리를 사용하여 벡터로 작업하고 max_element 함수를 사용하여 배열의 최대 요소를 찾습니다.