칵테일 셰이커 분류

칵테일 셰이커 분류

클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	${\displaystyle O(n^{2})\,}$
베스트 케이스 공연	$O(n)\,}$
평균 공연	${\displaystyle O(n^{2})\,}$
최악의 경우 공간 복잡성	${\displaystyle O(1)}$

칵테일 셰이커 ^[2]분류는 양방향 버블 분류, 칵테일 분류, 셰이커 분류(선택 분류의 변형도 참조할 수 있음), 리플 분류, 셔플 분류,^[3] 셔틀 분류라고도 하며 ^[1]버블 분류의 확장이다.알고리즘은 두 방향으로 작동하여 버블을 확장한다.목록의 시작 부분으로 항목을 더 빨리 이동시킴으로써 버블 정렬에서 개선되는 반면, 그것은 한계적인 성능 개선만을 제공한다.

대부분의 버블 종류와 마찬가지로, 칵테일 셰이커 종류도 주로 교육 도구로 사용된다.Python과 Java와 같은 인기 있는 프로그래밍 언어에 내장된 정렬 라이브러리에 의해 timsort 또는 merge sort와 같은 더 뛰어난 알고리즘이 사용된다.^[4][5]

가성음

가장 간단한 양식은 매번 전체 목록을 거친다.

만약 A[나는]> 절차 cocktailShakerSort(분류할 수 있는 항목의 A:목록):위조 각각 나는 0에서 − 2length(A)에:;A[나는 1+] 다음 시험 //는 두 요소의 잘못된 순서입니다 swap(A[나는], A[나는 1+])// 두가지를 이뤄 장소들을 서로 교환을 바꿀 수 있도록 해:)진정한 끝 끝나면을 포기하고 있다. 한다면만약 A[나는]> 다음 //지 않은 경우 스와프가 발생한 우리가 여기서 외부 루프를 빠져나갈 수 있다. 만약 바뀌do-while 루프 끝을 깨:위조 각각 나는 length(A)−에 2-0.;만약는 동안swapped을 끓여내내지 않은 경우 요소들을 서로 교환해 왔다 A[나는 1+] 다음 swap(A[나는], A[나는 1+]):)진정한 끝, 그때 바뀌고도 교체하지 않습니다. 그 목록이 종료 절차 정렬됨

첫 번째 우향 패스는 가장 큰 원소를 끝에 있는 정확한 위치로 이동시키고, 다음의 좌향 패스는 가장 작은 원소를 맨 앞에 있는 정확한 위치로 이동시킨다.두 번째 완전한 패스는 두 번째 가장 큰 요소와 두 번째 가장 작은 요소들을 올바른 위치로 이동시킬 것이다.내가 통과하면 목록의 첫 번째 i 요소와 마지막 i 요소가 올바른 위치에 있으므로 확인할 필요가 없다.매번 정렬되는 리스트의 부분을 줄임으로써, 운용 횟수를 절반으로 줄일 수 있다(버블 정렬 참조).

이것은 마지막 스왑 지수를 기억하고 한계를 업데이트하는 최적화를 가진 MATLAB/OCTAVE의 알고리즘의 예다.

반면 beginIdx<>)endIdxnewBeginIdx=endIdx,newEndIdx=beginIdx 기능 A)cocktailShakerSort(A)%`beginIdx`과 `endIdx`, endIdx)length(A)-1;ii에)beginIdx:A(ii)>, A(ii+1)[A(ii+1)A(ii)])deal(A(ii), A(ii+1). newEndIdx)ii, 끝%`end 끝을 감소시켜 endIdx 처음이자 마지막 지수=1beginIdx을 확인하는 것을 나타낸다.Idx` because the elements after `newEndIdx` are in correct order  endIdx = newEndIdx - 1;  for ii = endIdx:-1:beginIdx  if A(ii) > A(ii + 1)  [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));  newBeginIdx = ii;  end  end  % increases `beginIdx` because the elements before `newBeginIdx` are in correct order  beginIdx = newBeginIdx + 1; end end

