파이썬 - 정렬 알고리즘 정리

개요

정렬 알고리즘을 간단하게 정리한다.

O(n²)

• 버블 정렬 : 앞에서부터 인접한 두 수를 비교해가면서 큰 수를 뒤로 보내며 정렬하는 방식

• 선택 정렬 : 앞에서부터 가장 작은 수와 위치를 바꿔가며 정렬하는 방식

• 삽입 정렬 : 정렬 범위를 1칸씩 늘려가면서 새로운 정렬 대상을 기존 값과 비교하여 맞는 위치에 넣으며 정렬하는 방식

O(n logn)

• 병합 정렬 : 재귀 + 분할정복을 이용한 정렬 알고리즘이다.
  배열을 원소가 1개 남을때까지 둘로 나누고 다시 크기순으로 재배열하면서 합쳐서 정렬하는 방식이다.

• 퀵 정렬 : 병합정렬과 마찬가지로 재귀 + 분할정복을 이용한 알고리즘이다.
  피벗을 기준으로 피벗보다 큰 그룹, 작은 그룹으로 나눈다. 나누었으면 각 그룹에서도 다시 피벗을 정하여 같은 과정을 반복해서 정렬하는 방식이다.