자료구조(정렬 알고리즘) - 칵테일 정렬(Cocktail shaker Sort)

안녕하세요,

츄르 사려고 코딩하는 집사! 코집사입니다.

버블 정렬에 이어 버블 정렬에서 파생된 칵테일 정렬에 대해 글을 쓰려고 합니다.

칵테일 정렬(cocktail shaker sort)이란??

버블 정렬(Bubble Sort)에서 파생된 것으로, 각 노드들을 비교를 하여 자리를 바꾸는게 버블 정렬입니다.

이 버블 정렬에 양방향으로 이동을 하면서, 현재 위치에 있는 노드와 옆에 있는 노드를 비교하여 자리를 바꾸는 것이 칵테일 정렬이다. 즉, 칵테일을 만들 때, 위아래로 흔들거나 양 옆으로 움직여서 칵테일 정렬이라고 부릅니다.

버블 정렬은 한 방향으로 처리를 하지만, 칵테일 정렬은 양 방향으로 처리를 하여 버블 정렬보다 속도가 빠릅니다.

칵테일 정렬은 셰이커 정렬(shaker Sort)라고도 부르고, 양방향 버블 정렬(Bidirectional Bubble Sort)라고도 부릅니다.

칵테일 정렬의 시간복잡도

최악, 평균 복잡도는 O(n^2)를 가지고, 최상 복잡도는 O(n)을 가집니다.