스투지 분류
Stooge sort 스투지 정렬 시각화(스왑만 표시) | |
| 클래스 | 정렬 알고리즘 |
|---|---|
| 데이터 구조 | 배열 |
| 최악의 경우 공연 | O(nlog 3/log 1.5) |
| 최악의 경우 공간 복잡성 | O(n) |
스투지 정렬은 재귀 정렬 알고리즘이다.O(nlog 3 / log 1.5 ) = O(n2.7095...)의 예외적으로 나쁜 시간 복잡성으로 유명하다.따라서 알고리즘의 실행 시간은 합리적인 분류 알고리즘에 비해 느리고, 상당히 비효율적인 분류의 표준적인 예인 버블 분류보다 느리다.그러나 그것은 Slowsort보다 더 효율적이다.그 이름은 The Three Stooges에서 왔다.[1]
알고리즘은 다음과 같이 정의된다.
- 시작 부분의 값이 끝의 값보다 크면, 그것들을 교환한다.
- 목록에 3개 이상의 요소가 있는 경우:
- 목록의 초기 2/3 정렬
- 목록의 최종 2/3을 정렬하는 스투지
- 목록의 초기 2/3을 다시 정렬
2/3을 위쪽으로 반올림하여 재귀 호출에 사용되는 정수 정렬 크기를 얻는 것이 중요하다. 예를 들어, 5의 반올림 2/3은 3이 아니라 4가 되어야 한다. 그렇지 않으면 특정 데이터에서 정렬이 실패할 수 있기 때문이다.
실행
기능을 하다 호들갑 떨다(배열하다 L, i = 0, j = 길이(L)-1){ 만일 L[i] > L[j] 그때 // 가장 왼쪽 요소가 가장 오른쪽 요소보다 큰 경우 L[i] ↔ L[j] // 가장 왼쪽 요소와 가장 오른쪽 요소 교체 만일 (j - i + 1) > 2 그때 // 배열에 최소 3개의 요소가 있는 경우 t = 마루를 깔다((j - i + 1) / 3) 호들갑 떨다(L, i , j-t) // 어레이의 처음 2/3 정렬 호들갑 떨다(L, i+t, j) // 어레이의 마지막 2/3 정렬 호들갑 떨다(L, i , j-t) // 어레이의 처음 2/3을 다시 정렬 돌아오다 L } 참조
원천
- Black, Paul E. "stooge sort". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 18 June 2011.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Problem 7-3". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 161–162. ISBN 0-262-03293-7.
