정렬 알고리즘 - 선택정렬, 삽입정렬, 퀵정렬, 계수정렬

정렬(Sorting) 

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
• 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다.

각 정렬 알고리즘 비교

정렬 알고리즘	핵심 아이디어	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법	O(N^2)	O(N)	아이디어가 매우 간단합니다.
삽입 정렬	데이터를 앞쪽에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때 가장 빠름
퀵 정렬	기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법	O(NlogN)	O(N)	대부분에 경우에 가장 적합 충분히 빠름
계수 정렬	특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법	O(N+K) (K는 데이터 중에서 가장 큰 양수)	O(N+K) (K는 데이터 중에서 가장 큰 양수)	데이터의 크기가 한정 되어있는 경우에만 사용가능 매우 빠름

 

선택 정렬(Selection Sort)

• 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것 
• 가장 원시적인 방법으로 매번 '가장 작은 것을 선택' 한다는 의미

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)

* 스와이프: 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업

 

선택정렬의 시간 복잡도: O(N^2)

• 선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야한다.
• 또한 매법 가장 작은 수를 찾기 위해 비교 연산이 필요함

선택 정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교해 봤을 때 매우 비효율적임.

다만, 특정 리스트에서 가장 작은 데이터를 찾는 일이 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요는 있다.

 

---

삽입 정렬(Insertion Sort)

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

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) #인덱스 i부터 1까지 감소하며 반복하는 문법
    if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동
      array[j], array[j-1] = array[j-1], array[j]
    else: #자기보다 작은 데이터를 만나면 그 위치에서 멈춤
      break
      
 print(array)

삽입 정렬의 시간 복잡도: O(N^2)

• 선택정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태에서는 매우 빠르게 동작
• 최선의 경우 O(N)의 시간 복잡도를 가진다.

---

퀵 정렬(Quick Sort)

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 교환한 후 리스트를 반으로 나누는 방식으로 동작
• 가장 많이 사용되는 알고리즘
• 피벗(Pivot): 큰 수와 작은 수를 교환할 때, 교환하기 위한 '기준'

 

호어 분할 방식(Hoare Partition) 기준 퀵 정렬

• 리스트에서 첫 번째 데이터를 피벗으로 정한다.
• 왼쪽 부터는 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다
• 큰 데이터와 작은 데이터의 위치를 서로 교환해 준다.
• 위 과정을 반복하면 '피벗'에 대하여 정렬이 수행됨.
• 왼쪽부터 찾는 값과 오른 쪽 부터 찾는 값의 위치가 서로 엇갈린 경우에는 '작은 데이터'와 '피벗'의 위치를 서로 변경한다.
• 분할, 파티션: 피벗의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 5보다 크다
• 이 상태에서 왼쪽과 오른쪽 리스트를 개별적으로 정렬 시킴.

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)

• 퀵 정렬의 시간 복잡도:O(NlogN)
• 최악의 경우 시간 복잡도가 O(N^2)
• 이미 데이터가 정렬되어 있는 경우에는 매우 느림

 

---

계수 정렬(Count Sort)

• 특정한 조건(데이터의 크기 범위가 제한되어 정수로 형태로 표현할 수 있을 때)이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
• 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다

#모든 원소의 값이 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=' ')

계수 정렬의 시간 복잡도:O(N+K)

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할때 계수 정렬의 시간 복잡도는 O(N+K)이다.

 

계수 정렬의 공간 복잡도

때에 따라서 심각한 비효율성

- 데이터가 0과 9999999 단 두개만 존재해도 리스트의 크기가 100만 개가 되도록 선언해야함.