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

 

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

 

정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 또한 프로그램에서 데이터를 가공할 때 어떤 식으로든 정렬해서 사용하는 경우가 많기 때문에 정렬 알고리즘은 프로그램 작성 시 가장 많이 사용되는 알고리즘 중 하나이다. 

 

 

선택 정렬(Selection Sort)

💡 아이디어

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

=> 매번 가장 작은 것을 선택한다

출처: 위키백과 -  선택 정렬

 

💡 소스코드

def sel_sort(array):
  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] # swap

  return array

# 시간복잡도: O(N^2)

 

 

 

 

삽입 정렬(Insertion Sort)

💡 아이디어

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

출처: 위키백과 - 삽입 정렬

 

💡 소스코드

def ins_sort(array):
  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

  return array

# 시간복잡도: O(N^2)

삽입 정렬의 경우 정렬된 리스트를 인자로 주었을 때 O(N)에 작동한다. 이어서 나올 퀵 정렬과 비교했을 때, 보통의 경우 삽입 정렬이 더 비효율적이지만 정렬이 거의 되어 있는 상황에서는 더 강력하다는 것을 꼭 기억하고 잘 활용하자!!!😎

 

 

 

 

퀵 정렬(Quick Sort)

💡 아이디어

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿔보자!

 

 

💡 분할 과정

퀵 정렬은 기준(pivot)을 설정한 다음 큰 수와 작은 수를 교환한 후, 리스트를 반으로 나누는 방식으로 동작한다.

피벗을 설정하는 방법에는 여러 가지 방식이 있지만, 여기서는 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식으로 피벗을 정하겠다. 호어 분할 방식에서는 '리스트의 첫 번째 데이터'를 피벗으로 정한다. 

 

피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 바꾼다. 이 과정을 왼쪽에서 출발한 포인터와 오른쪽에서 출발한 포인터가 엇갈릴 때까지 반복한다. 

 

두 포인터가 엇갈린 시점에서, 작은 데이터와 피벗의 위치를 서로 바꾼다. 그렇게 되면 피벗의 왼쪽에는 피벗보다 작은 데이터만, 피벗의 오른쪽에는 피벗보다 큰 데이터만 존재하게 된다. 이 과정을 분할(Divide) 또는 파티션(Partition)이라고 한다. 

 

피벗에 따라 분할된 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬시키는 과정을 반복하다 보면 전체 리스트에 대하여 정렬이 이뤄지게 된다. 

 

출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 

💡 소스코드

def quickSort(array):
  if len(array) <= 1:
    return array

  pivot = array[0]
  tail = array[1:]

  leftSide = [x for x in tail if x <= pivot]
  rightSide = [x for x in tail if x > pivot]

  return quickSort(leftSide) + [pivot] + quickSort(rightSide)

# 평균 시간복잡도: O(NlogN)
# 최악의 경우: O(N^2)

퀵 정렬에서 최선의 경우는 피벗값이 정확히 리스트를 절반씩 나누는 것을 반복할 경우이다. 이 경우 시간 복잡도는 O(NlogN)이 된다. 

퀵 정렬에서 최악의 경우는 이미 정렬된 리스트를 입력으로 주었을 때이다. 이 경우 시간 복잡도는 O(N^2)이 된다. 

 

 

 

 

계수 정렬(Count Sort)

💡 계수 정렬이란?

계수 정렬은 데이터의 개수가 N, 데이터 중 최댓값이 K일 때 수행 시간 O(N + K)를 보장하는 알고리즘이다. 

 

하지만 언제나 쓰기 적합한 것은 아니고, 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 일반적으로 데이터의 max값과 min값의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 왜냐하면 계수 정렬을 수행하려면 모든 범위를 담을 수 있는 크기의 리스트가 필요하기 때문이다. 

 

계수 정렬의 수행 과정은 다음과 같다. 

1. 데이터의 (min, max) 범위를 포함하는 하나의 리스트를 생성함
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 값을 1씩 증가시킴
3. 리스트의 첫 번째 데이터부터 그 값만큼 인덱스를 출력

 

출처: https://www.programiz.com/dsa/counting-sort

 

 

💡 소스코드

def countSort(array):
  count = [0] * (max(array) + 1)

  for x in array:
    count[x] += 1

  result = []
  for i in range(len(count)):
    for j in range(count[i]):
      result.append(i)

  return result

# 시간복잡도: O(N + K)

 

 

 

 

참고자료: 이것이 취업을 위한 코딩 테스트다 with Python(나동빈 저, 한빛미디어)