🔊본 포스팅은 '(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬' 유튜브 강의를 수강하고 정리한 글입니다.
정렬 알고리즘
정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.
숫자가 하나씩 적힌 10장의 카드를 오름차순으로 정렬하자.
선택 정렬
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
문제 해결
[Step 0] 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꾼다.
[Step 1] 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와 바꾼다.
[Step 2] 처리되지 않은 데이터 중 가장 작은 '2'를 선택해 가장 앞의 '9'와 바꾼다.
[Step 3] 처리되지 않은 데이터 중 가장 작은 '3'을 선택해 가장 앞의 '7'과 바꾼다.
이러한 과정을 반복하면 다음과 같이 정렬이 완료된다.
→ 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.
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] # swap
print(array)실행 결과
[0,1,2,3,4,5,6,7,8,9]삽입 정렬
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.
문제 해결
[Step 0] 첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다.
[Step 1] 이어서 '9'가 어떤 위치로 들어갈지 판단한다.
'9'는 차례대로 왼쪽에 있는 데이터와 비교해서 왼쪽 데이터보다
더 작다면 위치를 바꿔 주고 그렇지 않다면 그냥 그자리에 머물러 있도록 한다.
'9'는 '7'보다 더 크기 때문에 현재 위치 그대로 내버려둔다.[Step 2] 이어서 '0'이 어떤 위치로 들어갈지 판단한다.
'0'은 '9','7','5'와 비교했을 때 모두 작기 때문에 '5'의 왼쪽에 위치한다.이러한 과정을 반복하면 정렬이 완성된다.
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(1, len(array)): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
for j in range(i, 0, -1): # 한 칸씩 왼쪽으로 이동
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)✨ 퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(pivot)로 설정한다.
문제 해결
[Step 0] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다.
[Step 1] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '2'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.
[Step 2] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '6'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '1'이 선택된다. 단, 이처럼 위치가 엇갈리는 경우 '피벗'과 작은 데이터의 위치를 서로 변경한다.
[분할 완료] 이제 '5'의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있다. 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)이라고 한다.
[왼쪽 데이터 묶음 정렬] 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.
[오른쪽 데이터 묶음 정렬] 오른쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.
이러한 과정을 반복하면 전체 데이터에 대해서 정렬이 수행된다.
array = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
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[tight]>=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))계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다.
문제 해결
[Step 0] 가장 작은 데이터로부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다.
인덱스는 0~9의 숫자로 구성된 것을 확인할 수 있고, 이때 각 인덱스가 데이터의 값에 해당한다.
[Step 1] 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다.
각각의 데이터가 몇번씩 등장했는지 세는 방식으로 동작하는 정렬 알고리즘이다.
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0]*(max(array)+1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력