알고리즘 서론 상세 해석 (7) 제8 장 선형 정렬 알고리즘

모든 비교 순 서 는 최 악의 경우 에 거 쳐 야 한다.Θ(nlgn) 차 비교.
본 고 는 세 가지 선형 시간 정렬 알고리즘 을 소개 한다. 계수 정렬, 기수 정렬 과 통 정렬 이다.따라서 이들 은 모두 비교 정렬 에 속 하지 않 는 다.
본 논문 의 모든 실현 코드 는 GitHub 에 놓 여 있 습 니 다. 보 시 는 것 을 환영 합 니 다: GitHub 링크
본 장 개술
비교 정렬 이란 비교 되 지 않 은 조작 으로 정렬 순 서 를 정 하 는 정렬 알고리즘 을 말 하 며, 비교 되 지 않 은 정렬 에 대해 서 는 하계 O (nlgn) 가 적용 되 지 않 습 니 다.
계수 정렬 은 안정 적 인 정렬 입 니 다. n 개 데이터 의 수치 범위 가 [0..k] 이면 운행 시간 은 O(n+k) 이 고 운행 공간 은 O(n+k) 입 니 다.
기수 정렬 도 안정 적 인 정렬 이 므 로 다른 안정 적 인 정렬 을 바탕 으로 해 야 합 니 다. n 개의 d 자릿수 가 있 으 면 한 사람 당 k 가지 수치 가 있 을 수 있 습 니 다. 사용 하 는 안정 적 인 정렬 운행 시간 은 O(n+k) 이 고 기수 정렬 시간 은 O(d(n+k)) 입 니 다.
통 정렬 도 안정 적 인 정렬 이 고 입력 데이터 가 균일 한 분포 에 부합 할 때 통 정렬 은 선형 시간 으로 운행 할 수 있다.설 치 된 모든 원 소 는 구간 [0,1) 에 골 고루 분포 하고 구간 [0, 1) 을 n 개의 같은 크기 의 서브 구간 (통) 으로 나 누 어 각 통 의 수 를 정렬 하여 각 통 의 원 소 를 순서대로 나열 한다.
계수 정렬 (8.2, P108)
계수 정렬 counting sort 은 입력 요소 의 실제 값 을 사용 하여 배열 에 있 는 위 치 를 확인 하 는 것 입 니 다.
계수 정렬 의 중요 한 특징 중 하 나 는 안정 적 인 것 입 니 다. 즉, 같은 값 의 요소 가 출력 배열 에서 의 상대 적 인 순 서 는 입력 배열 에서 의 상대 적 인 순서 와 같 습 니 다. 즉, 두 개의 같은 숫자 에 대해 서 는 입력 배열 에서 먼저 나타 나 는 수 는 지 는 배열 에서 도 앞 에 있 습 니 다.
계수 정렬 의 위조 코드:

COUNTING_SORT(A,B,k)
      for i=0 to k
        do C[i] = 0
      for j=1 to length(A)
          do C[A[j]] = C[A[j]]+1   //C[i]       i   
      for i=1 to k
          do C[i] = C[i] + C[i-1]  //C[i]         i   
      for j=length[A] downto 1
          do B[C[A[j]]] = A[j]
             C[A[j]] = C[A[j]] -1

계수 정렬 Python 구현:

# Author：wangwlj
#     
def counting_sort(A):
    k = max(A)  # k is max of A
    C = []
    for i in range(0, k + 1):
        C.append(0)
    for j in range(0, len(A)):
        C[A[j]] = C[A[j]] + 1
    for i in range(1, k + 1):
        C[i] = C[i] + C[i - 1]

    B = []  # output
    for i in range(0, len(A)):
        B.append(0)
    for j in range(len(A) - 1, -1, -1):
        # m = A[j],n  = C[m],k = B[n - 1]  # for test
        B[C[A[j]] - 1] = A[j]  # B[n] start from 0, so need -1
        C[A[j]] = C[A[j]] - 1
    return B

if __name__ == "__main__":

    A = [2, 5, 3, 0, 2, 3, 0, 3]
    B = counting_sort(A)
    for i in range(0, len(B)):
        print(B[i], end=" ")

