[알고리즘] 정렬

정렬 알고리즘이란?

정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.

대표적인 정렬 알고리즘 종류

• O($n^2$)
  - 버블 정렬
  • 선택 정렬
  • 삽입 정렬
• O($nlogn$)
  - 병합 정렬
  • 퀵 정렬

---

버블 정렬

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 인접한 2개의 레코드를 비교하여 정렬되어 있지 않으면 서로 교환한다.

과정

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

버블 정렬은 인접한 두 수를 비교하며 정렬해나가는 방법으로 O($n^2$)의 느린 성능을 가짐

파이썬 예제 코드

array = [9,8,7,6,5,4,3,2,1]

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

print("before: ",array)
bubble_sort(array)
print("after:", array)

결과

---

선택 정렬

• 데이터에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬

과정

1. 주어진 배열 중에서 최솟값을 찾는다
2. 그 값을 맨 앞에 위치한 값과 교체한다
3. 맴 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다

파이썬 예제 코드

array = [8,4,6,2,9,1,3,7,5]

def selection_sort(array):
	n = len(array)
	for i in range(n):
		min_index = i
		for j in range(i + 1, n):
			if array[j] < array[min_index]:
				min_index = j
		array[i], array[min_index] =  array[min_index], array[i]
		print(array[:i+1])

print("before: ",array)
selection_sort(array)
print("after:", array)

결과

선택 정렬도 버블 정렬과 마찬가지로 O($n^2$)의 복잡도를 가진다.

---

삽입 정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

과정

• 두 번째 자료부터 시작해서 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후, 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬한다.
• 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다.
• 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

파이썬 예제 코드

array = [8,4,6,2,9,1,3,7,5]

def insertion_sort(array):
	n = len(array)
	for i in range(1, n):
		for j in range(i, 0, - 1):
			if array[j - 1] > array[j]:
				array[j - 1], array[j] = array[j], array[j - 1]
		print(array[:i+1])

print("before: ",array)
insertion_sort(array)
print("after:", array)

결과

삽입 정렬 또한 선택 정렬과 버블 정렬과 마찬가지로 O($n^2$)의 시간복잡도를 가진다.

---

병합 정렬

• 분할 정복과 재귀를 이용한 알고리즘이다.
• 반으로 쪼개고 다시 합치는 과정에서 그룹을 만들어 정렬하게 되며 이 과정에서 $2n$개의 공간이 필요하다.
  
  
  분할 정복:

  문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

과정

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

파이썬 예제 코드

array = [8,4,6,2,9,1,3,7,5]

def merge_sort(array):
	if len(array) < 2:
		return array
	mid = len(array) // 2
	low_arr = merge_sort(array[:mid])
	high_arr = merge_sort(array[mid:])

	merged_arr = []
	l = h = 0
	while l < len(low_arr) and h < len(high_arr):
		if low_arr[l] < high_arr[h]:
			merged_arr.append(low_arr[l])
			l += 1
		else:
			merged_arr.append(high_arr[h])
			h += 1
	merged_arr += low_arr[l:]
	merged_arr += high_arr[h:]
	print(merged_arr)
	return merged_arr

print("before: ",array)
array = merge_sort(array)
print("after:", array)

결과

병합 정렬은 O($nlogn$)의 빠른 속도를 가진다.

---

퀵 정렬

• 병합 정렬과 같이 분할 정복 알고리즘 중 하나이나, 병합 정렬과 달리 퀵 정렬은 리스트를 pivot을 기준으로 비균등하게 분할한다.
• 추가적인 메모리 공간이 필요 없다는 장점을 가졌다.

과정

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 선택된 요소를 피벗(pivot)이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모드 피벗의 오른쪽으로 옮겨진다.
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   • 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.
   • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더이상 분할이 불가능할 때까지 반복한다.
   • 리스트의 크기가 0이나 1이 될 때까지 반복한다.

파이썬 예제 코드

array = [8,4,6,2,5,1,3,7,9]

def quick_sort(array):
	if len(array) <= 1:
		return array
	pivot = len(array) // 2
	front_arr, pivot_arr, back_arr = [], [], []
	for value in array:
		if value < array[pivot]:
			front_arr.append(value)
		elif value > array[pivot]:
			back_arr.append(value)
		else:
			pivot_arr.append(value)
	print(front_arr, pivot_arr, back_arr)
	return quick_sort(front_arr) + quick_sort(pivot_arr) + quick_sort(back_arr)

print("before: ",array)
array = quick_sort(array)
print("after:", array)

결과

• 병합 정렬과 마찬가지로 O($nlogn$)의 시간 복잡도를 가진다.
• 다른 정렬 알고리즘보다 빠르며, 많은 언어의 정렬 내장 함수로 퀵 정렬을 사용한다.

---

파이썬 정렬 라이브러리

sorted()

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.
특징

• 병합 정렬을 기반으로 만들어졌다.
• 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O($nlogn$)을 보장한다.
• 정렬된 결과를 리스트 자료형으로 반환한다.

sort()

• 리스트 객체의 내장 함수
• 리스트 변수가 있을 때 내부 원소를 바로 정렬한다.
• 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

array = [ 7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# sorted() 정렬 : 정렬된 리스트가 반환됨, array 는 그대로
result = sorted(array)
print(result)
print(array)

# sort() 정렬 : 내부 원소가 바로 정렬됨
array.sort()
print(array)

# sorted() 정렬 반환 결과를 담은 result 와 array
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# sort() 정렬된 array
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

key 값

• sorted()나 sort()를 이용할 때는 key 매개변수를 입력으로 받을 수 있다.
• key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

# 방법 1 : 함수를 정의한 후 key 값에 넣어주기
def setting(data):
    return data[1]      # 인덱스 1에 위치한 원소가 반환된다 (key 값 = 2, 5, 3)

result = sorted(array, key = setting)
print(result)

# 방법 2 : 람다함수를 key 값에 넣어주기
result = sorted(array, key = lambda data: data[1])
print(result)

[('바나나', 2), ('당근', 3), ('사과', 5)]
[('바나나', 2), ('당근', 3), ('사과', 5)]

정렬 라이브러리의 시간 복잡도

• 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O($nlogn$)을 보장한다.