정렬

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

 

선택 정렬

---

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.

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] #swapping
print(array)

-> O(n2)

 

선택 정렬은 다른 정렬 알고리즘이나 파이썬 기본 정렬 라이브러리와 비교햇을 때 매우 비효율적이다. 다만, 특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.

 

삽입 정렬

---

데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입한다.

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(n2)

삽입정렬은 정렬할 데이터 기준 그 앞 데이터까지는 정렬이 되어 있다고 판단하기 때문에 현재 리스트가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우 O(n)의 시간 복잡도를 가진다. 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다.

 

퀵 정렬

---

기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 대표적으로 리스트의 첫 번째 데이터를 피벗으로 설정하는 방식으로 사용한다.

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[pivot]>=array[left]:
      left+=1
    while right>start and array[pivot]<=array[right]:
      right-=1
    if left>right:
      array[pivot],array[right]=array[right],array[pivot]
    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)

데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 위처럼 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 데이터가 정렬되어 있는 경우 최악의 경우가 되어 O(n2)으로 매우 느리게 동작한다.

물론 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 시간복잡도가 O(nlogn)이 되는 것을 보장할 수 있도록 피벗값을 설정할 때 추가적인 로직을 더해준다.

 

계수 정렬

---

계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 계수 정렬은 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성하고 각 데이터가 몇 번 등장했는지 그 횟수를 기록한다.

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=' ')

-> O(N+K), N은 array의 크기, K는 array에서 최댓값

계수 정렬은 이처럼 매우 빠르게 동작할 뿐만 아니라 원리 또한 매우 간단하다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 예를 들어 0 이상 100 이하인 성적 데이터를 정렬할 때 효과적이다.

 

파이썬의 정렬 라이브러리

---

파이썬의 기본 정렬 라이브러리는 최악의 경우에도 항상 O(NlogN)을 보장한다.

문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.

특히 sorted는 리스트 뿐만 아니라 사전, 집합에 대해서도 가능하다. 다만, 반환 타입은 리스트이다.

 

+) 리스트 안에 튜플이 있는 경우 이를 정렬할 때, 튜플의 첫번째 원소, 두번째 원소 ... 순으로 기준을 정해 정렬한다.

그러나 다음과 같이 조건을 변경할 수도 있다.

result=sorted(data,key=lambda x:(-x[1],x[2],-x[3],x[0]))

 

파이썬의 정렬 라이브러리는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘으로 직접 퀵 정렬을 구현할 때보다 더욱더 효과적이다. 따라서 문제에서 별도의 요구가 없고 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.