🛩️ 정렬

🛩️ 선택 정렬

• 가장 작은 데이터를 선택하여 맨 앞의 데이터랑 바꾸는 정렬
• 선택정렬의 시간 복잡도 : O(N$^2$)

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[j] < array[min_index]:
      min_index = j
  array[i], array[min_index] = array[min_index], array[i]

print(array)

🛩️ 삽입 정렬

• 특정한 데이터를 적절한 위치에 삽입하는 정렬
• 삽입정렬의 시간 복잡도 : O(N$^2$)

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

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

🛩️ 퀵 정렬

• 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는것
• 퀵정렬의 시간 복잡도 : O(*Nlog(N)*)

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)

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
  if len(array) <= 1:
    return array
  
  pivot = array[0]
  tail = array[1:]

  left = [x for x in tail if x <= pivot]
  right = [x for x in tail if x > pivot]

  return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort(array))

🛩️ 계수 정렬

• 데이터의 크기 범위가 정수 형태일때 사용하는 매우 빠른 정렬
• 계수정렬의 시간 복잡도 : O(*N+K*)

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0]*(max(array)+1)

for i in array:
  count[i] += 1

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

🛩️ 문제 유형에 따른 풀이법

1. 정렬 라이브러리 사용 : 단순 정렬 기법확인 문제
2. 정렬 알고리즘 원리 : 선택 정렬, 삽입 정렬, 퀵 정렬등의 알고리즘 이용
3. 더 빠른 정렬 : 계수 정렬이나 문제에서 주어진 알고리즘 확인## ✈ 선택 정렬