정렬 알고리즘

선택 정렬 (Selection Sort)

• 최소값을 선택하여 정렬하는 알고리즘

def selection_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

삽입 정렬 (Insert Sort)

• 정해진 위치를 찾아서 삽입하는 알고리즘

def insert_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

버블 정렬 (Bubble Sort)

• 변경 여부에 따라 버블처럼 정렬하는 알고리즘

def bubble_sort(a):
    n = len(a)
    while True:
        changed = False
        for i in range(0, n-1):
            if a[i] > a[i + 1] :
                a[i], a[i + 1] = a[i + 1], a[i]
                changed = True
        if changed == False:
            return

병합 정렬 (Merge Sort)

• 중간값을 기준으로 정렬하여 합치는 알고리즘

def merge_sort(a):
  n = len(a)
  if n <= 1:
    return

  mid = n // 2
  g1 = a[:mid]
  g2 = a[mid:]
  merge_sort(g1)
  merge_sort(g2)

  ia, i1, i2 = 0, 0, 0
  while i1 < len(g1) and i2 < len(g2):
    if g1[i1] < g2[i2]:
      a[ia] = g1[i1]
      ia += 1
      i1 += 1
    else:
      a[ia] = g2[i2]
      ia += 1
      i2 += 1

  while i1 < len(g1):
    a[ia] = g1[i1]
    ia += 1
    i1 += 1
  while i2 < len(g2):
    a[ia] = g2[i2]
    ia += 1
    i2 += 1

퀵 정렬 (Quick Sort)

• 피벗값을 기준으로 나누어서 정렬하는 알고리즘

def quick_sort_sub(a, start, end):
  if end - start <= 0:
    return

  pivot = a[end]
  i = start
  for j in range(start, end):
    if a[j] <= pivot:
      a[i], a[j] = a[j], a[i]
      i += 1
  a[i], a[end] = a[end], a[i]

  quick_sort_sub(a, start, i - 1)
  quick_sort_sub(a, i + 1, end)

def quick_sort(a):
  quick_sort_sub(a, 0, len(a) - 1)