[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도

 정렬 별 특징 

선택정렬 (Selection Sort)

 

선택정렬은 앞에서부터 차례대로 정렬하는 방법입니다. 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬방법입니다. 코드가 직관적이기에 구현도 비교적 간단합니다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점인 정렬 방식입니다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있는 정렬 방식입니다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬입니다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여줍니다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준다는 단점도 있습니다.

[C언어] 선택정렬 (배열에 있는 정수값 내림차순 정렬하기)

 

 

버블정렬 (Bubble Sort)

버블정렬은 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식을 말합니다. 마찬가지로 코드가 간단하므로 구현이 간편합니다. 정렬을 하는 방식이 물속에서 물위로 올라오는 물방울 모양과 같다하여 버블정렬이라고 합니다. n개의 원소에 대하여 n개의 메모리를 사용합니다. 데이터를 하나씩 비교할 수 있어서 정밀하게 비교가 가능하나 비교횟수가 많아지므로 성능면에서는 좋은 방법이 아닙니다. 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소를 마지막 자리로 정렬하는 식으로 정렬이 됩니다. 

[C언어] 버블정렬 (배열에 있는 정수값 오름차순 정렬하기)

 

 

삽입정렬 (Insertion Sort)

버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해서 고안된 방법이 삽입정렬입니다. 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방법입니다. 버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 삽입정렬은 기본적으로 버블정렬의 비교횟수를 줄이고 크기가 적은 데이터 집합을 정렬하는 루팅을 작성할 시 버블정렬보다 탁월한 성능 효율을 보여줍니다. 정렬된 값은 한번도 교환이 일어나지 않고 N-1의 비교만 일어납니다.

[C언어] 삽입정렬 (배열에 있는 알파벳 차례대로 정렬하기)

 

 

합병 정렬 (Merge Sort)

작은 단위로 잘게 쪼개어 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합해가면서 정렬하는 방식입니다. 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법이며 안정성이 있여 상당히 좋은 성능을 나타냅니다. 하나 큰 결점이 있다면 공간이 많이 필요하다는 점입니다. 정렬을 하기 위해서는 데이터 전체 크기만한 메모리가 더 필요합니다.

[C언어] 병합정렬 O(N*LogN)

 

 

퀵 정렬 (Quick Sort)

연속적인 분할에 의한 정렬방식입니다. 처음 하나의 축(Pivot)을 먼저 정하여 이 축의 값보다 작은 값은 왼쪽에 큰 값은 오른쪽으로 위치시킨뒤 왼쪽과 오른쪽의 수 들은 다시 각각의 축으로 나누어져 축값이 1이 될 때까지 정렬합니다. 가장 많이 사용되는 정렬법이나 안정성이 떨어진다는 단점이 있습니다. 

[C언어] 퀵정렬 (빠르고 효율적인 정렬방법)

 

 

힙정렬 (Heap Sort)

힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법입니다. 이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘입니다. 처음에는 나무 아래에서 위로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꿉니다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려갑니다. 시간복잡도가 O(nlogn)인 정렬 알고리즘 중에서는 부가적인 메모리가 전혀 필요없다는 게 큰 장점인 정렬 방식입니다.

 

 

쉘 정렬 (Shell Sort)

삽입정렬의 개념을 확대하여 일반화한 정렬방법입니다. 알고리즘이 간단하여 프로그램으로 쉽게 구현할 수 있습니다. 수행 능력도 삽입 정렬보다 우수한 것으로 평가합니다. 멀리 있는 레코드들끼리 비교 및 교환될 수 있으므로, 어떤 데이터가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블정렬 방식의 단점을 해결할 수 있습니다.

 

 

기수 정렬(Radix Sort)

데이터의 비교를 통한 정렬이 아닌 분산 정렬을 이용한 정렬 방법이며 자릿수가 있는 데이터(정수, 문자열 등)에만 사용 가능합니다. 각 자리수를 기준으로 점차 정렬을 진행합니다.

 

 

정렬 별 장단점 비교

 

 

정렬 별 시간복잡도, 공간복잡도 비교

정렬 종류	시간 복잡도			공간 복잡도
	평균(Average)	최선(Best)	최악(Worst)
선택 정렬	O(n2)	O(n2)	O(n2)	O(n2)
버블 정렬	O(n2)	O(n)	O(n2)	O(n)
삽입 정렬	O(n2)	O(n)	O(n2)	O(n2)
합병 정렬	O(n×log n)	O(n×log n)	O(n×log n)	O(n×log n)
퀵 정렬	O(n×log n)	O(n×log n)	O(n2)	O(n×log n)
힙 정렬	O(n×log n)	O(n×log n)	O(n×log n)	O(n×log n)
쉘 정렬	O(N^1.25)	O(N^1.25)	O(N^1.25)	O(n)
기수 정렬	O(dn)	O(dn)	O(dn)

[Algorithm] 알고리즘 공간복잡도에 대하여

[Algorithm] 알고리즘 시간복잡도에 대하여

 

 

정렬 별 속도 비교

[C언어] 여러가지 정렬 속도 비교(정렬의 시간복잡도)