[Python] 버블정렬 Bubble sort & 셰이커 정렬

버블정렬은 단순 교환 정렬이다.

 

1. 일반적인 버블정렬

2. 교환이 한번도 일어나지 않은 경우 stop하는 개선 1

3. 교환이 일어나지 않는 부분을 마지막 지점으로 두는 개선 2

 

이렇게 3가지로 정리해봤다.

 

셰이커 정렬(양방향 버블정렬)은 이런경우에 이렇게 사용되는 알고리즘이다.

• 9 1 3 4 6 7 8 처럼 정렬이 거의 완료되었지만 9가 맨앞에 있으므로 버블 정렬로는 오래걸림

• 홀수 패스에서는 가장 작은 원소를 맨 앞으로 (뒤에서 앞으로 확인 후 정렬) , 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동 (앞에서 뒤로 확인 후 정렬)

<일반 버블 정렬>

오름차순임

import time

def bubble_sort(List):
    n=len(List)
    cnt=0
    
    for i in range(n-1):
        for j in range(n-1,i,-1):
            if List[j] < List[j-1]:
                List[j],List[j-1]=List[j-1],List[j] 
        cnt+=1
    print(f'교환횟수: {cnt}\n')            
    return List
    
    
    
List=[]
n=int(input('원소의 수를 입력하세요: '))
List=list(map(int,input().split()))

#결과 출력

print(*bubble_sort(List))

<일반 버블 정렬 - 개선 1>

def bubble_sort(List):
    n=len(List)
    cnt=0
    for i in range(n-1):
        check=0
        for j in range(n-1,i,-1):
            if List[j] < List[j-1]:
                List[j],List[j-1]=List[j-1],List[j]
                check+=1
        cnt+=1
        if check==0:
            break
        
    print(f'교환횟수: {cnt}\n')        
    return List
    
    
List=[]
n=int(input('원소의 수를 입력하세요: '))
List=list(map(int,input().split()))

#결과 출력

print(*bubble_sort(List))

<일반 버블 정렬 - 개선 2>

def dubble_sort(List):
    n=len(List)
    i=-1
    cnt=0

    while i<n-1:
        check=0
        for j in range(n-1,i,-1):
            if List[j] < List[j-1]:
                List[j],List[j-1]=List[j-1],List[j]
                check+=1
        i=n-check-1
        cnt+=1
    print(f'교환횟수: {cnt}\n')                
    return List
    
List=[]
n=int(input('원소의 수를 입력하세요: '))
List=list(map(int,input().split()))

#결과 출력

print(*bubble_sort(List))

<셰이커 정렬>

def shake_sort(List):
    n=len(List)
    left=0
    right=n-1
    cnt=0
    
    while left < right:
        #뒤에서 부터
        for i in range(right,left,-1):
            if List[i] < List[i-1]:
                List[i],List[i-1]=List[i-1],List[i]
        left+=1
        cnt+=1
                
        #앞에서 부터
        
        for i in range(left,right):
            if List[i] > List[i+1]:
                List[i],List[i+1]=List[i+1],List[i]
        right-=1
        cnt+=1
    
    print(f'교환횟수: {cnt}\n')
    
    return List
    
 List=[]
n=int(input('원소의 수를 입력하세요: '))
List=list(map(int,input().split()))

#결과 출력
print(*shake_sort(List))

 

실행해보면 알겠지만 같은 숫자, 같은 정렬인데 교환 횟수가 다름을 알 수 있다.

교환 횟수가 작은 코드가 더 빠르게 동작하니 효율적이다.