[Algorithm] 정렬 - 칵테일 정렬(Cocktail Sort)

# 요약

• 버블 정렬의 파생형 정렬
  • 양방향 버블 정렬이 이루어진다.
• 마치 양쪽에서 흔드는것처럼 보여서 칵테일 혹은 쉐이커 정렬이라고 불린다.

 

# 구체적 설명

• 홀수 번째 돌때는 앞부터, 짝수번째를 돌때는 뒤부터 훑는다.
  • 제일  처음에 하나, 제일 뒤에하나, 다시 제일 앞에 하나를 정렬하면서 마치 정렬하는 과정이 앞뒤로 흔드는 것처럼 보인다.
• 1회전을 수행하고 나면 오름차순, 내림차순에 따라 자료가 정렬이 진행된다.

 

# 알고리즘

https://www.baeldung.com/cs/cocktail-sort

# 코드 작성 -  JAVA

import java.util.Arrays;

public class SortAlgorithm {
    static int[] arr = new int[]{7, 1, 3, 2, 4, 5, 6};

    public static void main(String[] args) {
        sortBubble(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sortBubble(int[] arr) {
        boolean isSwap; //교환 여부
        do {
            isSwap = false;
            for (int i = 0; i < arr.length - 2; i++) { //시작부터 순회
                if (arr[i] > arr[i + 1]) {
                    swap(i, i + 1);
                    isSwap = true; //교환 발생
                }
            }
            if (!isSwap) {
                break;
            }
            isSwap = false;
            for (int i = arr.length - 2; i >= 0; i--) { //끝부터 순회
                if (arr[i] > arr[i + 1]) {
                    swap(i, i + 1);
                    isSwap = true;
                }
            }
        } while (isSwap);
    }

    private static void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

# 결과

[1, 2, 3, 4, 5, 6, 7]

 

 

#시간복잡도

최선	O(n)
평균	O(n^2)
최악	O(n^2)

 

 

#장단점

장점	단점
양방향 순회로 일부의 경우 버블 정렬보다 빠르다. 어느정도 정렬된 배열에 대해서는, 비교적 적은 수의 순회로 정렬을 완료한다.	시간복잡도가 최악,평균 O(n^2)으로 굉장히 비효율 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 발생

---