정렬 알고리즘

김가영·2021년 6월 11일

computer-science

목록 보기

9/11

버블정렬

서로 인접한 두 원소를 검사하여 정렬한다.

for i = 0 to (arr의 크기-1) do
  for j = 0 to (arr의 크기-2-i) do
    if arr[j]가 arr[j+1]보다 크면
    then arr[j+1]과 arr[j] 교환
    endif
  endfor
endfor

시간복잡도는 O(N^2)

선택정렬

해당 순서에 어떤 원소를 넣을 지 선택하는 알고리즘

for i = 0 to (arr의 크기-1) do
  min_index = i
  for j = i to (arr의 크기-1) do
    가장 작은 원소 찾아서 min_index에 넣어주기
    endfor
  arr[i]와 arr[min_index]값 교환
endfor

순서대로 n, n-1, n-2...1개씩 비교, 시간복잡도는 O(N^2)

삽입정렬

새로운 카드를 정렬된 카드 사이에서 올바른 자리에 삽입한다
두번째 원소부터 시작, 앞의 원소들과 비교하여 자리를 바꿔나간다

for i = 1 to (arr의 크기-1) do
  index = i-1
  while index가 0보다 크거나 같고 arr[index] > arr[index+1]
    arr[index]와 arr[index+1] 교환
    index-=1
  endwhile
endfor

최악의 경우(역으로 정렬돼있는 경우) 선택정렬과 마찬가지로 O(N^2)
모두 정렬이 돼있는 경우, 한번씩만 비교하므로 O(N)

병합정렬

요소를 반으로 쪼갠후, 다시 합병시키면서 정렬해나가는 과정을 반복

function mergeSort(a: 배열):
  if a의 사이즈가 1보다 작거나 같으면
    return a
  endif
  
  mid = len(a)를 2로 나눈 몫
  left = mergeSort(a[:mid])
  right = mergeSort(a[mid:])
  return merge(left, right)

function merge(left: 배열, right: 배열):
  i = 0, j = 0
  res = []
  while i가 len(left)보다 작고, j가 len(right)보다 작을때
    if left[i] <= right[j]
    then left[i]를 res에 push하고 i 1 증가
    else left[j]를 res에 push하고 j 1 증가
    endif
  endwhile
  
  while i가 len(left)보다 작음
    left[i]를 res에 push하고 i에 1 증가
  while j가 len(right)보다 작음
    left[j]를 res에 push하고 j에 1 증가
  return res

순차적인 비교를 하므로 linked list에 이용하면 효과적
시간복잡도는 평균, 최악, 최선 모두 O(N logN)

퀵 정렬

pivot을 기준으로 pivot보다 작은 수와 큰 수의 집합으로 나눈다.
집합 내에서 다시 pivot을 선택하여 집합으로 나누는 과정을 반복한다.
reference

function quickSort(arr: 배열, start: 시작 인덱스, end: 끝 인덱스):
  pivot = start
  left = pivot+1
  right = end
  while left <= right:
      while left < end and arr[left] <= arr[pivot]:
          left += 1
      endwhile
      while right > start and arr[right] >= arr[pivot]:
          right -= 1
      endwhile
      if left <= right:
      then arr[left],arr[right] = arr[right], arr[left]
  endwhile
  arr[right], arr[pivot] = arr[pivot], arr[right]
  quickSort(arr, start, right-1)
  quickSort(arr, right+1, end)