[Python] 정렬 알고리즘 종류(버블, 카운팅, 선택, 퀵, 삽입, 병합)

정렬

• 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순 : Ascending) 혹은 그 반대의 순서(내림차순 : Descending)대로 재배열하는 것
• 키 : 자료를 정렬하는 기준이 되는 특정 값

---

대표적인 정렬방식의 종류

버블 정렬(Bubble Sort)

• 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

• 정렬 과정

  • 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
  • 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
  • 교환하며 자리를 이동하는 모습이 마치 물 위에 올라오는 거품 모양과 비슷하다고 하여 버블정렬이라 함

• 시간 복잡도 : $O(n^2)$

  ex) [5, 9, 2, 3, 6] 을 버블정렬하는 과정
  - 1 번째 패스(구간 [0:4]) : [5, 9, 2, 3, 6]→[5, 2, 9, 3, 6]→[5, 2, 3, 9, 6]→[5, 2, 3, 6, 9]
  - 2 번째 패스(구간 [0:3]) : [2, 5, 3, 6, 9]→[2, 3, 5, 6, 9]→[2, 3, 5, 6, 9]
  - 3 번째 패스(구간 [0:2]) : [2, 3, 5, 6, 9]→[2, 3, 5, 6, 9]
  - 4 번째 패스(구간 [0:1]) : [2, 3, 5, 6, 9]
  - 정렬 끝 : [2, 3, 5, 6, 9]

  n = int(input())
  arr = list(map(int, input().split()))
  # arr: 정렬할 리스트, n: 원소의 개수
  
  def BubbleSort(arr, n): 
          for i in range(n-1, 0, -1):
                  for j in range(0, i):
                          if arr[j] > arr[j+1]:
                                  arr[j], arr[j+1] = arr[j+1], arr[j]
          return arr
  print(BubbleSort(arr, n))

카운팅 정렬(Counting Sort)

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

• 단, 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
  (각 항목의 발생 횟수 기록을 위해, 정수 항목으로 인덱스되는 카운트들의 배열을 사용하기 때문)

• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함

• 시간 복잡도 : $O(n)$

  def CountingSort(arr, k) # k : 배열에서 가장 큰 수
          # arr : 입력 배열(1 to k)
          # c : 카운트 배열
          c = [0]*(k+1)
          n = len(arr)
  
          for i in range(0, n): # 숫자 갯수를 카운트하여 c에 대입
                  c[arr[i]] += 1
          for j in range(1, k+1): # c[j-1]까지의 누적합을 c[j]에 대입
                  c[j] += c[j-1]
          tmp = [0] * n
          for i in range(n-1, -1, -1):
                  c[arr[i]] -= 1
                  tmp[c[arr[i]]] = arr[i]
          return tmp

선택 정렬(Selection Sort)

• 시간 복잡도 : $O(n^2)$

  arr = [4,7,1,3,5,2]
  for i in range(len(arr)-1):
      for j in range(i+1, len(arr)):
          if arr[i]>arr[j]:
                          # tmp = arr[i]
              # arr[i]=arr[j]
              # arr[j]=tmp
              arr[i], arr[j] = arr[j], arr[i] # 파이썬 스타일
  print(arr)

삽입 정렬(Insertion Sort)

• 이미 정렬된 리스트에 새로운 값을 넣고 정렬하는 경우 O(n) 시간복잡도를 가짐
• 시간 복잡도 : $O(n^2)$
• ex) [4,7,1,3,5,2] 을 삽입 정렬하는 과정

  arr = [4,7,1,3,5,2]
  result = []
  for i in range(len(arr)):
      result.append(arr[i])
      for j in range(i, 0, -1):
          if result[j]<result[j-1]:
              result[j], result[j-1] = result[j-1], result[j]
  print(result)

병합 정렬(Merge Sort)

def partition(left, right):
    pivot = arr[left]   # 피봇을 배열의 가장 왼쪽 값으로 초기화
    i, j = left, right  
    # i, j 가 교차 시, i, j는 피봇을 기준으로 작은 값과 큰 값들의 경계에 위치
    while i <= j:                 
        while i <= j and arr[i] <= pivot: # i : 왼쪽에서 오른쪽 방향으로 피봇보다 큰 값을 탐색
            i += 1
        while i <= j and arr[j] >= pivot: # j : 오른쪽에서 왼쪽 방향으로 피봇보다 큰 값을 탐색
            j -= 1
        if i < j :      # i와 j가 결정된 이후, arr[i]와 arr[j]를 SWAP
            arr[i], arr[j] = arr[j], arr[i]
    arr[left], arr[j] = arr[j], arr[left]
    return j

def quick_sort(left, right):
    if left < right: # 시작 인덱스보다 끝 인덱스가 큰 경우
        mid = partition(left, right)
        quick_sort(left, mid-1)
        quick_sort(mid+1, right)

arr = [7, 2, 5, 3, 4, 5]
n = len(arr)
quick_sort(0, n-1) # 시작 인덱스와 끝 인덱스를 인자로 전달
print(arr)

퀵 정렬(Quick Sort)

• 주어진 배열을 두 개로 분할하고, 각각을 정렬
• 병합 정렬은 두 부분으로 나누는 반면, 퀵 정렬은 분할할 때 기준 아이템(pivot item)을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킴
• 병합 정렬의 경우, 정렬이 끝나면 병합 처리가 필요하나, 퀵 정렬은 필요하지 않음
• 시간 복잡도 :

def partition(left, right):
    pivot = arr[left]   # 피봇을 배열의 가장 왼쪽 값으로 초기화
    i, j = left, right  
    # i, j 가 교차 시, i, j는 피봇을 기준으로 작은 값과 큰 값들의 경계에 위치
    while i <= j:                 
        while i <= j and arr[i] <= pivot: # i : 왼쪽에서 오른쪽 방향으로 피봇보다 큰 값을 탐색
            i += 1
        while i <= j and arr[j] >= pivot: # j : 오른쪽에서 왼쪽 방향으로 피봇보다 큰 값을 탐색
            j -= 1
        if i < j :      # i와 j가 결정된 이후, arr[i]와 arr[j]를 SWAP
            arr[i], arr[j] = arr[j], arr[i]
    arr[left], arr[j] = arr[j], arr[left]
    return j

def quick_sort(left, right):
    if left < right: # 시작 인덱스보다 끝 인덱스가 큰 경우
        mid = partition(left, right)
        quick_sort(left, mid-1)
        quick_sort(mid+1, right)

arr = [7, 2, 5, 3, 4, 5]
n = len(arr)
quick_sort(0, n-1) # 시작 인덱스와 끝 인덱스를 인자로 전달
print(arr)

---

정렬 알고리즘 비교

알고리즘	평균 수행시간	최악 수행시간	알고리즘 기법	비고
버블 정렬	$O(n^2)$	$O(n^2)$	비교 교환	쉽게 구현
카운팅 정렬	$O(n+k)$	$O(n+k)$	비교환	n이 비교적 작을 때만 가능
선택 정렬	$O(n^2)$	$O(n^2)$	비교 교환	교환의 횟수가 버블, 삽입정렬보다 작음
퀵 정렬	$O(n log n)$	$O(n^2)$	분할 정복	최악의 경우 O(n^2)이지만, 평균적으로 가장 빠름
삽입 정렬	$O(n^2)$	$O(n^2)$	비교 교환	n의 개수가 작을 때 효과적
병합 정렬	$O(n log n)$	$O(n log n)$	분할 정복	연결리스트의 경우 가장 효율적인 방식