정렬 알고리즘

한별·2023년 8월 21일

계수 정렬 삽입 정렬 선택 정렬 정렬 코딩테스트 퀵 정렬

코딩테스트

목록 보기

7/12

정렬 알고리즘❓

정렬: 데이터를 특정한 기준에 따라 순서대로 나열하는 것
문제 상황에 따라 적절한 정렬 알고리즘을 사용해야 함

거품 정렬

: 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환

시간 복잡도

O(N2)

선택 정렬

: 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꿈

시간 복잡도

O(N2)

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

# 처리되지 않은 데이터 중 맨 앞 데이터의 index
for i in range(len(arr)):
  # 처리되지 않은 데이터 중 가장 작은 데이터의 index
  min_index = i
  for j in range(i, len(arr)):
    if arr[j] < arr[min_index]:
      min_index = j
  # swap
  arr[i], arr[min_index] = arr[min_index], arr[i]
print(arr)

삽입 정렬

: 처리되지 않은 데이터를 하나씩 골라 적절한 위치(앞쪽의 데이터들은 정렬되어 있다고 가정하고)에 삽입

시간 복잡도

O(N2)

특징

현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작 = O(N)

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] < arr[j - 1]:  # 한 칸씩 왼쪽으로 이동
      arr[j], arr[j - 1] = arr[j - 1], arr[j]
    else:
      break

print(arr)

퀵 정렬

: 기준 데이터를 설정하고 그 기준 보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

시간 복잡도

O(NlogN)

특징

일반적인 상황에서 가장 많이 사용 → 병합 정렬과 더불어 대부분의 언어에서 표준 정렬 라이브러리의 근간 (C, Java, Python)
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정
최악의 경우(편향된 분할) = O(N2)

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

def quick_sort(arr, start, end):
  if start >= end: return # 원소가 1개인 경우 종료
  pivot = start # 피봇은 첫번째 원소
  left = start + 1
  right = end
  while left <= right:
    while left <= end and arr[pivot] >= arr[left]:
      left += 1
    while start < right and arr[pivot] <= arr[right]:
      right -= 1
    if left > right:
      arr[right], arr[pivot] = arr[pivot], arr[right]
    else:
      arr[left], arr[right] = arr[right], arr[left]
  # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
  quick_sort(arr, start, right-1)
  quick_sort(arr, right+1, end)

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

계수 정렬

i번 인덱스에 i 값의 개수를 저장

예제

5 3 6 1 2 7 9 5 1 1

0	1	2	3	4	5	6	7	8	9
0	3	1	1	0	2	1	1	0	1

정렬 결과 ) 1 1 1 2 3 5 5 6 7 9

시간 복잡도

데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N+K) 보장

특징

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
배열(인덱스)에 값을 저장

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

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

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

정렬 알고리즘 비교하기

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N2)	O(N)	아이디어가 매우 간단
삽입 정렬	O(N2)	O(N)	데이터가 거의 정렬되어 있을 때는 가장 빠름
퀵 정렬	O(NlogN) / 최악의 경우 O(N2)	O(N)	대부분의 경우에 가장 적합, 충분히 빠름
계수 정렬	O(N+K)	O(N+K)	데이터의 크기가 한정되어 있는 경우에만 사용 가능, 매우 빠름