WEEK. 01 2022.04.03 TIL

정렬 알고리즘이란?

정렬(sorting)이란 이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 의미함.

정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다.

안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 의미하고, 안정적이지 않은 알고리즘은 정렬한 후에도 원래의 순서가 유지된다는 보장을 할 수 없음.

정렬 알고리즘의 핵심은 교환, 선택, 삽입!

01. 버블 정렬

버블 정렬은 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 함. 아래는 버블 정렬을 이용하여 오름차순 하는 코드를 작성해본 예시다.

def bubble_sort(li):
    n = len(li)
    for i in range(n-1): #패스를 의미
    	cnt = 0 # 교환 횟수를 의미.
        for j in range(n-1, i, -1): # 교환을 의미 패스를 할 때마다 교환의 횟수가 1씩 줄어듦
            if li[j-1] > li[j]:
                li[j], li[j-1] = li[j-1], li[j]
            cnt += 1
        if cnt == 0: #교환 횟수가 0일 경우 정렬 완료를 의미하고 패스를 중단함.
        	break
    return li

02. 쉐이크 정렬

[9, 1, 2, 3, 4, 5]와 같은 배열에서 버블 정렬의 경우 9를 제외한 나머지 숫자들이 정렬되어 있음에도 불구하고 전체 패스 과정을 모두 수행해야 한다. 이러한 단점을 개선하기 위해 패스 수행 후 역방향으로 정렬을 수행하여 효율을 증가시키는 방법이다.

def shaker_sort(li):
    right = len(li) - 1
    left = 0
    while left < right: #각 방향에서 시작하는 인덱스의 크기가 같아지면 종료
        for i in range(right, left, -1):
            if li[i-1] > li[i]:
                li[i-1], li[i] = li[i], li[i-1]
            	left = i
        for i in range(left, right):
            if li[i] > li[i+1]:
                li[i], li[i+1] = li[i+1], li[i]
            	right = i
    return li

원리를 이해하고 제대로 코드를 작성했다고 생각했지만 실제로 실행을 해보니 while 문이 무한으로 실행되는 것을 확인하고, 원인을 찾아보았다.
위 코드는 각 방향에서 원소 위치를 바꿀 때 해당 조건에 부합하는 경우에만 left 및 right 값이 새로 할당되는데 left, right 값이 정해지고 나서 정렬이 완료될 경우 left와 right 값이 고정되어 루프가 계속 실행되는 것을 확인했다.
예를 들어, 정방향으로 시작하는 left의 인덱스가 2이고, 역방향에서 시작하는 right의 인덱스가 5인 상태에서 정렬이 끝나면 left가 right보다 작기 때문에 해당 범위 내에서 루프가 계속 실행됨.
따라서, 원소 교환이 일어나지 않는 경우는 정렬을 완료했다는 의미이기 때문에 이 경우 이전 방향에 대한 인덱스 값을 할당해주는 부분이 필요했다.

		for i in range(right, left, -1):
            if li[i-1] > li[i]:
                li[i-1], li[i] = li[i], li[i-1]
            	last = i
            left = last
        for i in range(left, right):
            if li[i] > li[i+1]:
                li[i], li[i+1] = li[i+1], li[i]
            	last = i
            right = last # 만일 정방향 연산 시 원소 교환이 일어나지 않을 경우 이전의 역방향에서의 last 값을 right에 할당하도록 함. 정상적으로 루프를 빠져나올 수 있다.

03. 단순 선택 정렬

배열의 첫 인덱스부터 가장 작은 원소를 차례대로 배치하는 정렬 방법.

def selection_sort(li):
    n = len(li)
    print(li)
    for i in range(n-1): # 배열의 첫 인덱스부터 시작    
        min = i
        for j in range(i+1, n): # 기준이 되는 인덱스를 제외한 원소 중에 가장 작은 값을 선택
            if li[min] > li[j]:
                min = j
        li[i], li[min] = li[min], li[i] # 기준이 되는 원소와 가장 작은 원소의 위치를 바꿈
        print(li)
    return li

04. 단순 삽입 정렬

배열의 두번째 index 값부터 시작하여 자신보다 큰 값 중 가장 작은 값의 위치의 원소와 교환하는 방법.

def insert_sort(li):
    n = len(li)
    for i in range(1, n): # 기준값은 배열의 2번째 원소부터 시작
        temp = li[i]
        k = i-1
        while li[k] > temp and k != -1: # 타겟값이 이전 값보다 작거나 인덱스가 0보다 크거나 같을 경우 진행
            li[k+1] = li[k]
            k -= 1
        li[k+1] = temp # temp보다 작은 값의 다음 원소를 기준값으로 수정
    return li

