정렬 알고리즘 정리 (파이썬)

정렬이란?

• 정렬 (sorting): 어떤 데이터들이 주어졌을 때 정해진 순서대로 나열하는 것
• 프로그래밍에서 자주 사용됨
• 정렬을 위한 다양한 알고리즘이 있음

+빅오 비교 (Big O)

O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(2^n) < O(n!)

쉬운 설명을 위해 모든 예시는 오름차순 정렬을 사용함.
모든 사진의 출처는 링크로 연결함

---

1. 버블정렬 (Bubble sort)

• 인접한 두 데이터를 비교
• 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 Swap!
• 시간복잡도: O(n^2)

def bubbleSort(x):
   length = len(x)-1
   for i in range(length):
      for j in range(length-i):
         if x[j] > x[j+1]:		# 앞에가 더 크면 Swap
            x[j], x[j+1] = x[j+1], x[j]
   return x

2. 삽입정렬 (Insertion sort)

• 앞에 있는 데이터들과 비교
• 비교할 데이터보다 작은 데이터가 나오는 곳에 Insert!
• O(n^2)

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			# 반복문 멈춘 자리에 Insert
   return x

3. 선택정렬 (Selection sort)

• 데이터 중 최소값을 찾아 맨 앞과 Swap
• O(n^2)

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]	#맨 앞과 Swap
   return x

4. 병합정렬 (Merge sort)

• 재귀 활용 (분할 정복) <-아래 설명 확인
• 절반으로 잘게 자르고 다시 합병하며 정렬
• O(n*log n)

split(data_list):
   if len(data_list) <= 1:	#탈출: 더 자를수 없음
      return data_list

   mid = len(data_list) // 2	#가운데를 기준으로 나눠서 재귀
   left = split(data_list[:mid])
   right = split(data_list[mid:])
   return merge(left, right)	#병합

merge(left, right):
   merged = list()
   left_i, right_i = 0, 0

   while left_i<len(left) and right_i<len(right):
      if right[right_i] < left[left_i]:    #left, right 중 작은 값 하나씩 추가
         merged.append(right[right_i])
         right_i += 1
      else:
         merged.append(left[left_i])
         left_i += 1

   #남은 값들 추가
   while left_i < len(left):
      merged.append(left[left_i])
      left_point += 1
   while right_i < len(right):
      merged.append(right[right_i])
      right_i += 1
   return merged

5. 퀵정렬 (Quick sort)

• 기준(pivot)을 잡고 해당 값보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 Swap
• 기준을 잡는 방법은 다양함
• O(n*log n)
• 정렬 알고리즘의 꽃

def quicksort(x):
   if len(x) <= 1:		#탈출: 더 자를 수 없음
      return x
   pivot = x[len(x) // 2]	#인덱스 기준 중간값을 기준점으로
   less = []
   more = []
   equal = []
   for a in x:			#모든 값을 기준값과 비교해 3개의 그룹으로 나눔
      if a < pivot:
         less.append(a)
      elif a > pivot:
         more.append(a)
      else:
         equal.append(a)
   return quicksort(less) + equal + quicksort(more)	#재귀 및 병합

---

* 동적 계획법 & 분할 정복

a. 동적 계획법 (Dynamic Programming)

• 흔히 DP라고 불림
• 상향식 접근법: 최하위 해답을 구한 후 이를 이용해 상위 문제를 풀어가며 결국 전체 문제를 해결
• Memoization 기법 사용: 이전에 계산한 값을 저장
• 피보나치 수열 등

b. 분할 정복 (Divide and Conquer)

• 하향식 접근법: 문제를 최대한 나누어 풀고 다시 합병하여 전체 문제를 해결
• Memoization 기법 사용 X
• 퀵 정렬 등