다른 정렬 알고리즘 보기

Sorting1 - bubble sort, selection sort, insertion sort
sorting2 - mergesort, quicksort, heapsort

마지막 시간!

• sorting 마무리 시간입니다. 지금까지 배워온 정렬은 두 수의 대소를 비교하는 정렬이었습니다. 이와 달리 시간복잡도를 $O(n)$까지 낮추는 non-comparison algorithm인 counting sort(계수정렬), radix sort(기수정렬), 그리고 graph 이론을 결합한 topological sort(위상정렬) 로 sorting algorithm 공부를 마무리해 봅시다!

📌counting sort

1. input array의 각 값들을 index, 그 개수를 value로 하는 counting array를 생성합니다.

2. counting array를 cumulative 하게 update합니다.
   

3. output array를 각 value의 위치에 알맞게 mapping시킵니다. mapping 후에는 값을 1씩 줄여가면서 차례대로 sorting 하며 output array를 완성합니다.
   

example code

array = [2, 0, 1, 4, 5, 4, 3, 2, 0, 1, 1, 0, 5, 4, 3]

def counting_sort(arr):
  # counting array 생성
  count_arr = [0]*(max(arr)+1)
  # index별 counter
  for num in arr:
    count_arr[num]+=1
  # return count_arr
  # counting arr -> cumulative list로 변환
  for i in range(len(count_arr)-1):
    count_arr[i+1]+=count_arr[i]
  # output array 생성
  output_arr = [-1]*len(arr)
  # 역순으로 array indexing 및 정렬
  for i in range(len(arr)-1,-1,-1):
    num = arr[i]
    output_arr[count_arr[num]-1]=num
    count_arr[num]-= 1

  return output_arr

counting_sort(array)

>>> [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5] # sorting 완료!

Time Complexity

• 데이터 개수가 n 일때
  - input array로부터 counting array 생성 : $O(n)$
  - counting array cumulative 하게 update : $O(max)(array의 최댓값)$
  - output array 생성 : $O(n)$

  max값이 매우 클경우, counting array의 길이로 연결되어 메모리 공간을 차지하게 됩니다. 따라서 array의 최댓값 크기에 따라 $O(n)$보다 커질수도, 그대로 해당될 수도 있습니다.

  ---

📌radix sort

[https://brilliant.org/wiki/radix-sort/]

• 자리수 별로 counting sort 하는 알고리즘이라고 생각하면 됨
• 기수별로 비교 없이 정렬하는 알고리즘(with no comparison)
• 가장 낮은 자리수부터 정렬하는 LSD, 가장 높은 자리수부터 비교하는 MSD가 있음
• 부동소수점이 없는 int type의 정수만 정렬 가능
• k값이 작을수록 더 빠르게 정렬 가능!

code

class method로 counting sort 활용하여 구현한 결과입니다.

class RadixSort:
  def __init__(self,array):
    self.array = array

  def radix_sort(self):
    max1 = max(self.array)
    exp = 1
    while max1/exp>0:
      self.count_sort(self.array, exp)
      exp*=10

  def count_sort(self,arr,k): #k는 가장 큰 데이터의 자릿수
    output_arr = [0] * len(arr)
    count_arr= [0] * 10 # 각 자릿수별로 비교하기 때문에 0~9면 충분 

    for num in arr:
      idx = num//k  # 자릿수로 나눔
      count_arr[idx%10] +=1

    for i in range(len(count_arr)-1): # 8까지 감
      count_arr[i+1] += count_arr[i]

    for i in range(len(arr)-1,-1,-1):
      _idx = (arr[i]//k)%10
      output_arr[count_arr[_idx]-1]=arr[i]
      count_arr[_idx]-= 1
    
    # 반복작업 위한 복사
    for i in range(len(arr)):
        arr[i] = output_arr[i]

numbers = [ 170, 45, 75, 90, 802, 24, 2, 66] 
arr = RadixSort(numbers)

print(arr.array)
arr.radix_sort()
arr.array

>>> [170, 45, 75, 90, 802, 24, 2, 66] sorting 전 array
>>> [2, 24, 45, 66, 75, 90, 170, 802] sortin 후 array

Time Complexity

• k는 가장 큰 데이터의 자릿수
• counting sort를 k자리에 대하여 각각 looping

---

📌topological sort

그래프에 대해 공부가 필요한 분은 Graph 자료구조 개념을 참고하세요.

• 순서가 정해져있는 작업에 있어 순서를 결정해주는 알고리즘
• Graph 개념을 도입, sorting될 값들이 graph의 node에 대응됨
• DAG(Directed Acyclic Graph) 를 활용하여, 노드들 사이에 선후관계를 중심으로 정렬하는 알고리즘
• DAG구조에 따라 여러 개의 답이 존재할 수 있음

Example

in-degree가 언급된 아래 그래프와 정렬된 결과물을 넣을 빈 array를 떠올려 봅시다.

1. incoming edge 가 없는 node들을 골라 봅시다. -> A, F
2. 그 중에서도 A를 source node로 선정합니다. node와 그로부터의 edge를 제거한 후 output array에 append합니다.

3. in-degree를 update하고 in-degree 값이 0인 node를 제거 및 list에 append합니다.

4. 1~3 과정 반복합니다.

아래와 같은 결과를 얻게 됩니다.

• 만약 F를 source node로 택했다면 [F,A,B,C,D,E] 가 됩니다. 이처럼 여러 결과물을 얻을 수 있는 것이 위상정렬의 큰 특징입니다.

code (아래 그래프 정렬 예시)

from collections import defaultdict
# graph class 정의

class Graph:
  def __init__(self,n):
    self.graph = defaultdict(list)
    self.N = n

  def addEdge(self,m,n): # m 노드 -> n 노드 추가
    self.graph[m].append(n)
  def sortUtil(self,n,visited,stack): # DFS 구현
    visited[n] = True
    for elem in self.graph[n]: #n 노드로부터 outgoing edge
      if not visited[elem]:
        self.sortUtil(elem,visited,stack) # 재귀적 호출
    stack.insert(0,n) #맨 앞 index에 n 노드를 추가

  def topologicalSort(self): 
    visited = [False]*self.N
    stack = []
    for elem in range(self.N): # N개의 node를 통하여 looping. 
      if not visited[elem]: 
         self.sortUtil(elem,visited,stack)
    print(stack) # 결과물 출력


graph = Graph(5)
graph.addEdge(0,1);
graph.addEdge(0,3);
graph.addEdge(1,2);
graph.addEdge(2,3);
graph.addEdge(2,4);
graph.addEdge(3,4);

print("The Topological Sort Of The Graph Is:  ")

graph.topologicalSort()

>>> The Topological Sort Of The Graph Is:  
>>> [0, 1, 2, 3, 4]

🤩 topological sort 정리

1. in-degree 값이 0인 node(incoming edge가 없는 node)를 source node로 선정합니다.
2. source node 및 그 node의 outgoing edge를 모두 제거하고, output array에 node 값을 추가합니다.
3. 각 node 의 in-degree 값들을 update합니다.
4. 1~3 과정을 반복합니다.

Time Complexity

• $m$ : graph에서 edge 개수
• $n$ : graph에서 node 개수
• n개의 node에 대하여 m개의 edge에 대해 loop를 돌리게 됨

이로서 sorting 알고리즘 정리 끝!😆

Reference

• https://elrion018.tistory.com/37
• https://devjin-blog.com/sort-algorithm-9/
• https://favtutor.com/blogs/topological-sort-python