[알고리즘] 셰이커 정렬, 파이썬 내장 함수

셰이커 정렬이란? 

버블 정렬을 개선한 알고리즘으로, 양방향 버블 정렬, 칵테일 정렬, 칵테일 셰이커 정렬이라고도 부른다.

 

지난 글(https://vibeee.tistory.com/29)에서 버블 정렬로 3가지 코드를 살펴보았다.

하지만 가장 큰 값이 맨 앞에 있는 경우 3가지 코드 모두 비효율적인 정렬 과정을 수행하는 것을 알 수 있었다.

 

다음 코드에서는 이 부분을 셰이커 정렬로 개선한 코드를 살펴본다.

from typing import MutableSequence

def shaker_sort(a: MutableSequence) -> None:
    left = 0
    right = len(a) - 1
    last = right
    while left < right: # 오른쪽이 왼쪽보다 큰 경우 교환
        for j in range(right, left, -1): # 원소를 맨 뒤에서 맨 앞으로 스캔
            if a[j - 1] > a[j]: # 앞의 값이 뒤보다 큰 경우에 교환
                a[j - 1], a[j] = a[j], a[j - 1]
                last = j # 가장 작은 원소를 last에 저장
        left = last # left에 last(가장 작은 원소)를 저장

        for j in range(left, right): # 원소를 맨 앞에서 맨 뒤로 스캔
            if a[j] > a[j + 1]: # 앞의 값이 뒤보다 큰 경우에 교환
                a[j], a[j + 1] = a[j + 1], a[j]
                last = j # 가장 작은 원소를 last에 저장
        right = last # right에 last(가장 작은 원소)를 저장  

if __name__ == "__main__":
    print("버블 정렬을 수행합니다.")
    num = int(input("원소 수를 입력하세요.: "))
    x = [None] * num # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f"x[{i}]: "))

    shaker_sort(x) # 배열 x를 버블 정렬

    print("오름차순으로 정렬했습니다.")
    for i in range(num):
        print(f"x[{i}] = {x[i]}")

 

실행 결과

버블 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 9
x[1]: 1
x[2]: 3
x[3]: 4
x[4]: 6
x[5]: 7
x[6]: 8
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9

Process finished with exit code 0

 

위 코드를 실행하면 비교 횟수가 21->15번으로 감소하여 효율적으로 정렬하여 연산 횟수를 줄일 수 있다.

원소의 값이 적을때는 얼마 차이 안날 수 있지만 원소의 값이 많아지면 효과가 극대화 될 것 같다.

 

파이썬 내장 함수의 종류