- 선택된 값과 나머지 데이터중에 비교하여 알맞은 자리를 찾는 알고리즘
- 최선, 평균, 최악 모두
O(N^2)
- 데이터 집합을 순회하면서 정렬이 필요한 요소롤 뽑아내어 이를 다시 적당한곳으로 삽입하는 알고리즘
- 성능은 버블정렬보다 좋다
- 최악, 평균 :
O(N^2)
- 최선 :
O(N)
- 이미 정렬되어 있는 경우
- 거품이 수면으로 올라오는 듯 하여 붙여진 버블정렬
- 인접한 두 수를 비교하여 오름차순 or 내림차순으로 정렬
- 최선, 평균, 최악 모두
O(N^2)
- 데이터 집합내에 임의의 기준값(=pivot)을 정하고 해당 피봇으로 집합을 기준으로 두개의 부분 집합으로 나눈다.
- 한쪽 부분에는 피봇값보다 작은 값들만, 다른 한쪽은 큰값들만 넣는다.
- 더 이상 쪼갤 부분 집합이 없을 때까지 각각의 부분 집합에 대해 피봇/쪼개기 재귀적으로 적용.
- 분할 정복법 사용(Divide-And-Conquer)
- 범위, 기준, 비교, 스왑으로 순서
- 최악 :
O(N^2)
- 평균, 최선 :
O(NlogN)