[Algorithms] 셰이커 정렬(Shaker Sort)

깃 허브: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/Sorting%20algorithm.ipynb

GitHub - PSLeon24/DataStructure-Algorithms: Do it! 자료구조와 함께 배우는 알고리즘 입문(Python)

셰이커 정렬(Shaker Sort)

셰이커 정렬을 버블 정렬의 변형된 정렬 알고리즘 중 하나이다.

예를 들어, [9, 1, 3, 4, 6, 7, 8]와 같이 정렬이 거의 완료된 배열을 버블 정렬을 진행하면 어떤 결과가 나올까?

원솟값을 거의 정렬한 듯이 입력된 배열이지만 위의 실행 결과를 보면 원솟값을 총 21번 비교하고 교환은 6번을 진행하는 것으로 보아, 정렬 작업을 빠르게 마칠 수가 없다는 것을 확인할 수 있다.

왜냐하면 가장 큰 원소인 9가 배열의 맨 앞에 위치해 있어 한 패스에 한 칸씩 뒤로 이동하기 때문이다.

만약 가장 큰 원소인 9를 빠르게 맨 뒤로 이동시킨다면 작업 속도는 훨씬 빨라질 것이다.

과연 일반 버블 정렬을 했을 때보다 얼마나 빨라지는지 차이를 보기 위해 파이썬으로 실습한 결과를 확인해보자.

비교 횟수가 기존 21번에서 10번으로 감소했음을 확인할 수 있다.

 

이러한 idea를 적용해서 홀수 패스에서는 가장 작은 원소를 맨 앞으로 이동시키고, 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동시켜 패스의 스캔 방향을 번갈아 바꾸며 정렬하는 알고리즘을 셰이커 정렬(shaker sort)이라고 하며, 양방향 버블 정렬(bidrectional bubble sort), 칵테일 정렬(cocktail sort), 칵테일 셰이커 정렬(cocktail shaker sort)이라고도 한다.

 

정렬되는 과정은 아래와 같다.

https://en.wikipedia.org/wiki/File:Sorting_shaker_sort_anim.gif

정렬되는 과정을 이미지로 잘 살펴보면 좌우로 번갈아가며 값들이 fix되는 것을 확인할 수 있다.

 

임의의 배열 [23, 78, 45, 8, 32, 56]를 셰이커 정렬로 손 로직도 한번 돌려보면 아래와 같이 나타낼 수 있다.

총 6번의 패스를 거치며 홀수의 패스에서는 정렬되지 않은 원솟값 중에서 최솟값을 맨 앞에 fix하고, 짝수의 패스에서는 정렬되지 않은 원솟값 중에서 최댓값을 맨 뒤에 fix하는 과정을 거친다. 이 과정을 반복해서 최종적으로 fix된 값들을 연결시켜 보면 M 형태를 띄는 것도 확인할 수 있다.

 

위 배열도 버블 정렬을 수행했을 때와 셰이커 정렬을 수행했을 경우의 차이를 파이썬으로 실습한 결과를 통해 살펴보자.

1. 버블 정렬의 경우

 

2. 셰이커 정렬의 경우

 

최종적으로 버블 정렬로 정렬을 수행하는 경우 총 15번의 비교를 진행하지만 셰이커 정렬의 경우 6회로 감소했다는 점을 확인할 수 있다.