정렬
기본적인 정렬 알고리즘에 대해 공부하고 코드를 작성해본다.
- 특정 리스트를 오름차순 정렬하는 상황을 가정하고 공부해본다.
ex) [5,3,4,1,2] => [1,2,3,4,5]
1. 선택정렬
간단하게 표현하면 제일 작은 수부터 차례로 찾아가며 정렬하는 방법이다.
리스트 요소를 하나씩 서로 비교해가며 '최솟값, 두번째 최솟값, 세번째 최솟값 ... ' 이런식으로 제일 작은 값부터 채워나가며 정렬하는 방식이다. 이때 정렬된 리스트를 담을 새로운 리스트를 만들고 이곳에 '최솟값, 두번째 최솟값, 세번째 최솟값 ... '을 채워넣는 식이 아니라, 기존에 존재하는 리스트 자체에서 '첫번째 요소와 리스트 내 최솟값을 스왑, 두번째 요소와 남은(첫번째 요소를 제외한) 리스트 내 최솟값을 스왑, 세번째 요소와 남은(첫번째 요소와 두번째 요소를 제외한) 리스트 내 최솟값을 스왑, ...' 이런식으로 스왑을 이용해 기존 리스트를 정렬한다. 즉, 'n번째 요소와 n번째 최솟값 스왑'을 반복하는 것이다.
- 파이썬 구현
- 첫번째 for문으로 n번째 요소 기준을 잡아주고(n번째 최솟값이 들어갈 자리를 잡아주는 느낌)
- 두번째 for문으로 n번째 요소 이후 요소들을 순환시키면서 하나하나 비교해나가며 n~마지막 요소들 중 최솟값을 찾아낸다. (n번째 요소 이후 요소들만 순환시키는 이유 : n번째 요소 이전 요소는 이미 전 단계에서 찾아낸 최솟값들로 이미 자리가 확정된 상태이므로 비교해줄 필요가 없음)
- 최솟값을 찾으면 최솟값과 1단계에서 기준으로 잡아논 n번째 요소를 스왑해준다.
- 그러면 n번째 최솟값이 n번째 요소에 위치해 있게되고, 이는 정렬이 확정된 요소로 다음 for문에서는 비교할 필요가 없게 된다.
- n+1로 1단계부터 반복
ex) [5,3,4,1,2] n=5
첫번째 for문으로 '첫번째요소->두번째요소-> ... ->마지막요소'를 순서대로 기준으로 잡는다.
먼저 [5,3,4,1,2]에서 첫번째 요소인 5가 기준으로 잡혔을 때...
두번째 for문으로 5 이후 요소들인 '3->4->1->2'를 순환시키면서 5와 비교한다. 그러면서 최솟값을 찾아냄. => 1
5와 1을 바꿔준다. 그럼 리스트는 [5,3,4,1,2]에서 [1,3,4,5,2]로 바뀐다.
그러면 1은 확실하게 자리를 잡은 상태가 되고 더 이상 비교해 관여하지 않아도 된다.
다시 첫번째 for문으로 올라가서 바뀐 리스트 [1,3,4,5,2]에서 두번째 요소인 3을 기준으로 잡고 반복한다.
- 시간 복잡도
(리스트 길이가 n이라면)
최솟값을 찾을 때는 모든 요소를 둘러봐야 하므로 n번 소요
두번째 최솟값을 찾을 때는 최솟값을 제외한 n-1번 소요
세번째 최솟값을 찾을 때는 최솟값,두번째 최솟값을 제외한 n-2번 소요
...
ex) [5,3,4,1,2] n=5
최솟값을 찾기 위해 '5->3->4->1->2'를 모두 훑어가며 최솟값을 찾는다. => 5번 소요
두번째 최솟값을 찾을 때는 최솟값인 1은 제외하고 '5->3->4->2'를 훑어가며 최솟값을 찾는다. => 4번
세번째 최솟값을 찾을 때는 최솟값 1과 두번째 최솟값 2를 제외화고 '5->3->4'를 훑어가며 최솟값을 찾는다. => 3번
...
총 n, n-1, n-2, ... , 1 번 소요된다. => (n + 1) * (n / 2)
즉, 빅오 표기법으로 O(n^2)
2. 삽입정렬
간단하게 표현하면 리스트에서 요소를 하나씩 빼서 출력값(정렬된 리스트)으로 제출할 리스트에 추가하고 정렬하는 행위를 한 세트로 묶어 반복하며 정렬하는 방법이다.
리스트에서 첫번째 요소는 이미 정렬된 것으로 여기며 시작한다. 이렇게 정렬된 첫번째 요소만을 포함한 리스트를 정렬 리스트라고 표현해본다.여기서 두번째 요소를 정렬 리스트에 추가하고 원래 정렬 리스트에 존재하던 요소들과 비교하며 정렬한다. 여기까지가 한 세트다. 이것을 계속 반복한다.
-
파이썬 구현
- 첫번째 for문으로 두번째 요소부터(첫번째 요소는 그 자체로 이미 정렬된 것으로 보고) 마지막 요소까지 순환시켜준다.
- 첫번째 for문에서 선택된 n번째 요소를 n-1번째 요소와 비교해 n-1번째 요소보다 작다면 서로 자리를 스왑한다.
- 만약 스왑을 하지 않는다면 즉시 첫번째 단계로 돌아가 다음 요소로 넘어가고, 스왑을 했다면 계속해서 n-1과 n-2, n-2과 n-3 이런식으로 두번째 단계와 같은 비교와 스왑을 진행한다. 여기서도 마찬가지로 스왑을 할 경우 첫번째 단계로 돌아가고 스왑을 진행했다면 다음 요소와도 비교하며 스왑여부를 따진다.
ex) [5,3,4,1,2]
첫번째 for문으로 '두번째요소->세번째요소...->마지막요소'를 순환시킨다.
먼저 [5,3,4,1,2]에서 두번째요소인 3이 기준으로 잡혔을 때...
3과 3바로 왼쪽에 위치한 요소 5를 비교한다. 3이 더 작으므로 3과 5를 스왑한다.
즉 [5,3,4,1,2]에서 [3,5,4,1,2]가 되고 스왑을 했기 때문에 즉시 첫번째 단계로 돌아간다.
바뀐 리스트 [3,5,4,1,2]에서 세번째요소인 4가 기준으로 잡혔을 때...
4와 4바로 왼쪽에 위치한 요소 5를 비교한다. 4가 더 작으므로 4와 5를 스왑한다.
즉 [3,5,4,1,2]에서 [3,4,5,1,2]가 된다. 스왑을 했기 때문에 반복해서 비교를 이어나가면 4와 3을 비교했을 때 4가 3보다 크므로 스왑하지 않고 즉시 첫번째 단걔로 돌아간다.
바뀐 리스트 [3,4,5,1,2]에서 네번째 요소인 1을 기준으로 잡고 반복 ...
-
시간 복잡도
(리스트 길이가 n이라면)
두번째 요소와 첫번째 요소를 비교하고 스왑 결정 = 1번
세번째 요소와 두번째 요소를 비교하고 스왑 결정(만약 스왑한다면)
두번째 요소와 첫번째 요소를 비교하고 스왑 결정 = 2번
네번째 요소와 세번째 요소를 비교하고 스왑 결정(만약 스왑한다면)
세번째 요소와 두번째 요소를 비교하고 스왑 결정(만약 스왑한다면)
두번째 요소와 첫번째 요소를 비교하고 스왑 결정 = 3번
...
마지막 요소(위와 같이 계속 스왑한다면) = n-1번
총 1,2,3, ... , n-1번 => (1 + n-1) * (n-1)
즉, 빅오 표기법으로 O(n^2)
하지만 이 경우는 위처럼 계속 스왑을 해줘야 하는 최악의 경우를 가정한 것이고, 만약 이미 리스트가 어느 정도 정렬되어 있는 경우 위처럼 스왑을 생략하고 넘어가는 경우가 많을 것이고 그에 따라 시간 복잡도도 줄어들 것이다.
=> 특징 : 어느 정도 정렬된 리스트에서 굉장히 효율적으로 동작한다.
3. 퀵 정렬
pivot을 이용한 정렬 방법이다. pivot은 기준점이라고 표현할 수 있다. 이 pivot은 정렬하고 싶은 리스트의 첫번째 요소를 의미한다. 정렬하고 싶은 리스트의 pivot(첫번째 요소)보다 작은 수들은 pivot 왼쪽에 정렬하고, pivot보다 큰 수들은 pivot 오른쪽에 정렬한다. 이 방법을 pivot을 기준으로 두개로 나뉜 리스트에 각각 적용하며 반복한다. 그렇게 리스트의 길이가 1이 되어 더 이상 두개의 리스트로 나뉘지 못하면 정렬이 완성된다.
-
파이썬 구현
코드를 통한 설명이 이해하기 쉽다. -
시간 복잡도
피벗을 이용해 계속해서 거의 리스트를 이등분해나가며 정렬해주는 모습을 띈다. 길이가 n인 리스트를 길이가 1이 될 때까지 이등분하는 횟수는 log2(n)이다. 또한 각각의 이등분 단계에서 리스트의 길이만큼 연산이 들어가므로 n이 곱해진다.
즉, 빅오 표기법으로 O(n*log2(n))
4. 병합 정렬
간단하게 표현하면 리스트를 이등분해나가다 모두 길이가 1인 리스트들로 쪼개지면 다시 정렬하며 병합해나가 모든 리스트를 다시 정렬 병합하는 방법이다
-
파이썬 구현
- 퀵 정렬과 마찬가지로 리스트 길이가 1이 될 때까지 이등분해나간다.
- 길이가 1로 나뉘어진 리스트들을 정렬하며 병합한다. 이때 요소 하나하나를 모두 비교해가며 정렬하며 병합한다.
(말로 설명하기에 복잡/ 코드를 보는 것이 이해하기 쉽다)
-
시간 복잡도
모두 이등분하며 다시 2개씩 병합하며 1개의 리스트로 만드는 단계 수 : log2(n), 그리고 각 단계마다 연산하는 리스트 요소 갯수 : n개
즉, 빅오 표기법 : O(nlog2(n))
=> 특징1 : 언제나 동작방식은 동일하여 아무리 정렬이 안된 리스트를 정렬해도 O(nlog2(n))의 복잡도를 보장해준다.
=> 특징2 : 어느 정도 정렬된 리스트에서 오히려 굉장히 비효율적으로 동작한다.
구현한 코드들
###################### < 오름차순 정렬 방법들 > ######################
import random
arr=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
random.shuffle(arr)
print('랜덤배열 : ',arr)
#----------- 선택정렬 O( n^2 ) -----------#
def select_sort(arr):
for i in range(len(arr)):
min_idx = i # 기준인 i번째 인덱스값이 가장 작다고 가정
for j in range(i+1,len(arr)): # i번째 뒤쪽 인덱스를 모두 훑으면서 가장 작다고 가정된 i번째 값보다 작은 값을 찾으며 최솟값을 갱신한다.
if arr[min_idx] > arr[j]:
min_idx = j # 새로운 최솟값 갱신
arr[i],arr[min_idx]=arr[min_idx],arr[i] # 스왑
return arr
print('선택정렬 : ',select_sort(arr))
#----------- 삽입정렬 O( n^2 ) -----------#
def insert_sort(arr):
for i in range(1,len(arr)):
for j in range(1,i+1):
if arr[i-j] > arr[i+1-j]: # 새로운 기준값이 바로 왼쪽값보다 작으면 스왑
arr[i-j],arr[i+1-j]=arr[i+1-j],arr[i-j] # 스왑
else:
break
return arr
print('삽입정렬 : ',insert_sort(arr))
#----------- 퀵정렬 O( nlog(n) ) -----------#
def quick_sort(arr):
if len(arr) < 2:
return arr
pivot = 0 # pivot, i(끝에서부터왼쪽, pivot보다작은값), j(pivot에서부터오른쪽, pivot보다큰값)
i=len(arr)-1
j=pivot+1
while True:
while arr[pivot] < arr[i]:
i-=1
while arr[pivot] > arr[j]:
j+=1
if j == len(arr):
break
if i < j: # i와 j가 엇갈린 경우
arr[pivot],arr[i]=arr[i],arr[pivot] # 이제 arr[i]는 고정 / arr[i]을 pivot으로 왼쪽, 오른쪽 또 정렬해주면 된다.
break
else: # 아직 엇갈리지 않은 경우
arr[i],arr[j]=arr[j],arr[i]
return quick_sort(arr[:i])+[arr[i]]+quick_sort(arr[i+1:])
print(' 퀵 정렬 : ',quick_sort(arr))
#----------- 병합정렬 O( nlog(n) ) -----------#
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
left = arr[:mid] # 리스트를 반으로 나누기
right = arr[mid:]
left_merging = merge_sort(left) # 리스트길이가 1이 되어 return될때까지 계속 재귀
right_merging = merge_sort(right)
# 여기서부터 리스트길이가 1이되어 arr가 return되며, 다시 거슬러 올라가는 부분 (left_merging 과 right_merging 의 값이 구해진 시점 이후)
merging=[] # left_merging과 right_merging이 정렬되며 합쳐질 리스트 선언-----------------------------------------------------------
l_idx = 0
r_idx = 0
l_max = len(left_merging)-1
r_max = len(right_merging)-1
while (l_idx <= l_max) and (r_idx <= r_max):
if left_merging[l_idx] < right_merging[r_idx]:
merging.append(left_merging[l_idx])
l_idx += 1
else:
merging.append(right_merging[r_idx])
r_idx += 1
# left_merging 이나 right_merging 중 한 쪽이 모두 merging으로 들어가 while문 종료된 시점. 나머지 부분 붙여준다.
if l_idx > l_max: # left_merging이 모두 소비된 경우
merging.extend(right_merging[r_idx:])
else: # right_merging이 모두 소비된 경우
merging.extend(left_merging[l_idx:])
# ------------------------------------------------merging 완성---------------------------------------------------------------------
return merging
print('병합정렬 : ',merge_sort(arr))