칵테일 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox Algorithm
|class=[[정렬 알고리즘]]
|image=[[파일:Sorting shaker sort anim.gif|칵테일 정렬 시각화]]
|data=[[배열]]
|best-time= <math>O(n)\,</math>
|average-time= <math>O(n^2)\,</math>
|time=<math>O(n^2)\,</math>
|space=<math>O(1)</math>
|optimal=아니오
}}
'''칵테일 셰이커 정렬'''({{llang|en|cocktail shaker sort|칵테일 셰이커 소트}})<ref name="Knuth">{{서적 인용|title=Art of Computer Programming|edition=1st|pages=110–111|last=Knuth|first=Donald E.|authorlink=Donald Knuth|volume=3. Sorting and Searching|chapter=Sorting by Exchanging|publisher=[[Addison-Wesley]]|date=1973|isbn=0-201-03803-X}}</ref>, '''양방향 거품 정렬'''({{llang|en|bidirectional bubble sort|비디렉셔널 버블 소트}})<ref>{{서적 인용|first=Paul E.|last=Black|first2=Bob|last2=Bockholt|url=http://xlinux.nist.gov/dads/HTML/bidirectionalBubbleSort.html|chapter=bidirectional bubble sort|title=Dictionary of Algorithms and Data Structures|editor1-first=Paul E.|editor1-last=Black|publisher=[[National Institute of Standards and Technology]]|date=24 August 2009|accessdate=5 February 2010|보존url=https://web.archive.org/web/20130316180005/http://xlinux.nist.gov/dads//HTML/bidirectionalBubbleSort.html|보존날짜=2013-03-16|url-status=dead}}</ref> 또는 '''셰이커 정렬'''({{llang|en|shaker sort|셰이커 소트}})은 [[정렬 알고리즘]] 중 하나로, [[버블 정렬]]의 변형이다.

== 알고리즘 ==
{{참고|버블 정렬#알고리즘|버블 정렬#예시}}
버블 정렬과 다른 점은 버블 정렬은 배열을 앞부터 뒤까지 반복하며 두 수를 바꾸지만, 칵테일 정렬은 배열을 앞에서 뒤까지, 다음은 뒤에서 앞까지, 다음은 다시 앞에서 뒤까지 반복하는 식으로 순서만 다르다.

== 소스 코드 ==
=== [[C++]] ===
<syntaxhighlight lang="cpp">
template 〈typename BidirectionalIterator〉
void cocktailShaker(BidirectionalIterator first, BidirectionalIterator last)
{
    BidirectionalIterator shift = first;
    BidirectionalIterator i;

    while (first < last) {
        i = first;
        while (++i < last) {        // [shift, last)
            if (*i < *(i-1)) {
                std::iter_swap(i, i-1);
                shift = i;
            }
        }
        last = shift;

        i = last;
        while (--i > first) {        // (shift, first]
            if (*i < *(i-1)) {
                std::iter_swap(i, i-1);
                shift = i;
            }
        }
        first = shift;
    }
}
</syntaxhighlight>

=== [[스칼라]] ===
<syntaxhighlight lang="scala">
def cocktailShaker(arr: Array[Int]):Array[Int] =  {

  var i = 0
  var tmp = 0
  var lastIdx = arr.length - 1
  var swapped  = true

  do {
      println("i:"+i)

      if (swapped) {
        for (j <- i to lastIdx-i-1) {
          if (arr(j) > arr(j+1)) {
            tmp = arr(j+1)
            arr(j+1) = arr(j)
            arr(j) = tmp
            swapped = true
          }
        }
        arr.map(x=> print(x+" "))
        println
      }

      if (swapped) {
       swapped = false

        for (j <- lastIdx-i-1 to i by -1) {
          if (arr(j) > arr(j+1)) {
            tmp = arr(j+1)
            arr(j+1) = arr(j)
            arr(j) = tmp
            swapped = true
          }
        }

        arr.map(x=> print(x+" "))
        println
      }

      i = i + 1

  } while (swapped)

  arr
}
</syntaxhighlight>

=== [[파이썬]] ===
<syntaxhighlight lang="python3" line="1">
def cocktailShaker(arr):
    
    lastIdx = len(arr) - 1
    swapped  = True
    i = 0

    while swapped: 
        swapped = False
        for j in range(i, lastIdx-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True

        if swapped:
            for j in reversed(range(i, lastIdx-i)):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swapped = True
        
        i = i + 1
    return arr
</syntaxhighlight>

== 각주 ==
{{각주}}

{{정렬 알고리즘}}
{{토막글|컴퓨터 과학}}

[[분류:정렬 알고리즘]]
[[분류:안정 정렬]]
[[분류:비교 정렬]]