위 방법은 배열 원소 수가 많아지면 원소 삽입에 필요한 비교, 교환 비용이 커짐. 이 경우, 이진 검색법을 이용하면 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있음.

보충 - 이진 검색

이진 검색은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다.

def search_bin(li, value):
    # 오름차순으로 정렬되어 있는 데이터일 경우 사용함.
    pr = len(li) - 1
    pl = 0
    pc = (pl + pr) // 2
    while li[pc] != value:
        pc = (pl + pr) // 2
        if pl>pr: # 검색할 범위가 존재하지 않음.
            return "검색 실패"
            break
        else:
            if value > li[pc]:
                pl = pc + 1
            elif value < li[pc]:
                pr = pc - 1
    return pc

04-2. 이진 삽입 정렬

삽입 정렬에서 기준이 되는 값의 앞 요소들은 모두 정렬이 완료되어 있는 상태이므로 해당 범위에서 기준값이 들어갈 위치를 찾을 때 이진 검색을 이용하는 코드를 작성하였다.

def binary_insert_sort(li):
    n = len(li)
    for i in range(1, n): # 기존의 단순 삽입 정렬과 동일하게 두번째 인덱스부터 시작
        pl = 0
        pr = i - 1
        pc = (pl+pr)//2
        tmp = li[i]
        while True:
            pc = (pl+pr)//2
            if pl > pr:
                break
            elif li[pc] < tmp:
                pl = pc + 1
            elif li[pc] > tmp:
                pr = pc - 1            
            elif li[pc] == tmp:
                break
        pd = pc + 1 if pl <= pr else pr + 1 # 만일 기준값과 동일한 값을 찾아 while 문이 종료 되었을 경우 기존의 순서를 유지하며 기준값이 삽입될 위치는 pc+1이 된다.
        									# 기준값이 앞선 배열에 없어서 pl이 pr보다 커졌을 경우 기준값이 pc값보다 크기 때문에 삽입 위치는 pr+1이 된다. 
        li[pd+1:i+1] = li[pd:i] # 삽입될 위치의 다음 인덱스부터 기준값 이전까지의 원소들을 오른쪽으로 한칸 이동 시킨다.
        li[pd] = tmp # 기준값 삽입
    return li

05. 셸 정렬

단순 삽입 정렬의 경우 삽입될 위치가 멀리 떨어져 있을수록 시간이 오래 소요된다. 이를 보완하기 위해 일정한 거리만큼 떨어져있는 원소들을 그룹별로 정렬하여 원소의 이동 횟수를 줄이는 방법.

def shell_sort(a):
    n = len(a)
    h = n//2 # 비교할 원소들의 간격
    while h > 0:
        for i in range(h, n):
            j = i - h
            tmp = a[i]
            while j >= 0 and a[j] > tmp:
                a[j+h] = a[j]
                j -= h
            a[j+h] = tmp
        h //= 2 # 효율 증대를 위해 3*h+1 (h=0,1,2...) 사용. 초기 h값이 너무 크면 효율이 떨어지므로 배열 길이를 9로 나눈 몫보다 작은 것이 좋음.
    return a

06. 퀵 정렬

퀵 정렬은 가장 빠른 정렬 알고리즘으로 알려져 있으며 배열에서 피봇을 선택하여 피봇보다 작은 값은 피봇 기준 왼쪽으로 피봇보다 큰 값은 오른쪽으로 위치시키는 방법

def pivot_sort(a):
    n = len(test)
    pl = 0
    pr = n - 1
    pivot = a[n//2]
    while pl <= pr:
        while a[pl] < pivot: pl += 1 # 피봇보다 큰 값을 찾을때까지
        while a[pr] > pivot: pr -= 1 # 피봇보다 작은 값을 찾을때까지
        if pl <= pr: # 피봇 기준으로 한쪽이 교환할 수 있는 값이 없어져버릴 경우 교차??되버리는 경우가 발생하는 것 같음. 깜빡하고 이걸 생략했더니 이미 pl과 pr이 교차되버린 상태에서 값이 교환되어 이상해진 것을 발견.
            a[pl], a[pr] = a[pr], a[pl] # 피봇 기준으로 위치에 맞게 교환
            pl += 1 # pl, pr이 교차되는 것을 확인하기 위해 
            pr -= 1
    print('pivot 보다 큰 애들:', a[pl:])
    print('pivot 보다 작은 애들:', a[0:pr+1])
    if pr+1 < pl:
        print('pivot과 일치하는 애들:', a[pr+1:pl])
    return a