정렬 알고리즘

2019-03-27

Algorithm - Sort

bubble sort(거품 정렬)

Comparison sort의 한 종류
두 수를 비교해서 정렬하는 방법
O(n^2)
simple sort
마지막 전 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬
한번 순회가 끝나면 가장 큰 자료가 맨뒤로 이동
2번째 순회에서는 맨 끝에 있는 자료를 정렬에서 제외되는 방식

순회할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어남

import random

def bubble_sort(li):
   
    n = len(li)
    
    for i in range(n-1):
        for j in range(n-i-1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                

if __name__ == '__main__':
    
    while True:
        num_data = int(input('데이터 개수(종료:0):'))
        if not num_data:
            break
            
        data = [random.randint(1,100) for _ in range(num_data)]
        print(data)
        
        bubble_sort(data)
        print(data)

insertion sort(삽입 정렬)

Comparison sort의 한 종류
두 수를 비교해서 정렬하는 방법
O(n^2)
Comparison sort 중에 그나마 나음
simple sort
두 번째 자료부터 시작하여 그 앞 자료들과 비교하면서 삽입할 위치를 지정
지정한 후, 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 방식

처음 key 값은 두번째 자료부터 시작한다.

import random

def insertion_sort(li):
    
    n = len(li)
  
    for i in range(1, n):
       
        ref_idx = li[i]            

        for j in range(i-1, -2, -1):

            if j == -1:
                break
              
            elif li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                
            else:
                break
                
        ref_idx = li[j+1]
          
    
if __name__ == "__main__":
  
    while True:
        num_data = int(input('데이터 개수(종료:0):'))
        if not num_data:
            break
            
        data = [random.randint(1,100) for _ in range(num_data)]
        print(data)
        
        insertion_sort(data)
        print(data)

selection sort(선택 정렬)

Comparison sort의 한 종류
두 수를 비교해서 정렬하는 방법
O(n^2)
simple sort
제자리 정렬 알고리즘의 하나
입력 리스트(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

주어진 배열 중에서 최솟값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다.(두 수를 비교하여 pass도 가능)
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.

import random

def selection_sort(li):
  
    n = len(li)
   
    for i in range(0, n-1):
        min_idx = i
      
        for j in range(i+1, n):

            if li[j] < li[min_idx]:
                min_idx = j
                
        # min_idx --> 맨 앞자리를 제외하고 최소값이 위치한 곳의 인덱스
        li[i], li[min_idx] = li[min_idx], li[i]
       

if __name__ == "__main__":
    
    while True:
        num_data = int(input('데이터 개수(종료:0):'))
        if not num_data:
            break
            
        data = [random.randint(1,100) for _ in range(num_data)]
        print(data)
        
        selection_sort(data)
        print(data)

quick sort(퀵 정렬)

Comparison sort의 한 종류
두 수를 비교해서 정렬하는 방법
divide and conquer(분할 정복 알고리즘)
O(nlogn)
맨 앞의 데이터를 기준으로 선택했을 경우
- 모든 데이터가 정렬되었을 때, 오히려 많은 시간이 걸리게 된다.(O(n^2))
따라서 이 문제를 해결하는 방법은 기준을 선택할 때 중간 값을 기준으로 선택한다.

리스트의 중간 원소 pivot을 기준으로 pivot보다 큰 원소는 오른쪽으로 옮긴다.
리스트의 중간 원소 pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로 옮긴다.
pivot의 오른쪽 리스트와 왼쪽 리스트를 분할하여 재귀를 통해 다시 정렬 반복한다.

리스트의 크기가 0이나 1이 될때까지 반복한다.

import random

# 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
# 따라서 pivot을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는
# 데이터를 선택할 수 있도록 get_pivot_index 함수를 설계
def get_pivot_index(li, start, mid, end):
    """
    get_pivot_index(li, start, end) -> index
    리스트의 맨 처음 값, 가운데 값, 마지막 값 중에서
    중간 값을 가진 인덱스를 반환한다.
    """
    # 더 좋은 알고리즘이 있는지 다시 코딩해보기
    idx_li = [start, mid, end]
    if li[idx_li[0]] > li[idx_li[1]]:
        idx_li[0], idx_li[1] = idx_li[1], idx_li[0]
    if li[idx_li[1]] > li[idx_li[2]]:
        idx_li[1], idx_li[2] = idx_li[2], idx_li[1]
    if li[idx_li[0]] > li[idx_li[1]]:
        idx_li[0], idx_li[1] = idx_li[1], idx_li[0]
       
    return idx_li[1]


def quick_sort(li, start, end):
    # base case
    if start > end:
        return
    
    left = start
    right = end
    mid = (start + end) // 2
    pivot_index = get_pivot_index(li, start, mid, end)
    li[pivot_index], li[mid] = li[mid], li[pivot_index]
    
    pivot = li[mid]
  
    while left <= right:
        while li[left] < pivot:
            left += 1
            
        while li[right] > pivot:
            right -= 1
            
        if left <= right:
            li[left], li[right] = li[right], li[left]
            left += 1
            right -= 1
            
    quick_sort(li, start, right)
    quick_sort(li, left, end)
            

if __name__ == "__main__":
    
    while True:
        num_data = int(input("데이터 개수(종료: 0):"))
        if not num_data:
            break
            
        data = [random.randint(1, 100) for _ in range(num_data)]
        print(data)
        
        quick_sort(data, 0, len(data) - 1)
        print(data)

merge sort(합병 정렬)

Comparison sort의 한 종류
두 수를 비교해서 정렬하는 방법
divide and conquer(분할 정복 알고리즘)
O(nlogn)

리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
그렇지 않을 경우에는 정렬되지 않는 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

import random

def merge(li, start, mid, end):
    """
    쪼개진 두 개 리스트 조각에서
    left_idx, right_idx를 비교해서
    작은 값을 올리고 다음 칸으로 이동
    둘 중 하나가 범위를 벗어날 때
    """
    left_idx = start
    right_idx = mid + 1
    temp = []
   
    while left_idx <= mid and right_idx <= end:
        if li[left_idx] < li[right_idx]:
            temp.append(li[left_idx])
            left_idx += 1
        else:
            temp.append(li[right_idx])
            right_idx += 1
            
    while left_idx <= mid:
        temp.append(li[left_idx])
        left_idx += 1
        
    while right_idx <= end:
        temp.append(li[right_idx])
        right_idx += 1
        
    li[start:end+1] = temp

    
def merge_sort(li, start, end):
    # base case
    if start >= end:
        return
    
    mid = (start + end) // 2
    
    merge_sort(li, start, mid)

    merge_sort(li, mid + 1, end)
    
    merge(li, start, mid, end)
    

if __name__ == "__main__":
    
    while True:
        num_data = int(input('데이터 개수(종료:0):'))
        if not num_data:
            break
            
        data = [random.randint(1, 100) for _ in range(num_data)]
        print(data)
        
        merge_sort(data, 0, len(data) - 1)
        print(data)

지눅쿠의 개발 블로그

StudyPython and CE

정렬 알고리즘

Algorithm - Sort