맨위로가기

칵테일 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

칵테일 정렬은 버블 정렬의 변형 알고리즘으로, 배열을 양방향으로 번갈아 스캔하며 정렬한다. 버블 정렬과 달리, 칵테일 정렬은 배열을 앞에서 뒤로, 다시 뒤에서 앞으로 이동하며 정렬하는 과정을 반복한다. 칵테일 정렬은 최악 및 평균 시간 복잡도가 O(n2)이지만, 거의 정렬된 데이터에서는 O(n)에 가깝게 동작하여 삽입 정렬과 유사한 성능을 보인다. 알고리즘의 마지막 교환 위치를 기억하거나 스캔 범위를 좁히는 등의 최적화를 통해 성능을 향상시킬 수 있으며, C++, 파이썬, 스칼라 등 다양한 프로그래밍 언어로 구현될 수 있다.

더 읽어볼만한 페이지

  • 안정 정렬 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 안정 정렬 - 삽입 정렬
    삽입 정렬은 미정렬 부분의 원소를 정렬된 부분의 올바른 위치에 삽입하여 정렬을 완성하는 간단하고 효율적인 알고리즘이지만, 데이터 세트가 클수록 성능이 저하되어 이를 개선하기 위한 변형 알고리즘이 존재한다.
  • 비교 정렬 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 비교 정렬 - 퀵 정렬
    퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
  • 정렬 알고리즘 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 정렬 알고리즘 - 퀵 정렬
    퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
칵테일 정렬
개요
유형정렬 알고리즘
자료 구조배열
최선 시간 복잡도O(n)
평균 시간 복잡도O(n^2)
최악 시간 복잡도O(n^2)
공간 복잡도O(1)
최적화 여부아니오

2. 알고리즘

버블 정렬의 변형 알고리즘으로, 양방향으로 번갈아 가며 정렬을 수행한다.[1] 버블 정렬은 한 방향으로만 리스트를 통과하며 각 반복마다 항목을 한 단계씩 뒤로만 이동할 수 있지만, 칵테일 정렬은 양방향으로 리스트를 통과시켜 성능을 개선한다.

예를 들어, (2, 3, 4, 5, 1) 리스트는 칵테일 정렬을 사용하면 한 번의 통과로 정렬되지만, 오름차순 버블 정렬은 네 번의 통과가 필요하다. 칵테일 정렬 한 번은 버블 정렬 두 번으로 계산되는데, 일반적으로 칵테일 정렬은 버블 정렬보다 두 배 미만으로 빠르다.

알고리즘 최적화 방법 중 하나는 마지막으로 실제 교환이 수행된 위치를 기억하는 것이다. 다음 반복에서 이 한계를 넘어서는 교환은 없으므로 알고리즘은 더 짧은 통과를 하게 된다. 칵테일 정렬은 양방향으로 진행되므로, 가능한 교환 범위가 통과당 감소하여 전체 실행 시간을 줄일 수 있다.

버블 정렬에서 마지막 스캔 시 연속 m개 요소 교환이 없었다면, 해당 m개는 정렬 완료된 것으로 간주하여 다음 스캔 범위를 m만큼 좁힐 수 있다. 칵테일 정렬은 스캔 방향을 매번 반전시켜 스캔 범위를 앞뒤에서 좁힐 수 있다. 삽입 정렬처럼 거의 정렬된 데이터에 대해 빠르게 수행할 수 있다.

2. 1. 알고리즘 작동 방식

버블 정렬과 칵테일 정렬의 차이점은 버블 정렬은 배열을 앞에서 뒤까지 반복하며 두 수를 바꾸지만, 칵테일 정렬은 배열을 앞에서 뒤까지, 다음은 뒤에서 앞까지, 다시 앞에서 뒤까지 반복하는 방식으로 순서만 다르다는 것이다. 가장 단순한 형태는 매번 전체 목록을 훑는 것이다.

첫 번째 오른쪽 통과는 가장 큰 요소를 끝의 올바른 위치로 이동시키고, 그 다음 왼쪽 통과는 가장 작은 요소를 시작의 올바른 위치로 이동시킨다. 두 번째 완전한 통과는 두 번째로 크고 두 번째로 작은 요소를 올바른 위치로 이동시키는 식으로 진행된다. ''i'' 번의 통과 후, 목록의 처음 ''i''개 요소와 마지막 ''i''개 요소는 올바른 위치에 있으므로 확인할 필요가 없다. 매번 정렬되는 목록의 부분을 줄임으로써 연산 수를 절반으로 줄일 수 있다.

3. 소스 코드

