Shaker sort

개요

버블 소트 에서 부분 데이터가 오름차순으로 정렬되어 있어도 무조건 비교를 반복함으로 효율이 떨어진다. 따라서 데이터의 원쪽부터 검사를 시작해서 마지막으로 교환한 것이 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 // test whether the two elements are in the wrong order
        swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
        swapped := true
      end if
    end for
    if not swapped then
      // we can exit the outer loop here if no swaps occurred.
      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 // if no elements have been swapped, then the list is sorted
end procedure