정렬 (Sorting) 이란
데이터를 특정한 기준에 따라서 순서대로 나열하는 것
정렬 알고리즘으로 데이터를 정렬하면 이진탐색(Binary Search)가 가능하다.
선택 정렬(Selection Sort)
매번 가장 작은 것을 선택한다.
- 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복
- 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료됨
장점
- 구현이 간단하다.
- 데이터를 하나씩 비교하기 때문에 정밀한 비교 가능
- 비교하는 횟수에 비해 교환하는 횟수 작음
단점
- 데이터를 하나씩 비교하기 때문에 시간이 오래 걸림
- 정렬된 상태에서 데이터가 추가되면 정렬 효율이 좋지 못함
python 코드
arr = [3, 1, 4, 9, 7, 2, 8, 6, 0, 5]
for i in range(len(arr)):
min_idx = i # 가장 작은 원소의 인덱스
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx=j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # Swap
print(arr)[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]시간 복잡도
🕰 O(N²)
데이터의 개수가 N개라고 했을 때
N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하고, 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다.
첫 번째 회전에서의 비교횟수 : 1 ~ (N-1) : N-1
두 번째 회전에서의 비교횟수 : 2 ~ (N-1) : N-2
...
(N-1) + (N-2) + (N-3) + ... + 1 = N(N-1)/2
삽입 정렬(Insertion Sort)
특정한 데이터를 적절한 위치에 삽입한다.
- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어있다고 가정함
장점
- 정렬된 데이터가 입력으로 들어오는 경우 속도가 빠름
- 정렬된 값은 교환이 일어나지 않음
단점
- 삽입을 구현해야 하므로 속도가 자료구조의 영향을 많이 받음
- 입력으로 들어오는 배열이 역순으로 정렬되어 있는 경우 성능이 좋지 않음
python 코드
arr = [3, 1, 4, 9, 7, 2, 8, 6, 0, 5]
for i in range(len(arr)):
for j in range(i, 0, -1):
if arr[j] < arr[j-1]: # 한 칸씩 왼쪽으로 이동
arr[j], arr[j-1] = arr[j-1], arr[j]
else: # 자신보다 더 작은 데이터를 만나면 그 위치에서 멈춤
break
print(arr)[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]시간 복잡도
🕰 O(N²)
선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용 됨
삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다!
- 최선의 경우(데이터가 이미 정렬되어 있는 상태) 시간복잡도 : O(N)
퀵 정렬(Quick Sort)
기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
- 가장 많이 사용되는 알고리즘
- 피벗(Pivot)이 사용됨
📌 피벗(Pivot)
- 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'
- 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 함 - 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행함
- 분할 정복 방식(Divide and Conquer)을 사용
합병 정렬(Merge Sort) 같은 경우에는 2개의 문제로 분할할 때, 문제의 크기가 항상 같았지만, 퀵 정렬은 일정하지 않은 형태로 분할한다.
피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬 구분
호어 분할(Hoare Partition) 방식
리스트에서 첫 번째 데이터를 피벗으로 정한다.
- 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
- 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
- 1, 2의 과정을 반복하면 피벗에 대하여 정렬이 수행됨
장점
- 평균 실행 시간이 빠름 : O(NlogN)
- 추가 메모리 공간을 필요로 하지 않음
단점
- 피벗을 어떻게 설정하느냐에 따라 성능 차이가 심함
- 안정성이 좋지 못함
python 코드
일반 퀵 정렬 소스 코드
arr = [3, 1, 4, 9, 7, 2, 8, 6, 0, 5]
def quick_sort(arr,start,end):
if start>= end: # 원소가 1개인 경우 종료
return
pivot = start # 피벗은 첫 번째 원소
left = start + 1
right = end
while left<=right:
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left<=end and arr[left]<=arr[pivot]:
left +=1
while right>start and arr[right]>= arr[pivot]:
right-=1
if left>right: #엇갈렸다면 작은 데이터와 피벗을 교체
arr[right],arr[pivot]= arr[pivot],arr[right]
else: #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
arr[left],arr[right]=arr[right],arr[left]
#분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 다시 정렬 수행
quick_sort(arr, start,right-1)
quick_sort(arr,right+1,end)
quick_sort(array,0,len(arr)-1)
print(array)파이썬 장점을 살린 퀵 정렬 소스코드
arr = [3, 1, 4, 9, 7, 2, 8, 6, 0, 5]
def quick_sort(arr):
# 리스트가 하나 이하의 원소만을 담고 있다면 종료
if len(arr) <=1:
return arr
pivot = arr[0] # 피벗은 첫 번째 원소
tail = arr[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(arr))[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]시간 복잡도
🕰 평균 : O(NlogN)
데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높음
퀵 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다!
- 최악의 경우(데이터가 이미 정렬되어 있는 경우) 시간 복잡도 : O(N²)
합병 정렬(Merge Sort)
일단 정확히 반으로 나누고 정렬한다.
- 분할 정복 방식(Divide and Conquer)을 사용
n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)한다.
장점
- 항상 일정한 시간복잡도 O(NlogN)을 가짐
- 안정적이며 대부분의 경우에서 좋은 성능을 냄
단점
- 추가 메모리 공간이 필요함
python 코드
def merge(left, right):
sorted_list=[]
i, j= 0, 0
while( i<len(left)) and (j<len(right)):
if left[i]<right[j]:
sorted_list.append(left[i])
i+=1
else:
sorted_list.append(right[j])
j+=1
if i<len(left): # 남은 왼쪽 리스트 합해줌
sorted_list+=left[i:]
if j<len(right): # 남은 오른쪽 리스트 합해줌
sorted_list+=right[j:]
return sorted_list
def merge_sort(list):
if len(list) <= 1:
return list
mid = len(list) // 2 # 중간 지점
leftList = list[:mid]
rightList = list[mid:]
leftList = merge_sort(leftList)
rightList = merge_sort(rightList)
# 주어진 두 개 리스트를 크기 순으로 정렬
return merge(leftList, rightList)시간 복잡도
🕰 O(NlogN)
단계의 크기(logN) * 정렬 자체에 필요한 수행시간(N) = NlogN
합병 정렬은 정확하게 반절씩 나눈다는 점에서 최악의 경우에도 O(NlogN)을 보장한다.
💻🐯