칵테일 정렬의 가장 단순한 형태는 매번 전체 목록을 훑는 방식이다.

```

'''절차''' 칵테일정렬(A ''':'' 정렬 가능한 항목 목록) '''은'''

'''실행'''

바뀜 := 거짓

'''각''' i '''에 대해''' 0 '''부터''' 길이(A) − 1 '''까지:'''

'''만약''' A[i] > A[i + 1] '''이라면'''

바꾸기(A[i], A[i + 1])

바뀜 := 참

'''만약'''

'''끝'''

'''만약 그렇지 않다면''' 바뀜

'''반복-while 루프 중단'''

'''끝'''

바뀜 := 거짓

'''각''' i '''에 대해''' 길이(A) − 1 '''부터''' 0 '''까지:'''

'''만약''' A[i] > A[i + 1] '''이라면'''

바꾸기(A[i], A[i + 1])

바뀜 := 참

'''만약'''

'''끝'''

'''while''' 바뀜

'''절차 종료'''

```

첫 번째 오른쪽 순회는 가장 큰 요소를 끝의 올바른 위치로 이동시키고, 그 다음 왼쪽 순회는 가장 작은 요소를 시작의 올바른 위치로 이동시킨다. 두 번째 완전한 순회는 두 번째로 크고 두 번째로 작은 요소를 올바른 위치로 이동시키는 식으로 진행된다. ''i'' 번의 순회 후, 목록의 처음 ''i''개 요소와 마지막 ''i''개 요소는 올바른 위치에 있으며 확인할 필요가 없다. 매번 정렬되는 목록의 부분을 줄임으로써 연산 수를 절반으로 줄일 수 있다 (버블 정렬 참조).

다음은 마지막 교환 인덱스를 기억하고 범위를 업데이트하는 최적화를 사용한 MATLAB/OCTAVE의 알고리즘 예시이다.

```matlab

function A = 칵테일정렬(A)

% `beginIdx`와 `endIdx`는 확인할 첫 번째 및 마지막 인덱스를 표시합니다.

beginIdx = 1;

endIdx = length(A) - 1;

while beginIdx <= endIdx

newBeginIdx = endIdx;

newEndIdx = beginIdx;

for ii = beginIdx:endIdx

if A(ii) > A(ii + 1)

[A(ii+1), A(ii)] = deal(A(ii), A(ii+1));

newEndIdx = ii;

end

end

% `endIdx`를 감소시킵니다. `newEndIdx` 이후의 요소는 올바른 순서입니다.

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

% `beginIdx`를 증가시킵니다. `newBeginIdx` 이전의 요소는 올바른 순서입니다.

beginIdx = newBeginIdx + 1;

end

end

3. 1. C++

cpp

template

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;

}

}

```

C++ 언어로 구현된 예시는 다음과 같다.

