[SW사관학교정글] WEEK01 개발일지 - Ⅲ

정렬

정렬이란

정렬은 이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 데이터를 정렬하면 더 쉽게 검색할 수 있다. 값이 작은 데이터를 앞쪽에 늘어 놓는 것을 오름차순 정렬이라고 하고, 그 반대를 내림차순 정렬이라고 한다.

버블 정렬

버블 정렬은 뒤에서 부터 앞으로 정렬을 진행하는 구조를 가지고 있다. 오름차순 정렬 기준으로 배열의 맨 뒷공간에 가장 높은 값을 보내고, 그 앞에 두번째로 큰 값을 보낸다. 이를 위하여 배열 내 값들을 앞뒤로 서로 비교하며 자리를 바꾸는 작업을 반복한다. '작은 값을 앞으로 가져오겠다'라는 개념을 반대로 이용하여 큰 값을 뒤로 보내며 원소들끼리 위치를 변경하는 모습이 물방울이 이동하는 것과 같아 보여서 Bubble Sort라는 이름이 명명되었다고 한다.

버블 정렬 구현

def bubble_sort(arr):
	for i in range(len(arr)-1, 0, -1): # 뒤에서 부터 정렬한다.
    	for j in range(len(i)): 	   # 앞에서 부터 조회
        	if arr[j] > arr[j+1]:      # 인근 값 대소 비교
            	arr[j], arr[j+1] = arr[j+1], arr[j]

거품 정렬은 큰 값들을 뒤에서 부터 앞으로 하나씩 쌓아 나가기 때문에 원소가 자리를 잡을 떄 마다 정렬의 범위가 하나씩 줄어들게 된다. 제일 작은 값을 찾아 맨 앞에 위치시키는 선택정렬과는 정 반대의 정렬 방향을 갖는다. 타 정렬 알고리즘에 비하여 값의 swap이 빈번히 일어나게 된다.

시간 복잡도는 루프문을 통해 모든 인덱스에 방문해야 하므로 기본적으로 O(N)의 시간을 소모하며, 하나의 루프에서는 인접한 원소와 대소 비교 및 swap을 위하여 O(N)의 시간을 추가로 필요로 한다. 따라서 버블 정렬은 O(N^2)의 복잡도를 갖는 정렬 알고리즘이다.

선택 정렬

선택 정렬은 정렬되어 있지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞부터 순서대로 정렬해 나아가는 알고리즘이다. 선택 정렬은 정렬된 값을 배열의 맨 앞부터 하나씩 채워나가게 된다. 따라서, 뒤 index로 갈수록 비교 범위가 1씩 감소한다는 특성을 갖는다. 입력 배열이 이미 정렬되어 있거나 말거나 상관없이 동일한 연산량을 갖기 때문에 최적화의 여지가 적어 성능이 떨어지는 편이다.

선택 정렬 구현

def selection_sort(arr):
	for i in range(len(arr) -1):  # outer
    	min_idx = i
        for j in range(i+1, len(arr)): # inner
        	if arr[j] < arr[min_idx]"  # 최저값을 찾아내면
            	min_idx = j			   # 최저값의 idx를 가져온다.
        arr[i], arr[min_idx] = arr[min_idx], arr[i] # value swap
    return arr

선택 정렬은 루프문을 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N) 시간을 소모하며, 최소값을 찾으면 현재 인덱스와 최소값을 서로 swap해야 하기 떄문에 O(N) 시간을 필요로 하게 된다. 따라서, 선택 정렬은 총 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘이다.

삽입 정렬

삽입 정렬은 모든 요소를 앞에서부터 정렬 범위를 확장시켜나가며 정렬을 진행한다. 차례대로 이미 정렬된 배열 부분과 확장된 범위 부분을 비교하며, 자신의 위치를 찾아 삽입함으로써 정렬을 완성시키는 알고리즘이다. 앞서 살펴봤던 선택, 버블 정렬과는 달리 정렬이 진행될수록 범위가 넓어진다. 크게 바라보면 outer 루프는 순방향, inner 루프는 역방향으로 반복을 진행한다.

삽입 정렬 구현

def insertion_sort(arr):
	for end in range(1, len(arr)):
    	for i in range(end, 0, -1):
        	if arr[i-1] > arr[i]:
            	arr[i]. arr[i-1] = arr[i-1], arr[i]
    return arr

삽입 정렬은 루프문을 통해 정렬 범위를 2개로 시작하여 전체를 확장해 나아가기 때문에 기본적으로 O(N) 시간을 소모하며, 각 회차마다 정렬 범위에 추가된 값과 기존 값들과의 대소 비교 및 swap을 위해 O(N) 시간이 추가적으로 소모된다. 따라서, 삽입 정렬은 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘이다.

퀵 정렬

퀵 정렬은 분할 정복 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다. 퀵 정렬에서는 pivot(임의의 기준값)이라는 변수가 도입된다. 퀵 정렬은 배열을 pivot 값을 기준으로 더 작은 값과 더 큰값으로 반복적으로 분할하며 정렬해 나아가는 방식을 취하고 있다.

퀵 정렬 구현

def quick_sort(arr):
    if len(arr) == 1:
        return arr
    pivot = arr[len(arr)//2]
    lesser_list, equal_list, greater_list = [], [], []
    for i in arr:
        if i < pivot:
            lesser_list.append(i)
        elif i > pivot:
            greater_list.append(i)
        else:
            equal_list.append(i)
    return quick_sort(lesser_list) + equal_list + quick_sort(greater_list)

퀵 정렬의 성능은 pivot 값의 선택에 따라 크게 달라질 수 있다. 이상적인 경우, 작은값과 큰값이 동일한 개수로 분할된다면 O(NlogN)의 시간복잡도를 갖게 된다. 하지만, 만일 잘못된 pivot 선택으로 값이 한쪽으로 치우치게 된다면 퀵 정렬의 성능이 정하되어 최악의 경우 O(N^2)의 시간 복잡도를 보이게 된다.

병합 정렬

병합 정렬은 퀵 정렬과 동일하게 분할 정복 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다. 주어진 배열의 크기가 1이 될 때까지 반씩 쪼갠뒤 정렬을 진행하며 병합을 진행한다.

병합 정렬 구현

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0

    while l < len(left) and h < len(right):
        if left[l] < right[h]:
            merged_arr.append(left[l])
            l += 1
        else:
            merged_arr.append(right[h])
            h += 1
    merged_arr += left[l:]
    merged_arr += right[:h]
    return merged_arr

병합 정렬은 크게 split 단계와 merge 단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾아야 하는 분할 비용보다 모든 값들을 비교해야 하는 병합 비용이 더욱 크다. 기존 배열을 split할 때, 8 > 4 > 2 > 1 크기로 반복의 수가 거듭할수록 반으로 줄어들기 때문에 O(logN)의 시간이 필요하며, 병합시에 모든 값들을 비교해야 하므로 O(N)시간이 소모된다. 따라서, 병합 정렬은 O(NlogN)의 시간복잡도를 갖는다.

정렬 관련 백문 문제 Github 링크
백준 정렬 관련 문제