버블 정렬과의 차이

칵테일 셰이커 종류는 버블 종류에 약간 변형된 것이다.^[1]리스트를 아래에서 위로 반복적으로 넘기는 대신 아래에서 위로, 위에서 아래로 번갈아 통과한다는 점에서 차이가 있다.그것은 표준 버블 종류보다 약간 더 나은 성능을 달성할 수 있다.그 이유는 버블 정렬이 목록을 한 방향으로만 통과하므로 반복할 때마다 항목을 한 단계 뒤로만 이동할 수 있기 때문이다.

이 점을 증명하는 리스트의 예로는 리스트(2,3,4,5,1)를 들 수 있는데, 칵테일 종류는 1회만 통과하면 분류되지만, 상승 버블 종류를 사용할 경우 4회 통과가 된다.그러나 하나의 칵테일 분류 패스는 두 개의 버블 분류 패스로 계산해야 한다.일반적으로 칵테일 종류는 버블 종류보다 2배 미만 빠르다.

또 다른 최적화는 알고리즘이 마지막 실제 스왑이 수행된 위치를 기억하는 것일 수 있다.다음 반복에서, 이 한계를 초과하는 스왑은 없을 것이며 알고리즘은 더 짧은 패스를 가진다.칵테일 셰이커 정렬이 양방향으로 진행되면서 테스트 대상 범위인 스와프 가능 범위가 패스당 감소해 전체 러닝 시간이 다소 줄어든다.

복잡성

빅 O 표기법으로 분류된 칵테일 셰이커의 복잡성은 최악의 경우나 평균적인 경우 $모두$ O${\displaystyle }$( n ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle$ O$(n^{2})}$이지만, 정렬 알고리즘을 적용하기 전에 목록이 대부분 순서가 되면 $O$${\displaystyle }$( n${\displaystyle }$) ${\displaystysty O(n)}$에 가까워진다.예를 들어, 모든 원소가 결국 들어갈 위치로부터 최대 k (k ≥ 1)로 다른 위치에 있다면, 칵테일 셰이커 분류의 복잡성은 $O{\displaystyle }$( ${\displaystyle k}$)${\displaystyle }$. ${\displaystyle O(kn$)가 된다$.$$}$

칵테일 셰이커 분류는 버블 분류의 유사한 정교함과 함께 "컴퓨터 프로그래밍의 기술"이라는 책에서도 간략하게 논의되고 있다.결론적으로 Knuth는 버블 종류와 그것의 개선에 대해 다음과 같이 말한다.

그러나 이러한 정교함들 중 어느 것도 직선 삽입[즉, 삽입 정렬]보다 더 나은 알고리즘을 이끌어내지 못한다.그리고 우리는 직선 삽입이 큰 N에 적합하지 않다는 것을 이미 알고 있다.[...] 요컨대, 거품 분류는 그것을 추천할 만한 것이 아무것도 없는 것처럼 보인다. 요컨대, 눈에 띄는 이름과 그것이 몇 가지 흥미로운 이론적인 문제로 이어진다는 사실 외에는.

— D. E. Knuth^[1]

참조

원천

• Hartenstein, R. (July 2010). "A new World Model of Computing" (PDF). The Grand Challenge to Reinvent Computing. Belo Horizonte, Brazil: CSBC. Archived from the original (PDF) on 2013-08-07. Retrieved 2011-01-14.

외부 링크

위키북 알고리즘 구현에 칵테일 정렬을 주제로 한 페이지가 있다.

• 칵테일 정렬의 대화형 데모
• Java 소스 코드와 칵테일 종류 애니메이션 데모(양방향 버블 종류라고 함) 및 기타 알고리즘 몇 가지
• ".NET Implementation of cocktail sort and several other algorithms". Archived from the original on 2012-02-12.