계수정렬

• 이전의 대소를 비교하여 정렬했던 방법과는 다른 분포기반 정렬 방식이다.
• 특정 조건만 만족한다면 더 효율적인 알고리즘이 될 수 있다.

• 영문알파벳 또한 26개이기 때문에 1~26으로 키값을 정해서 계수정렬을 할 수 있다.
• A에서 배열이 정의되었다.
• N에서 각 수의 빈도수가 정의된다.
• 그 아래 N은 누적 빈도수가 정의된다.
• B는 빈도수에 따른 정렬된 배열이다.

• 배열 A의 역순으로 탐색한다.
• 4에 해당하는 누적빈도수값은 6이므로 배열 B의 6번째에 4를 배치한다.
• 이후 4의 누적빈도수를 -1 한다.
  
• 배열 A의 다음 수는 1이고, 1의 누적빈도수는 2이므로 배열 B의 두번째에 위치한다.
• 이후 마찬가지로 1의 누적빈도수 -1 한다.
• 이 과정을 계속 반복한다.

기수정렬

• 계수정렬과 마찬가지로 분포기반 정렬이다.
• 계수정렬의 특수한 조건에서 응용버전이다.
• 계수정렬과 같이 키값이 작은 범위가 아닌 큰 범위일 때 사용한다.

• 전체 키를 각 자리수로 나누어 일의자리부터 비교를 시작한다
• 일의자리가 작은수 부터 다시 재배열한다. 이때 동일한 키값이라면 기존의 순서를 유지한다 ( = 안정 정렬)
• 이후 다시 십의자리를 비교해서 작은 수부터 재배열한다. 이때 배열을 보면 십의자리까지의 값이 오름차순으로 정렬되어 있다. ]
• 다시 백의자리를 비교해서 작은 수부터 재배열한다.
• 최종적으로 오름차순으로 정렬된다 .

버킷정렬

• 위의 정렬들과 마찬가지로 분포기반 정렬이다.

• a과정에서는 각 확률에 데이터 개수를 곱하여 특정 키값에 배치시킨다.
• 동일한 키값에 배치된다면 순서를 유지하면서 배치한다. 이때 두 값을 연결리스트로 연결시킨다.
• b과정에서는 값이 두개이상인 노드들에 한해서 노드안에서 삽입정렬등과 같은 안정된 정렬을 이용하여 정렬시킨다
• b과정이 완료되면 값이 존재하지않는 노드는 건너뛰고 존재하는 노드는 끝까지 읽어 배열시킨다.

• 배열 A는 0과 1 사이에서 정규화되어 있다고 가정

정렬 응용 문제

• 지금까지 배워온 정렬 알고리즘들을 이용하여 문제를 해결하는 법을 배울 것이다.

선택 문제

임의로 나열된 n개의 데이터에서 크기가 i번째인 것을 찾는 문제

• i=1 : 최소치 문제 , O(n)시간
• i=n : 최대치 문제 , O(n)시간
• 일반적인 경우 - 정렬 후 i번째 원소 선택
  -> O(nlogn)시간, 평균도 Ω(nlogn)

• 최대나 최소를 찾는 문제는 일반적으로 O(n)

• 최대와 최소를 동시에 찾는 문제는 인덱스를 2만큼 증가시키면서 한번 반복문에서 두개의 인덱스를 비교한다면 같은 O(n)이라도 효율적으로 해결할 수 있다.

• 퀵정렬의 Partition함수를 이용하여 중간에 위치한 값을 기준으로 찾고자하는 값이 중간보다 왼쪽에 위치한다면 중간을 기준으로 오른쪽에 있는 값들은 배제한다. 마찬가지로 찾고자하는 값이 중간보다 오른쪽에 위치한다면 중간을 기준으로 왼쪽에 있는 값들은 배제한다.
  = 마치 이분탐색과 비슷하다.
• 평균시간 복잡도는 매우 줄었지만, 최악시간 복잡도는 여전히 O(n2)이다.

• 위에서의 최악의 경우는 Partition의 결과가 항상 하나의 배열로만 나뉘는 것이다. 즉, 오른쪽 / 왼쪽 그룹 두가지가 나와야하는데 항상 하나의 그룹만 나오는 경우이다.

• 각 그룹의 내부에서 정렬을 수행한다.

• 각 그룹의 내부에서 정렬을 수행한 후 중간값을 보게되면 정렬이 되어있지 않은 상태이다. 따라서 중간 값들을 기준으로 오름차순 정렬을 하게되는데 이때 값을 바꿔야 한다면 그룹 자체를 바꿔야 한다.

• 중간값의 중간값인 mm값이 도출된다. 이 mm값을 Partition함수의 분할원소로 사용하게되면 반드시 mm값을 기준으로 오른쪽 / 왼쪽 그룹이 생긴다. 즉, 한쪽 그룹만으로 분할되는 최악의 경우가 발생하지 않는다.