연습COUNTING_SORT 과정 에서 네 번 째 for 순환 은 왜 for j=length[A] downto 1 이지 for j=1 to length[A] 가 아 닙 니까?
알고리즘 이 안정 적 임 을 보장 하기 위해 서 입 니 다. 뒤로 가서 정렬 하 는 것 이기 때문에 두 수가 같 을 때 계수 값 이 큰 수 는 배열 의 뒤쪽 요소 에 대응 하기 때문에 출력 할 때 역순 이 필요 합 니 다.
기수 정렬 (8.3, P110)
기수 정렬 radix sort 은 유효 위치 에 따라 낮은 것 에서 높 은 것 으로 순서대로 정렬 합 니 다.
의사 코드 는 다음 과 같 습 니 다:

RADIX_SORT(A,d）
    for i=1 to d
          use a stable sort to sort array A on digit i

기수 정렬 은 일반적으로 계수 정렬 을 중간 안정 정렬 으로 한다.
기수 정렬 python 실현 은 아래 연습 문제 8.3-4 를 참조 하 시기 바 랍 니 다.
연습
설명 RADIX-SORT 다음 과 같은 영어 단어 에서 의 조작 과정:

    A = {COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX}  
==> A = {SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX}  
==> A = {TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUB}  
==> A = {BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, TAB, TAR, TEA, SEA, RUB} 

연습
제목: O(n) 시간 내 에 [0..n^3-1] 사이 의 n 개의 정 수 를 정렬 합 니 다.
사고: 정 수 를 n 진법 으로 바 꾸 고 정렬 합 니 다. 각 수 는 세 자리 가 있 습 니 다. 각 비트 의 수치 범 위 는 [0. n - 1] 이 고 기수 정렬 을 합 니 다.
실현:

import random

n = 5
base_k = 5  # bask could be any number. In test 8.3-4 is 5(equal to n)
d = 3  # 8.3-4


def stable_sort(A, index):  # similar with counting sort,
    C = []  # C：           k     
    for i in range(0, base_k + 1):  # the number is in range of base_k（k）
        C.append(0)
    for j in range(0, len(A)):
        #              
        num = int(A[j] % pow(base_k, index) / pow(base_k, index - 1))  # the base number
        # print(A[j], '      ：', index, '   ：', num, )  # for test
        C[num] = C[num] + 1  # the count of the base number (C - num)
    for i in range(1, base_k + 1):
        C[i] = C[i] + C[i - 1]

    B = []  # output
    for i in range(0, len(A)):
        B.append(0)
    for j in range(len(A) - 1, -1, -1):
        num = int(A[j] % pow(base_k, index) / pow(base_k, index - 1))
        B[C[num] - 1] = A[j]  # B[n] start from 0, so need -1
        C[num] = C[num] - 1
    return B


def radix_sort(A):
    for i in range(1, d + 1):
        A = stable_sort(A, i)
    # for i in range(0, len(A)):
    #     print(A[i], end=' ')
    return A


if __name__ == "__main__":

    # A = [114, 18, 35, 74, 36]
    A = []
    for i in range(0, n):
        A.append(random.randint(0, pow(n, 3)))

    for i in range(0, len(A)):
        print(A[i], end=' ')
    print('
')

    A = radix_sort(A)
    print('After radix_sort：')
    for i in range(0, len(A)):
        print(A[i], end=' ')

통 정렬 (8.4, P112)
통 정렬 bucket sort입력 데이터 가 균일 한 분포 에 따른다 고 가정 하면 평균 적 인 상황 에서 시간 대 가 는 On 이 고 계수 정렬 과 유사 하 다. 입력 데이터 에 대해 특정한 가설 을 했 기 때문에 통 정렬 의 속도 도 빠르다. 구체 적 으로 계산 정렬 가설 입력 데 이 터 는 모두 한 동네 간 의 정수 에 속 하고 통 정렬 은 입력 이 무 작위 과정 에서 발생 한다 고 가정 한다. 이 과정 은 요 소 를 균일 하고 독특 하 게 한다.입 지 는 [0, 1) 구간 에 분포 한다.
참고 자료
1. 알고리즘 서론 중국어 제3 판 2. 알고리즘 서론 제8 장 선형 시간 정렬 이것 은 연습 문제 의 답 을 포함 하고 좋 습 니 다. 3. 알고리즘 서론 8.3 - 4 4. MIT 알고리즘 서론 - 제5 강 - 선형 시간 정렬