```cpp

#include // std::swap

template

void shaker_sort(T data[], int num_elements)

{

int top_index = 0;

int bot_index = num_elements - 1;

while (true)

{

int last_swap_index;

/* 순방향 스캔 */

last_swap_index = top_index;

for (int i = top_index; i < bot_index; i++)

{

if (data[i] > data[i + 1])

{

std::swap(data[i], data[i + 1]);

last_swap_index = i;

}

}

bot_index = last_swap_index; /* 후방 스캔 범위를 좁힘 */

if (top_index == bot_index)

break;

/* 역방향 스캔 */

last_swap_index = bot_index;

for (int i = bot_index; i > top_index; i--)

{

if (data[i] < data[i - 1])

{

std::swap(data[i], data[i - 1]);

last_swap_index = i;

}

}

top_index = last_swap_index; /* 전방 스캔 범위를 좁힘 */

if (top_index == bot_index)

break;

}

}

3. 2. 파이썬

python

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

3. 3. 스칼라

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

}

4. 성능

칵테일 정렬의 점근 표기법에서의 복잡도는 최악의 경우와 평균적인 경우 모두 O|오영어(n2)이지만, 정렬 알고리즘을 적용하기 전에 목록이 대부분 정렬된 상태라면 O|오영어(n)에 더 가까워진다. 예를 들어, 모든 요소가 최종적으로 위치하게 될 위치와 최대 k (k ≥ 1)만큼만 다른 위치에 있다면, 칵테일 정렬의 복잡도는 O|오영어(kn)이 된다.[1]

칵테일 정렬은 양방향으로 진행되므로, 테스트할 범위인 가능한 교환 범위가 통과당 감소하여 전체 실행 시간을 약간 줄인다.

버블 정렬은 1회 스캔을 수행하면 마지막 요소 1개가 스캔 범위 내에서 최대값임을 알 수 있으며, 다음 스캔 범위를 1만큼 좁힐 수 있다. 또한, 이 스캔의 마지막에서 연속적으로 m개의 요소 교환이 일어나지 않았다면, 해당 m개는 정렬 완료된 것으로 간주하여 다음 스캔 범위를 m만큼 좁힐 수 있다. 이 방식을 통해 후반부가 거의 정렬된 데이터에 대해 버블 정렬을 빠르게 수행할 수 있다.[1]

셰이커 정렬은 여기에 더하여 스캔 방향을 매번 반전시킴으로써, 스캔 범위를 뒤쪽뿐만 아니라 앞쪽에서도 좁힐 수 있도록 하였다. 삽입 정렬과 같이, 거의 정렬된 데이터에 대해서는 빠르게 수행할 수 있다.

5. 최적화

칵테일 정렬의 최적화 방법 중 하나는 마지막으로 실제 교환이 일어난 위치를 기억하는 것이다.[1] 이를 통해 다음 반복에서 그 위치를 넘어서는 교환은 일어나지 않으므로, 알고리즘은 더 짧은 구간을 탐색하게 된다. 칵테일 정렬은 양방향으로 진행되기 때문에, 탐색 범위, 즉 가능한 교환 범위가 반복마다 줄어들어 전체 실행 시간을 단축시킨다.

버블 정렬에서 한 번의 스캔으로 마지막 요소가 스캔 범위 내 최댓값임을 알 수 있으므로, 다음 스캔 범위를 1만큼 줄일 수 있다. 또한, 스캔 마지막에 연속적으로 m개의 요소 교환이 없었다면, 그 m개의 요소는 이미 정렬된 것으로 간주하여 다음 스캔 범위를 m만큼 줄일 수 있다. 이러한 최적화를 통해 후반부가 거의 정렬된 데이터에 대해 버블 정렬을 빠르게 수행할 수 있다.

6. 다른 정렬 알고리즘과의 비교

칵테일 셰이커 정렬은 버블 정렬의 변형이다.[1] 버블 정렬은 배열을 앞에서 뒤로 반복하며 두 수를 바꾸지만, 칵테일 정렬은 양방향으로 번갈아 가며 배열을 훑는다는 차이점이 있다. 이러한 방식은 특정 상황에서 버블 정렬보다 약간 더 나은 성능을 낼 수 있다. 예를 들어, (2, 3, 4, 5, 1)과 같은 리스트는 칵테일 정렬을 사용하면 한 번에 정렬되지만, 오름차순 버블 정렬을 사용하면 네 번의 과정이 필요하다. 그러나 칵테일 정렬 한 번은 버블 정렬 두 번으로 계산해야 하므로, 일반적으로 칵테일 정렬은 버블 정렬보다 두 배 미만으로 빠르다.

칵테일 정렬은 마지막으로 실제 교환이 수행된 위치를 기억하여 다음 반복에서 그 범위를 좁히는 최적화를 적용할 수 있다. 양방향으로 진행되기 때문에, 가능한 교환 범위가 줄어들어 전체 실행 시간을 단축시킨다.

점근 표기법에서 칵테일 정렬의 복잡도는 최악의 경우와 평균적인 경우 모두 O(n^2)이지만, 정렬 전에 목록이 대부분 정렬된 상태라면 O(n)에 가까워진다.

삽입 정렬과 마찬가지로, 칵테일 셰이커 정렬은 거의 정렬된 데이터에 대해 빠른 성능을 보인다.[1]

참조

[1] 서적 Art of Computer Programming Addison-Wesley 1973
[2] 서적 Dictionary of Algorithms and Data Structures http://xlinux.nist.g[...] National Institute of Standards and Technology 2010-02-05
[3] 서적 HYPERKARL aus der Algorithmischen Darstellung des BUBBLE-SORT-ALGORITHMUS Technical University of Kaiserslautern
[4] 웹사이트 "[JDK-6804124] (coll) Replace ""modified mergesort"" in java.util.Arrays.sort with timsort - Java Bug System" https://bugs.openjdk[...] 2020-01-11
[5] 웹사이트 "[Python-Dev] Sorting" https://mail.python.[...] 2020-01-11
[6] 웹사이트 シェーカーソートの意味 https://dictionary.g[...] goo辞書
[7] 서적 Art of Computer Programming Addison-Wesley 1973
[8] 서적 Dictionary of Algorithms and Data Structures http://xlinux.nist.g[...] National Institute of Standards and Technology 2009-08-24


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com