정렬이란?
데이터를 특정한 기준에 따라 순서대로 나열하는 것이다.
가장 많이 사용되는 알고리즘 중 하나로, 정렬로 인해 이진 탐색이 가능해진다.(전처리 과정)
0에서 9까지의 숫자 카드를 정렬한다고 생각하면, 사람이 생각하기엔 단순한 것 같지만 컴퓨터에는 어떻게 수행할 지에 대한 과정을 상세히 명시해줘야하기 때문에 쉽지만은 않다.
많이 사용하는 종류: 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬
*내림차순 정렬은 오름차순 정렬 후 뒤집기하면 된다.
( reverse() 사용하면 O(N) 복잡도로 수행 가능하다.)
선택 정렬
가장 원시적인 방법으로, 매번 가장 작은 것을 선택한다는 의미이다.
가장 작은 데이터를 선택해서 맨 앞의 데이터와 바꾸고, 그 다음으로 작은 데이터를 선택해서 앞에서 두번째 데이터와 바꾸는 과정을 반복한다.
선택 정렬 소스코드
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[j] < array[min_index]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
print(array)
파이썬에서는 위처럼 임시 변수를 따로 만들지 않고도 간단히 리스트 안에 두 변수의 위치를 변경할 수 있다.
O(N^2)의 시간 복잡도를 가지므로 매우 비효율적이다. 하지만 특정 리스트에서 가장 작은 데이터를 찾는 일이 코테에서 잦으므로 코드에 익숙해져야한다.
삽입 정렬
데이터를 하나씩 확인하며 각 데이터의 적절한 위치를 찾아 삽입하는 알고리즘이다.
실행 시간 측면에서 선택 정렬보다 효율적이다.
삽입 정렬은 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다!
선택 정렬은 현재 데이터와 관련없이 무조건 모든 원소를 비교하는 반면에 삽입 정렬은 그렇지 않다.
특정한 데이터가 삽입되기 이전에 그 앞까지의 데이터들은 정렬되어 있다고 가정한다. 정렬된 데이터 리스트에서 적절한 위치를 찾고 그 위치에 삽입되는 것이다.
과정)
맨 앞 데이터는 정렬되었다고 보고, 그 다음 데이터부터 앞의 데이터부터 차례로 비교해서 적절한 위치를 찾아 삽입한다. 앞의 데이터들은 모두 정렬된 상태기 때문에 자신보다 작은 데이터를 만나면 그 앞에 데이터들은 살펴볼 필요 없이 그 자리에 삽입하면 되어서 효율적이다.
삽입 정렬 소스코드
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:
break
print(array)현재 데이터의 앞 데이터들은 모두 정렬이 되었다고 생각하기 때문에 그 앞만 비교해서 한칸씩 옮겨주면 된다.
만약 거의 정렬되어있는 상태라면 O(N)의 시간 복잡도를 가져서 가장 효율적인 알고리즘이 된다.
퀵 정렬
가장 많이 사용되는 정렬 알고리즘이다. 이와 비슷하게 병합 정렬도 비슷하게 빠른 알고리즘이다.
퀵 정렬은 기준 데이터인 피벗을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
과정)
일반적으로 가장 첫 데이터를 피벗으로 정하고 왼쪽에서부터 피벗보다 큰 데이터를 선택하고 오른쪽에서부터 피벗보다 작은 데이터를 선택한 후 둘의 데이터를 서로 변경해준다. 이 과정을 반복하면서 동작한다.
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[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, start, end):
#리스트가 하나 이하의 원소만을 가진다면 종료한다.
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(n^2) 이었다.
퀵 정렬의 평균 시간 복잡도는 O(NlogN)으로 매우 빠른 편이다. 만약 피벗이 정확히 반을 분배한다면 N개일 때 높이는 logN이 된다. 분할이 기하급수적으로 감소하는 것이다. 하지만 최악의 경우에는 N^2이다. 이미 정렬되어 있는 경우에는 매우 느리게 동작하는 것이다. <-> 삽입 정렬과 반대된다.
계수 정렬
특정 조건이 부합할 때만 사용되지만 매우 빠른 정렬 알고리즘이다.
데이터 개수 N, 데이터 최댓값 K일 때, 최악의 경우에도 O(N+K)를 보장한다.
별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다. 데이터 크기가 제한되어 있을 때 개수가 많더라도 빠르게 동작한다.
모두 0으로 초기화시킨 후 하나씩 확인하며 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시키면 된다.
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
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=' ')
파이썬 내장 정렬 함수
최악의 경우에도 NlogN 을 보장한다.
sorted(array) : 새로운 리스트 반환
array.sort() : 내부 원소 정렬
*key를 활용한 소스코드
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
def setting(data):
return data[1]
result = sorted(array, key=setting)
print(result)리스트의 데이터가 튜플로 구성되어 있을 때 각 데이터의 두 번째 원소를 기준으로 설정하는 경우 위와 같이 하면 잘 정렬된다.
