들어가기 전에 ..
정렬(Sorting) : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
오늘은 여러 정렬 알고리즘 중 선택정렬, 삽입정렬, 퀵정렬, 계수정렬에 대해서 다루도록 하겠다.
선택 정렬
"가장 작은 것을 선택"하는 방법
가장 작은 것을 선택해서 앞으로 보내는 과정을 반복하면 전체 데이터가 정렬된다.
(정렬할 데이터에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다.)
❗ 앞쪽은 이미 정렬되어 있으므로 제외하고 정렬되지 않은 뒷부분에 대해서만 정렬을 진행하면 된다.
0~9까지 카드가 섞여있을 때 이를 선택 정렬을 통해 정렬하면 ..
[이코테 157,158p 참고]
가장 작은 데이터를 앞으로 보내는 과정을 9번 반복하면 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다.
-> 따라서 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.
소스코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i # 가장 작은 원소의 인덱스
for j in range(i+1, len(array)): # 정렬이 된 데이터를 제외하고 정렬이 필요한 부분에 대해서만 반복
if array[min_index] > array[j]: # 정렬되지 않은 데이터 중 가장 작은 데이터 찾기
min_index = j
array[i], array[min_index] = array[min_index], array[i] # 가장 작은 데이터와 현재 인덱스의 데이터 스와프
print(array)파이썬에서는 위 소스코드의 마지막줄과 같이 간단히 리스트 내 두 원소의 위치를 스와프할 수 있다.
그러나 다른 대부분 프로그래밍 언어에서는 명시적으로 임시 저장용 변수(ex. temp)를 만들어 두 원소의 값을 변경해야 한다.
시간 복잡도
선택 정렬은 N-1번 만큼 가장 작은 수를 찾아 맨 앞으로 보내고, 매번 가장 작은 수를 찾기 위해 비교 연산을 한다.
연산 횟수는 N + (N-1) + ... + 2 = N(N+1)/2 = (N^2+N)/2 => O(N^2)
-> 직관적으로 소스코드 상에서 2중 반복문이 사용되었으므로 O(N^2)라고 이해할 수 있다.
시간 복잡도 O(N^2)는, 정렬해야 할 데이터 개수가 100배 늘어나면 수행시간은 10,000배로 늘어남을 뜻한다.
삽입 정렬
데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입한다.
필요할 때만 위치를 바꾸므로 "데이터가 거의 정렬되어 있을 때" 훨씬 효율적이다.
특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
삽입 정렬은 두번째 데이터부터 시작한다. -> 첫번째 데이터는 그 자체로 정렬되어 있다고 판단한다.
- 선택 정렬에 비해 구현 난이도는 높지만, 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다.
-> 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 필요할 때만 위치를 바꾼다.
0~9까지 카드가 섞여있을 때 이를 선택 정렬을 통해 정렬하면 ..
[이코테 157,158p 참고]
적절한 위치에 삽입하는 과정을 N-1번 반복하면 모든 데이터가 정렬된다.
또한 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 것이 큰 특징이다.
0️⃣ 5️⃣ 7️⃣ 9️⃣ 3 1 6 2 4 8 에서는 3이 어떤 위치에 들어갈 지 판단한다.
이때 3 이전 0 5 7 9는 모두 정렬이 끝나 오름차순을 유지하고 있는 것을 확인할 수 잇다.
3은 한칸씩 왼쪽으로 이동하다가 ❕❗자신보다 작은 '0'을 만났을 때❕❗ 그 위치에 삽입된다.
특정한 데이터의 왼쪽에 있는 데이터들은 ❕❗이미 정렬이 완료된 상태❕❗이므로 자기보다 작은 데이터를 만났다면 더이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 된다.소스코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)): # 두번째 데이터부터 정렬 시작
for j in range(i, 0, -1): # 정렬된 데이터를 뒤에서 앞으로 오며 삽입할 위치를 찾음
if array[j] < array[j-1]: # 한칸씩 왼쪽으로 이동시킴
array[j], array[j-1] = array[j-1], array[j]
else: # array[j]가 더 크면 (array[j]보다 작은 원소를 만나면) 그 위치에서 멈춤
break
print(array)시간 복잡도
삽입 정렬의 시간 복잡도는 O(N^2) <- 반복문이 2번 중첩되어 사용됨
❗ 삽입 정렬은, 현재 리스트의 데이터가 거의 정렬되어 있는 상태면 매우 빠르게 동작한다
-> 최선의 경우 시간 복잡도 O(N)
퀵 정렬
선택 정렬, 삽입 정렬과 비교했을 때, 가장 많이 사용되는 알고리즘
"기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자"
피벗(pivot) : 큰 숫자와 작은 숫자를 교환하기 위한 "기준"
-> 퀵 정렬에서 피벗을 어떻게 설정할 것인지 명시해야 한다. 주로 리스트 첫번째 데이터를 피벗으로 정한다.
1️⃣피벗 설정 후, 리스트의 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그리고 큰 데이터와 작은 데이터의 위치를 교환해준다.
2️⃣과정을 진행해나갈 때 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈릴 경우, '작은 데이터'와 '피벗'의 위치를 서로 변경한다.
-> 분할완료) 이렇게 하면 피벗을 기준으로 왼쪽에 있는 데이터는 모두 피벗보다 작고, 오른쪽에 있는 데이터는 모두 피벗보다 큰 것을 확인할 수 있고, 이렇게 위치하도록 하는 작업을 분할(divide) 혹은 파티션(partition)이라고 한다.
위 과정 후, 왼쪽 리스트와 오른쪽 리스트에서 각각 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어진다.
퀵 정렬은 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. 이는 "재귀 함수" 동작 원리와 같다.
그렇다면 재귀함수 종료조건은 무엇일까?
퀵 정렬은 현재 리스트의 데이터 개수가 1개인 경우 종료된다.
소스코드
아래는 직관적인 형태의 퀵 정렬 소스코드이다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left <= right: # 엇갈리기 전까지
while left <= end and array[left] <= array[pivot]: # 피벗보다 큰 데이터를 찾을 때까지 반복
left += 1
while right > start and array[right] >= array[pivot]: # 피벗보다 작은 데이터를 찾을 때지지 반복
right -= 1
if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
array[right], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
# 분할 후 왼쪽 부분과 오른쪽 부분에 대해 각각 정렬 수행 - 재귀호출
quick_sort(array, start, right-1)
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array)-1)
print(array)다음은 파이썬의 장점을 살려 짧게 작성한 퀵 정렬의 소스코드이다.
직관적인 코드에서는 피벗과 데이터를 비교하는 비교 연산 횟수가 증가해 시간 면에서 비효율적인 부분을 개선하였다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
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))
시간 복잡도
퀵 정렬의 평균 시간 복잡도는 O(NlogN)
cf. 선택 정렬과 삽입 정렬은 O(N^2)
데이터 개수가 N개 일 대 높이는 약 log N
ex. 8개 -> 4/4개 -> 2/2/2/2개 -> 1/1/1/1/1/1/1/1개로 3단
-> 분할이 이루어지는 횟수가 기하급수적으로 감소한다.
-> 데이터 개수 N이 1,000일 때 log2(N)은 10 정도로 상대적으로 매우 작은 수이다.
데이터 개수가 많을수록 퀵 정렬은 선택 정렬, 삽입 정렬에 비해 압도적으로 빠르게 동작한다.
파이썬의 정렬 라이브러리
sorted() 함수 : 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다.
시간 복잡도 O(NlogN)을 보장한다.
