[Algorithm] 정렬 알고리즘 정복하기

kiteB·2022년 5월 20일

Sort TIL python 삽입 정렬 선택 정렬 정렬 퀵 정렬

Algorithm-Python

목록 보기

7/7

[ 정렬 알고리즘 ]

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다.
정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬 등 다양한 종류가 있다. 각각의 정렬 알고리즘의 동작 방식과 특징을 기억해두자!

1. 선택 정렬 (Selection Sort)

매번 가장 작은 것을 선택하여 정렬하는 알고리즘

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하여 동작한다.
가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.

💡 동작 과정

주어진 배열 중에 최솟값을 찾는다.

그 값을 맨 앞에 위치한 값과 교체한다. (pass)

맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 완료된다.

✅ 선택 정렬 구현

array = [7, 5, 9, 0, 3]

for i in range(len(array)):
	min_idx = i		#가장 작은 원소의 인덱스

	for j in range(i + 1, len(array)):
    	if array[min_idx] > array[j]:
        	min_idx = j
         
	array[i], array[min_idx] = array[min_idx], array[i]		# swap

print(*array)	# 0, 3, 5, 7, 9

swap이란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업이다.

📌 특징

시간 복잡도
- 두 개의 중첩 루프가 있으므로 O(N²)이다.
  - Array의 요소를 하나씩 선택하는 하나의 루프 = O(N)
  - 해당 요소를 다른 모든 Array 요소와 비교하는 또 다른 루프 = O(N)
- 선택 정렬은 기본 정렬 라이브러리를 포함하여 다른 정렬 알고리즘과 비교했을 때 매우 비효율적이다.
공간 복잡도
- 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(N).
  → 추가 공간이 필요하지 않으므로 메모리 쓰기 비용이 많이 드는 작업일 때는 유용하다.
알고리즘이 단순하다.
불안정 정렬(Unstable Sort)이다.

📌 안정 정렬 vs 불안정 정렬

안정 정렬(Stable Sort): 중복된 값을 입력 순서와 동일하게 정렬하는 알고리즘의 특성

불안정 정렬(Unstable Sort): 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘

2. 삽입 정렬(Insertion Sort)

2번째 원소부터 시작하여 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘

필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.

💡 동작 과정

현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작)

타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.

그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

✅ 삽입 정렬 구현

array = [7, 5, 9, 0, 3]

for i in range(1, len(array)):
	for j in range(i, 0, -1):	# 인덱스 i부터 1까지 감소하며 반복하는 문법
    	if array[j] < array[j - 1]:		# 한 칸씩 왼쪽으로 이동
        	array[j], array[j - 1] = array[j - 1], array[j]
        else:	# 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        	break

print(array)	# [0, 3, 5, 7, 9]

📌 특징

시간 복잡도
- 최악의 경우 O(N²)이다.
- 모두 정렬되어 있을 경우(Optimal한 경우, 최선의 경우), 한번씩만 비교하면 되므로 O(N)의 시간 복잡도를 가지게 된다.
공간 복잡도
- 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.
알고리즘이 단순하며, 안정 정렬이다.
대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있으며, 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다.
배열의 길이가 길어질수록 비효율적이다.

3. 퀵 정렬

가장 많이 사용되는 알고리즘으로, 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

퀵 정렬에는 피벗(pivot)이 사용된다. 큰 수와 작은 수를 교환할 때, 교환하기 위한 기준이 바로 피벗이다.

💡 동작 과정

리스트 안에 있는 한 요소(피벗)를 선택한다.

피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)

피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.

분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.

부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.

부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

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

✅ 퀵 정렬 구현

array = [5, 7, 9, 0, 3]


def quick_sort(array):
	# 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
    	return array
        
    pivot = array[0]	# 피벗은 첫 번째 원소
    tail = array[1:]	# 피벗을 제외한 리스트
    
    left_side = [x for x in tail if x <= pivot]	# 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot]	# 분할된 오른쪽 부분
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)


print(quick_sort(array))	# [0, 3, 5, 7, 9]

⏰ 특징

시간 복잡도
- 최선의 경우 O(Nlog₂N)이다.
  - 비교 횟수: O(log₂N)
  - 각 순환 호출 단계의 비교 연산: O(N)
- 최악의 경우 (정렬하고자 하는 배열이 오름차순 정렬되어 있거나 내림차순 정렬되어 있는 경우) O(N²)이다.
공간 복잡도
- 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.
속도가 빠르며, 추가 메모리 공간을 필요로 하지 않는다.
정렬된 리스트에 대해서 느리게 동작한다. → 기본 정렬 라이브러리를 이용하면 O(Nlog₂N)을 보장해준다.