정렬 알고리즘

< 선택 정렬 >

1. 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

# 선택 정렬
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
  min_index = i
  for j in range(i + 1, len(array)):
    if array[min_index] > array[j]:
      min_index = j
  array[i], array[min_index] = array[min_index], array[i]

print(array)

< 삽입 정렬 >

1. 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
2. 선택 정렬에 비해 구현 난이도가 높은 편이지만 더 효율적임
3. 데이터가 어느정도 정렬되어 있을 때 효과적

# 삽입 정렬
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
  for j in range(i, 0, -1):
    if array[j-1] > array[j]:
      array[j], array[j-1] = array[j-1], array[j]
    else:
      break

print(array)

< 퀵 정렬 >

1. 기준 데이터를 설정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈
2. 병합 정렬과 더불어 정렬 라이브러리의 근간이 되는 알고리즘
3. 가장 기본은 첫 번째 데이터를 기준(Pivot)으로 설정
4. 오름차순: 왼쪽에선 pivot보다 큰 값 오른쪽에선 pivot보다 작은 값 찾음

# 퀵정렬
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
  if start >= end:
    return
  pivot = start
  left = start + 1
  right = end
  while(left <= right):
    while(left <= end and array[left] <= array[pivot]):
      left += 1
    while(right > start and array[right] >= array[pivot]):
      right -= 1
    if(left > right):
      array[right], array[pivot] = array[pivot], array[right]
    else:
      array[left], array[right] = array[right], array[left]
  
  quick_sort(array, start, right - 1)
  quick_sort(array, right + 1, end)

quick_sort(array,0,len(array)-1)
print(array)

# 파이썬의 장점을 살린 퀵정렬
def quick_sort(array):
  if len(array) <= 1:
    return array
    
  pivot = array[0]
  tail = array[1:]

  left_side = [x for x in tail if x <= pivot]
  right_side = [y for y in tail if y > pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

< 계수 정렬 >

1. 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작
2. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용
3. 최악의 경우에도 O(데이터 개수 + 데이터(양수) 중 최댓값) 보장

# 계수 정렬
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array) + 1)

for i in range(len(array)):
  count[array[i]] += 1

for i in range(len(count)):
  for j in range(count[i]):
    print(i, end = " ")

< 정렬 알고리즘 비교 >