정렬은 데이터를 특정 기준에 따라서 순서대로 나열하는 것을 말한다. 데이터를 오름차순이나 내림차순으로 정렬해서 사용하는 경우가 있기 때문에, 많이 사용되는 알고리즘 중 하나이다. 이진탐색을 위한 전처리 과정으로도 정렬이 필요하다. 선택정렬, 삽입정렬, 퀵 정렬, 계수 정렬과 파이썬 내장 라이브러리를 통한 정렬에 대한 포스트이다. 각각 시간 복잡도와, 알고리즘에 대한 설명과 실제 데이터 정렬시 어떻게 되는지, 파이썬으로 구현하는 방법까지를 포함하고 있다.
선택 정렬
- 시간 복잡도 :
데이터가 무작위로 여러개 있을 때, 매번 가장 작은 값을 선택하는 알고리즘이다. 먼저, 정렬되지 않는 데이터 중에서 가장 작은 값과 맨 앞에 위치한 데이터와 교환한다. 그다음 맨 앞 데이터를 제외한 나머지 데이터에서 또 가장 작은 값을 선택해 두 번째 위치에 데이터를 둔다. 이렇게 계속해서 정렬되지 않은 데이터에서 가장 작은 값을 선택해 연속해서 차례로 앞에 둔다. 가장 원시적인 방법이라 할 수 있다. 예시 데이터로 어떻게 동작하는지 파악해보자
정렬되지 않은 데이터에서 가장 작은값을 차례로 앞에 위치시키는 것을 알 수 있다. N개의 데이터가 있을 때, 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.
- python 코드
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)가장 작은 값이 위치할 인덱스를 i로 설정하고, i+1부터 데이터를 모두 탐색해 가장 작은 값을 i번째 인덱스와 교환하여 가장 작은 값을 i번째 인덱스에 위치시키는 것을 반복하는 것으로 정렬을 마친다.
선택 정렬은 N-1번 만큼 가장 작은 수를 찾아 교환하는 작업을 수행한다. 이때 가장 작은 수를 찾는 연산의 수행시간은 N, N-1, N-2,,,2 로 볼 수 있다. 수행 횟수가 진행될만큼 작은 수를 찾을 데이터의 총량이 줄어들기 때문이다. 이는 근사치로,
로 표현할 수 있다. 이를 빅오 표기법으로 로 표현할 수 있다. 직관적으로, 2중 반복문이기 때문에 쉽게 을 생각할 수 있다. 선택 정렬은 다른 정렬 알고리즘보다 비효율적이지만, 특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 자주 있기 때문에, 선택 정렬의 코드 부분을 응용할 능력을 키워야한다.
삽입 정렬
- 시간 복잡도 :
데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 것으로 정렬을 진행한다. 삽입 정렬은 필요할 때만 위치를 바꾸기 때문에, 주어진 데이터가 이미 거의 정렬된 상태라면 훨씬 효율적이다. 삽입 정렬은 데이터가 적절한 위치에 삽입되기전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 예시 데이터로 어떻게 동작하는지 파악해보자.
첫번째 데이터는 이미 정렬되어있다고 판단하고, 두번째 데이터부터 크기 비교후 삽입을 시작한다. 정렬이 진행되며, 데이터가 삽입될 수 있는 위치는 점점 늘어난다. 위는 오름차순으로 정렬하는 것을 기준으로 작성한 것이다.
정렬이 이루어진 원소들(노란색 하이라이트 된 원소들)은 항상 오름차순을 유지하고 있다. 이 특징 때문에, 특정 데이터가 삽입될 위치를 선정할 때, 삽입될 위치를 찾기 위해 데이터를 한칸씩 좌측으로 이동하는데, 앞으로 삽입할 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.
- python 코드
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)앞서 설명한 것과 같이 오른쪽 끝에서부터 한칸씩 비교하며 원소를 바꾸다가 왼쪽에 위치한 값이 더 작으면 break를 사용해 정렬을 멈추는 것을 알 수 있다. 위의 사진에서의 예시에서 두차례 더 실행한 경우 아래와 같은 상황이 되는데, 이해에 도움이 될 것이다.
선택정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 따라서 시간 복잡도는 이다. 이미 거의 정렬된 상태로 입력이 주어진다면 최대 의 시간복잡도까지도 가질 수 있다. 이때는 퀵 정렬보다 더 성능적으로 효율적이다.
퀵 정렬
- 시간 복잡도 : 평균적으로, 최악의 경우,
퀵 정렬은 가장 많이 사용되는 알고리즘이다.
기준 데이터를 설정하고, 그 값보다 큰 값과 작은 값의 위치를 바꾸면 어떨까?
퀵 정렬은 기준을 설정한 다음, 해당 기준보다 큰 수와 작은 수를 교환하고 리스트를 반으로 나누는 방식으로 동작한다. 데이터가 이미 정렬이 되어있다면, 효율이 떨어지지만, 데이터의 특성파악이 어려울 시 사용하면 효과적이다. 기준값인 pivot을 설정하는 방법에 따라 다양한 퀵 정렬알고리즘이 가능하지만, 본 포스트는 호어분할 방식(리스트에서 첫번째 data가 pivot)을 사용하였다.
pivot을 기준으로 큰값과 작은 값을 모두 나눈 후에 pivot보다 작은 값들, 큰값들을 또 다시 퀵정렬을 처음부터 수행한다. 예를들어 좌측으로 나눠졌던 1,4,2,0,3 의 데이터에 대해선 아래와 같이 퀵 정렬이 이루어진다.
실제로 퀵정렬은 재귀함수를 통해서 간결하게 구현할 수 있다. pivot을 기준으로 나눈 값들을 계속해서 퀵 정렬을 수행해가며, 최종적으로 나눠진 리스트가 원소가 1개가 될때까지 분할 및 정렬을 계속 반복한다.
- python 코드
array=[5,7,9,0,3,1,6,2,4,8]
def quick_sort(array,start,end):
if start>=end:
return # element 1개 일때 return
# pivot, pivot과 비교할 원소의 위치 가리키는 left,right
pivot=start
left=start+1
right=end
while left<=right:
while left<=end and array[left]<=array[pivot]:
left+=1 # pivot보다 큰 데이터 찾을 때까지 left 증가
while right>start and array[right]>=array[pivot]:
right-=1 # pivot보다 작은 데이터 찾을 때까지 right감소
if left>right: #엇갈린 경우
array[right],array[pivot]=array[pivot],array[right] #pivot과 작은 값 교환
else:
array[left],array[right]=array[right],array[left]
quick_sort(array,start,right-1) # 분할된 왼쪽 리스트에서 quick 정렬 수행
quick_sort(array,right+1,end) # 분할된 오른쪽 리스트에서 quick 정렬 수행
quick_sort(array,0,len(array)-1)
print(array)left: pivot에 해당하는 값보다 큰 값을 가리키는 cursor
right: pivot에 해당하는 값보다 작은 값을 가리키는 cursor
left,right의 위치가 엇갈리면 pivot에 해당하는 값과 교환하고, 그렇지 않다면,left와 right를 교환하며, 분할된 리스트들이 길이가 1이 될때까지 재귀호출을 진행하여 정렬하는 것을 알 수 있다. 또한, 조금 더 python 답게 직관적으로 구현할 수 있다.
array=[5,7,9,0,3,1,6,2,4,8]
def quick_sort(array):
if len(array)<=1: # list 원소가 1개 남아있다면 종료 및 array 반환
return array
pivot=array[0]
others=array[1:] # pivot에 해당하는 원소 제외 나머지 데이터
left_side=[x for x in others if x<=pivot] # pivot 값보다 작은 데이터는 left_side에 할당
right_side=[x for x in others if x>pivot] # pivot 값보다 큰 데이터는 right_side에 할당
return quick_sort(left_side)+[pivot]+quick_sort(right_side)
print(quick_sort(array))pivot값을 가운데로 두고, left side와 right side에 pivot값을 기준으로 나눈 값을 실제로 부여하며, list단위로 표현해 좀 더 직관적이게 구현도 가능하다.
pivot값이 정확히 중앙값에 해당하는 값을 고르게 된다면, 분할이 이루어지는 횟수가 기하급수적으로 감소하게 된다.
반대로 입력되는 데이터가 이미 어느정도 정렬이 되어있어서 pivot이 계속해서 제일 작은값,큰값에 해당하는 혹은 그에 가까운 값이 선택되면 오히려 이전의 삽입정렬보다 더 성능이 안좋게 나올 수 있다. 이에 파이썬 내장 라이브러리에서의 정렬 알고리즘은 pivot을 선택하는 로직을 더해서 의 성능을 보장해준다.
계수 정렬
- 시간 복잡도, 공간복잡도
계수 정렬은 특정 조건에만 사용하는게 좋지만, 굉장히 빠른 정렬 알고리즘이다. 모두 양수인 데이터 N개에 최댓값 K를 가질때 위와 같은 시간 복잡도를 가진다. 계수정렬은 주어진 데이터의 최대값까지의 크기를 가지는 리스트를 선언한 후, 주어진 데이터를 한번 순회하며 각 원소 값들을 count해주는 것이다. 따라서, 가장 큰값과 작은 값의 차이가 1,000,000보다 작은 경우 정수형태 표현일때만 사용 가능하다. 이는 앞선 정렬알고리즘과 다르게, 비교 기반 알고리즘이 아니다. 별도로 리스트를 선언하고 그 안에 정렬 정보를 넣는 알고리즘이다. 원래 정렬하려던 데이터의 각 숫자들이 몇번 등장했는지 count하여 각 count 횟수만큼 차례로 출력하면 끝이다.
array=[7,5,9,0,3,1,6,2,0,1,4,8,0,5,2]
count=[0]*(max(array)+1) # max value까지 index가지는 count list
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=" ")계수 정렬은 데이터의 크기가 많이 중복되어 있을수록 유용하다. 하지만, 최대값이 너무 크다면, 그 값에 맞는 리스트의 크기가 필요하기 때문에, 시간복잡도 뿐 아니라 공간복잡도도 어느정도 생각을하고 사용해야한다.
파이썬 내장 라이브러리
기본적으로 sorted 메서드를 통해서 정렬할 수 있다. 파이썬 내장 라이브러리에서의 정렬 메서드들은 의 시간복잡도를 보장한다. 직접 퀵 정렬을 구현하는 것보다 효율적이다.
array=[7,5,9,0,3,1,6,2,4,8]
result=sorted(array)
print(result)리스트 객체의 내장 함수인 sort()를 이용해서 내부 원소를 바로 정렬하는 것도 가능하다. 이는 따로 반환하는 값은 없이 내부 원소를 정렬해주는 메서드이다. 또한, key 매개변수를 통해서 어떤 원소를 기준으로 정렬할 것인지 정할 수 있다. 이때 람다함수를 이용해서 적용 가능하다. 아래는 튜플 리스트인데 튜플의 1번째 값을 기준으로 정렬하기 위해서 작성한 코드이다.
array=[('바나나',2),('사과',5),('당근',3)]
array.sort(key= lambda x : x[1])
print(array)정렬 문제 유형
정렬 문제 유형은 아래 세가지로 보통 등장한다
- 정렬 라이브러리로 풀 수 있는 문제
정렬 라이브러리의 메서드를 사용할 줄알면 문제없이 해결할 수 있다.
- 정렬 알고리즘의 원리를 물어보는 문제
선택,삽입,퀵 정렬 등의 알고리즘의 원리를 알아야 풀 수 있다.
- 더 빠른 정렬이 필요한 문제
퀵 정렬 기반의 정렬 기법으로 풀 수 없어 다른 정렬 알고리즘을 사용하거나 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야한다.
Reference
이것이 취업을 위한 코딩 테스트다 with 파이썬
