알고리즘 - 정렬 알고리즘

자세히 공부하기 전 특성 정리

 

정렬 알고리즘

① 비교 기반 정렬 알고리즘

종류	특징	평균 시간 복잡도
버블 정렬	인접한 두 수를 비교해 정렬	O(n2)
선택 정렬	정렬되지 않은 배열에서 최솟값을 선택해 정렬
삽입 정렬	정렬된 배열에서 탐색 중인 요소 삽입
합병 정렬	* 분할 정복 기분 알고리즘 * 배열을 1 이하 크기로 분할 후 합병 과정에서 정렬	O(n log n)
퀵 정렬	* 분할 정복 기반 알고리즘 * 피봇을 선택해 피봇을 기준으로  작은 수의 배열과 피봇보다 큰 수의 배열로 분할하여 정렬 * 피봇에 따라 시간 복잡도가 달라질 수 있음
힙 정렬	* 힙 기반 정렬 알고리즘 * 최대 힙을 이용해 오름차순 정렬, 최소 힙을 이용해 내림차순 정렬

* 피봇 : 배열에서 선택한 하나의 데이터 원소

 

 

 

② 비교 기반이 아닌 정렬 알고리즘

종류	특징
기수 정렬	* 낮은 자릿수부터 높은 자릿수까지 정렬 * 자릿수에 올 수 있는 숫자별로 각각 큐를 생성해 각 자릿수에 해당하는 큐에 숫자를 넣으며 정렬 * 시간 복잡도 면에서 효율적이지만 메모리 소비가 큼
계수 정렬	데이터 범위를 인덱스로 갖는 배열을 생성해 각 인덱스에 해당하는 데이터 개수를 세서 정렬 수행