[Algorithm] 정렬

지난 포스팅에서 선형 탐색과 이진 탐색에 대한 내용을 다뤘습니다. 이진 탐색을 하기 위해서는 정렬된 상태여야 한다는 조건이 있었죠. 그래서 이번 포스팅은 정렬에 관한 내용을 다루겠습니다.

 

정렬? 그냥 sort메서드나 sorted함수 사용하면 안되나? 라고 생각하실 수 있지만 아래 그림처럼 각 정렬 알고리즘은 시간/공간 복잡도가 각 상황에 따라 다르기 때문에 상황에 맞는 알고리즘을 사용하는 것이 효율적인지 생각해야 합니다. 

 

정렬 알고리즘 별 속도

 

순서

1. 선택정렬

2. 삽입 정렬

3. 합병 정렬

4. 퀵 정렬

 

모든 정렬의 설명은 내림차순 기준입니다.

 

1. 선택 정렬(Selection Sort)

선택 정렬은 현재 위치에 들어갈 값을 선택하여 정렬하는 것입니다. 아래 그림과 같이 배열 값 중 가장 작은 값을 찾습니다. 가장 작은 값을 현재 인덱스의 값과 바꾸는 과정을 반복하여 정렬합니다. 

선택정렬 예시

def select_sort(lst):

  for i in range(len(lst)-1):
      min_index = i   # 가장 작은 값이 있는 인덱스를 담을 변수
      
      # 현재 인덱스부터 마지막 인덱스까지 최소값의 인덱스를 찾음. 
      for j in range(i+1, len(lst)):   # 0번 인덱스와 그 후 인덱스를 비교해야하므로 1번 인덱스부터 j 시작
          if lst[min_index] ? lst[j]:   # 순서대로 값을 비교하며 가장 작은 값이 있는 인덱스 찾음. 
              min_index = j   # 가장 작은 값이 있는 인덱스 저장
        
      lst[i], lst[min_index] = lst[min_index], lst[i]   # 가장 작은 값을 앞쪽으로 배치 
      
    return lst

코드 설명

선택 정렬은 구현이 쉽고 비교하는 횟수에 비해 교환이 적게 일어난다는 장점이 있지만 최악의 경우 O(N^2)의 시간복잡도를 가져 오래 걸리기 때문에 비효율적입니다.

 

 

2. 삽입 정렬(Insert Selection)

삽입 정렬은 각 값이 어떤 위치에 들어갈 지 찾는 알고리즘입니다. 삽입정렬은 1번 인덱스부터 살펴봅니다. 1번 인덱스에 있는 값과 0번 인덱스에 있는 값을 비교하고 1번 인덱스에 있는 값이 0번 인덱스보다 크다면 1번 인덱스를 0번 인덱스로 삽입시킵니다. 

 

삽입정렬 예시

def insert_sort(lst):

  for i in range(1, len(lst)):   # 1번 인덱스부터 삽입할 위치 확인 

    value = lst[i]
	
    # j: 비교하려는 값의 위치
    j = i-1   # i보다 한 칸 왼쪽에 있는 값과 비교해야하므로 -1 

    while j >= 0 and value > lst[j] :  # 몇 번째 인덱스에 값을 넣어야할지 찾음.
      lst[j+1] = lst[j]
      j -= 1  # j를 감소시키면서 몇 번째 인덱스에 값을 넣어야할 지 찾음. 

    lst[j+1] = value
      
   return lst

삽입정렬은 최선의 경우 O(N)으로 속도가 빠르고 성능이 좋은 방법이지만 최악의 경우 O(N^2)으로 데이터의 크기에 따라 성능의 차이가 심합니다.

 

3. 합병 정렬

 

합병 정렬은 두 개의 배열로 분할하고 분할된 부분 배열을 정렬한 다음 합치는 방식입니다. 합병 정렬은 분할(Divide), 정복(Conquer), 결합(Combine) 3가지 단계로 이루어집니다. 

 

1. 분할(Divide): 배열을 같은 크기의 2개의 부분 배열로 분할

2. 정복(Conquer): 부분 배열을 정렬

3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열로 결합

합병정렬 예시

def merge(list1, list2):
    i = 0
    j = 0

    # 정렬된 항목들을 담을 리스트
    merged_list = []

    # list1과 list2를 돌면서 merged_list에 항목 정렬
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1

    # list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]

    # list1에 남은 항목이 있으면 정렬 리스트에 추가
    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list  
    
# 합병 정렬
def merge_sort(my_list):
    # base case: list에 값이 0개 또는 1개 일 때
    if len(my_list) < 2:
        return my_list
    
    # Divide
    mid_point = len(my_list)//2
   
    left_lst = my_list[:mid_point]
    right_lst = my_list[mid_point:]
    
    # Combine, Conquer
    return merge(merge_sort(left_lst), merge_sort(right_lst))

합병정렬은 항상 O(NlogN)의 시간복잡도를 가지는 장점이 있지만 O(N)만큼의 공간복잡도를 가져 추가적인 메모리 공간을 필요로 한다는 단점이 있습니다.

 

4. 퀵 정렬

퀵 정렬도 합병 정렬과 마찬가지로 Divide and Conquer방식을 사용합니다. 하지만 동작하는 방식이 다릅니다.

 

1. Divide(분할): pivot(기준점)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 두고 두 개의 배열로 분할

2. Conquer(정복): pivot 왼쪽 배열, 오른쪽 배열 각각에서 정렬

3. Combine(결합): 정렬된 배열을 결합

 

pivot은 임의의 위치에 있는 값을 설정하면 됩니다. 저는 마지막 값을 pivot으로 두고 예시를 보겠습니다. 

 

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]

# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    
    # 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의
    i = start  # small
    b = start  # big 
    p = end  # pivot 

    # start와 end가 겹치지 않을 때까지 
    while i < p:
        # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
        i += 1

    # b와 기준점인 p 인덱스에 있는 값들을 바꿔준다
    swap_elements(my_list, b, p)
    p = b

    # pivot의 최종 인덱스를 리턴
    return p


# 퀵 정렬
def quicksort(my_list, start, end):
    # 코드를 작성하세요.
    if end - start < 1:
        return  # return 뒤에 아무것도 없으면 return None
    
    pivot = partition(my_list, start, end) # pivot의 인덱스 받기
    
    quicksort(my_list, start, pivot -1)  # pivot기준으로 왼쪽
    quicksort(my_list, pivot+1, end)  # pivot기준으로 오른쪽 
    
    return 

퀵정렬 예시

 

퀵정렬은 O(NlogN)의 시간복잡도를 가지지만 pivot에 의해 성능의 차이가 심하고 최악의 경우에는 O(N^2)의 시간복잡도를 가집니다. 또한 O(logN)의 공간복잡도를 가지고 있습니다. 

 

 

참고

[1] 시간복잡도 관련 문서

[2] evan-moon.github.io/2018/10/13/sort-algorithm/