나동빈 정렬
정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다.

선택 정렬 알고리즘

처리되지 않은 데이터 중 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
일단 구현 해 봤다.

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
idx = 0
for i in range(len(arr)):
  min_val = min(arr[idx:])
  min_idx = arr.index(min_val)
  temp = arr[idx]
  arr[idx] = arr[min_idx]
  arr[min_idx] = temp
  idx += 1
print(arr)

음.. 최소값도 찾고, 최소값의 인덱스도 찾고 있다. 그리고 중복 값이 있다면 잘못된 결과가 나왔다. 내장 함수를 사용하지 말고 해볼까!

for i in range(len(arr)):
  min_idx = i
  for j in range(i + 1, len(arr)):
    if arr[min_idx] > arr[j]:
      min_idx = j
  arr[i], arr[min_idx] = arr[min_idx],arr[i]
print(arr)

이제 잘 정렬된다. 스와프가 저렇게 되는것도 새로 알았다.

선택정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

N + (N-1) + (N-2) +... + 2
시간 복잡도는 O(N^2)

삽입 정렬 알고리즘

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
선택 정렬에 비해 구현 난이도가 높지만, 더 효율적으로 동작한다.
일단 구현

arr = [7, 5, 9, 0, 3, 1, 1, 1, 4, 8]
for i in range(1, len(arr)):
  for j in range(i, 0, -1):
    if arr[j] < arr[j-1]:
      arr[j], arr[j-1] = arr[j-1], arr[j]
    else:
      break
print(arr)

O(N^2)의 시간 복잡도를 가진다. 이중for문이 돌아가고 있는것을 볼 수 있다.
현재 리시트가 거의 정렬되어 있는 상태라면 매우 빠르게 정렬을 완성할 수 있다.

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
가장 많이 사용되는 알고리즘 중 하나로 정렬 라이브러리의 근간이 된다.
기본적으로는 첫번째 원소가 pivot이 된다.
두번째 부터 pivot값보다 큰 값을 고르고, 맨 끝에서부터 왼쪽으로 오면서 pivot보다 작은 값을 고른다. 그리고 둘의 자리를 바꾼다. 다시 같은 작업 반복.
그렇게 작업을 반복 수행하다가 왼쪽부터 오던 친구와 오른쪽부터 오던 친구가 서로 엇갈릴 때 작은 값과 pivot의 위치를 바꿔준다.
pivot을 기준으로 왼쪽은 pivot보다 작은 값들이, 오른쪽은 pivot보다 큰 값들이 자리잡게 된다.
그리고 다시 pivot기준으로 왼쪽과, 오른쪽 애들이 퀵 정렬을 수행한다.

이상적으로 분할이 절반씩 일어난다면 O(NlogN)을 기대할 수 있다.
이미 정렬된 경우애는 최악으로 O(N^2)의 시간 복잡도를 가진다.

def quick_sort(arr):
  if len(arr) <= 1: return arr
  pivot = arr[0]
  other = arr[1:]
  left = [i for i in other if i <= pivot]
  right = [i for i in other if i > pivot]
  return quick_sort(left) + [pivot] + quick_sort(right)


arr = quick_sort(arr)

계수 정렬

데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 시킨다.

count = [0] * (max(arr) + 1)
for i in range(len(arr)):
	count[arr[i]] += 1
for i in range(len(count)):
  for j in range(count[i]):
    print(i, end=' ')

시간과 공간 복잡도 모두 O(N+K)
데이터의 범위가 너무 커 버리면 사용하기 힘들다.