Shaker sort 문서 원본 보기

[[분류: 정렬]]
[[파일:Shaker Sort.gif|섬네일|가운데]]

== 개요 ==
[[버블 소트]] 에서 부분 데이터가 오름차순으로 정렬되어 있어도 무조건 비교를 반복함으로 효율이 떨어진다. 따라서 데이터의 원쪽부터 검사를 시작해서 마지막으로 교환한 것이 i 와 i + 1 의 위치라면 i + 1 ~ n - 1 까지는 데이터가 정렬되어 있는 것임으로 다음부터는 검사하지 않아도 된다. 따라서 마지막에 교환을 수행한 위치를 저장해 두고 다음 번 검사에서 범위로 이용하면 된다. 그러나 만일 오른쪽 끝 부분에 작은 값이 있다면 마지막 교환은 항상 데이터의 뒷부분에서 수행하게 됨으로 이러한 장점이 줄어든다. 따라서 검사를 왼쪽과 오른쪽 양쪽 방향에서 수행하도록 한다. 쉽게 설명하자면, 우선은 큰거 올리고, 그다음은 작은거 내리고 그다음 큰거 올리고... 께속

== 의사코드 ==

 '''procedure''' cocktailShakerSort( A ''':''' list of sortable items ) '''defined as:'''
   '''do'''
     swapped := false
     '''for each''' i '''in''' 0 '''to''' length( A ) - 2 '''do:'''
       '''if''' A[ i ] > A[ i + 1 ] '''then''' <span style="color:green">// test whether the two elements are in the wrong order</span>
         swap( A[ i ], A[ i + 1 ] ) <span style="color:green">// let the two elements change places</span>
         swapped := true
       '''end if'''
     '''end for'''
     '''if not''' swapped '''then'''
       <span style="color:green">// we can exit the outer loop here if no swaps occurred.</span>
       '''break do-while loop'''
     '''end if'''
     swapped := false
     '''for each''' i '''in''' length( A ) - 2 '''to''' 0 '''do:'''
       '''if''' A[ i ] > A[ i + 1 ] '''then'''
         swap( A[ i ], A[ i + 1 ] )
         swapped := true
       '''end if'''
     '''end for'''
   '''while''' swapped <span style="color:green">// if no elements have been swapped, then the list is sorted</span>
 '''end procedure'''