정렬 알고리즘_버블 정렬, 단순 선택/삽입 정렬

~ 목차 ~

• 정렬 알고리즘
• 버블 정렬
  • 버블 정렬
  • 버블 정렬 개선 1 - 교환 발생하지 않는 경우 정렬 중단
  • 버블 정렬 개선 2 - 이미 정렬된 원소는 비교/교환 범위에서 제외
  • 버블 정렬 개선 3 - shaker sort
• 단순 선택 정렬
• 단순 삽입 정렬

 

 

  정렬 알고리즘  

 

- 안정적인 정렬 알고리즘 vs 안정적이지 않은 정렬 알고리즘

값이 같은 원소의 순서가 정렬 후에도 유지되는지 여부에 따라 결정

   -> 유지 : 안정적

   -> 유지 보장 x : 안정적 x

 

- 내부 정렬 vs 외부 정렬

정렬할 데이터를 하나의 배열에 저장할 수 있는지 여부에 따라 결정

   -> 가능 : 내부 정렬

   -> 불가능 : 외부 정렬

 

- 버블, 단순 선택, 단순 삽입 정렬 시간복잡도

모두 O(n^2)로 프로그램 효율 좋지 X

 

  버블 정렬(bubble sort)  

= 단순 교환 정렬

이웃한 두 원소의 대소 비교해 필요에 따라 교환을 반복하는 알고리즘

 

버블 정렬 코드

from typing import MutableSequence
 
def bubble_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
 
if __name__ == '__main__':
    num = int(input('원소의 수 : '))
    x = [None] * num
 
    for i in range(num):
        x[i] = int(input(f'x[{i}] : '))
 
    bubble_sort(x)
 
    print(x)

 

 

버블 정렬 개선 1

한 패스(이웃값을 비교하여 왼쪽이 크기가 큰 경우 오른쪽과 위치 교체)에서 교환 발생 x 

= 정렬 완료이므로 교환 횟수에 따라 중단점 적용

버블 정렬 개선 1 - github

 

 

버블 정렬 개선 2

버블 정렬 개선 2 - github

이미 정렬된 원소를 제외한 나머지만 비교/교환하도록 스캔 범위 제한

 

 

버블 정렬 개선 3 - shaker sort

 = 양방향 버블 정렬, 칵테일 정렬

 

버블 정렬을 개선하여, 

홀수 패스에서는 가장 작은 원소 맨 앞으로 이동,
짝수 패스에서는 가장 큰 원소 맨 뒤로 이동
=> 패스의 스캔 방향 번갈아 바꾸어 버블정렬보다 적은 비교 횟수로 정렬 가능한 방법

 

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
        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
    right = last

 

 

 

 

 

  단순 선택 정렬(straight selection sort)  

가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

def selection_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(n-1):
        min = i     # 정렬할 부분에서 가장 작은 원소의 인덱스
        for j in range(i+1, n):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]     # 정렬할 부분 맨 앞 원소 <-> 가장 작은 원소

 

서로 이웃하지 않는(떨어져있는) 원소를 교환하므로 안정적  X

 

 

  단순 삽입 정렬(straight insertion sort)  

아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입하는것을 반복하여 정렬

가장 작은 원소 선택 x 단순 선택 정렬과의 차이점

def insertion_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(1, n):
        j = i
        tmp = a[i]
        while j > 0 and a[j-1] > tmp:
            a[j] = a[j-1]
            j -= 1
        a[j] = tmp