칵테일 셰이커 정렬(영어: cocktail shaker sort 칵테일 셰이커 소트[*])[1], 양방향 거품 정렬(영어: bidirectional bubble sort 비디렉셔널 버블 소트[*])[2] 또는 셰이커 정렬(영어: shaker sort 셰이커 소트[*])은 정렬 알고리즘 중 하나로, 버블 정렬의 변형이다.
알고리즘
버블 정렬과 다른 점은 버블 정렬은 배열을 앞부터 뒤까지 반복하며 두 수를 바꾸지만, 칵테일 정렬은 배열을 앞에서 뒤까지, 다음은 뒤에서 앞까지, 다음은 다시 앞에서 뒤까지 반복하는 식으로 순서만 다르다.
소스 코드
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;
}
}
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
}
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
각주
