버블정렬, 선택정렬, 삽입정렬, 힙정렬, 퀵정렬, 병합정렬

버블 정렬

---

• 햔 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복
• 시간 복잡도 O(n2), 공간 복잡도 O(n)

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

선택 정렬

---

• 수열 중에서 최솟값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업 반복
• 시간 복잡도 O(n2), 공간 복잡도 O(n)

def selectionSort(x):
  length = len(x)
  for i in range(length-1):
      indexMin = i
      for j in range(i+1, length):
          if x[indexMin] > x[j]:
              indexMin = j
      x[i], x[indexMin] = x[indexMin], x[i]
  return x

삽입 정렬

---

• 왼쪽부터 순서대로 정렬, 좌측은 정렬이 끝난 숫자, 우측은 미확인 숫자
• 우측에서 숫자를 꺼내 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식
• 시간 복잡도 O(n2), 공간 복잡도 O(n)

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

힙 정렬

• 힙 자료구조로 정렬
• 힙에 모든 숫자를 저장
• 모든 숫자(n), 각 숫자당 삽입 시간(logn) 따라서 nlog(n)
• 힙 구조에 저장된 숫자(n)에 대해 최상단 숫자를 꺼내고 정렬(logn) 따라서 nlog(n)
• 시간복잡도 O(nlogn)

병합 정렬

• 정렬하고 싶은 수열을 두 개의 수열로 분할
• 더이상 분할할 수 없으면(한개의 숫자가 되면) 병합해 나감
• 하나가 될 때까지 반복
• 시간복잡도 O(nlogn)

def merge(left, right):
  result = []
  while len(left) > 0 and len(right) > 0:
      if left[0] + right[0] < right[0]+ left[0]:
          result.append(right[0])
          del right[0]
      else:
          result.append(left[0])
          del left[0]
  return result + left + right

def merge_sort(list):
  if len(list) <= 1:
      list[0] = str(list[0])
      return list
  mid = len(list) // 2
  leftList = list[:mid]
  rightList = list[mid:]
  leftList = merge_sort(leftList)
  rightList = merge_sort(rightList)
  return merge(leftList, rightList)

def solution(numbers):
  arr = merge_sort(numbers)
  if arr[0] == '0':
      return '0'
  else :
      return ''.join(arr)

퀵 정렬

• 수열 안에서 임의로 하나를 선택하고 이 피벗 기준으로 두 그룹으로 나눔
• 각 그룹에서 또 피벗을 선택하여 계속 나눠가며 정렬을 해줌
• 시간복잡도 O(nlogn)이지만 최악의 경우(피벗이 효과적으로 역할을 못할 때) O(n2)