[자료구조] 기본 정렬 알고리즘(Sorting Algorithm)

버블 정렬(Bubble Sort) 

버블 정렬이란 인접한 두개의 데이터를 비교해서 정렬을 진행하는 정렬방식이다. 방식이 간단한만큼 비효율적이다.

ex) 배열에 숫자들을 오름차순으로 정렬할 때 첫번째 수를 시작으로 끝의 숫자까지 바로 인접해 있는 숫자와 비교하며 이동한다. 

 

선택정렬(Selection Sort)

선택정렬이란 제자리 정렬 알고리즘 중 하나이며, 오름차순으로 정렬한다면 가장 작은 최솟값을 맨앞에 놓고 그 이후의 값들을 하나씩 비교한 후 올바른 값을 선택하여 채워넣는 정렬방법이다. (버블정렬과 비슷한 성능)

 

삽입정렬(Insertion Sort)

삽입정렬은 정렬대상을 정렬된 부분과 안된 부분 두 부분으로 나눈 후 정렬안된부분의 데이터를 정렬된 부분의 특정 위치에 삽입하는 정렬방법이다. 

 

병합정렬(Merge Sort)

병합정렬은 분할정복 알고리즘 디자인기법에 근거하여 만들어졌으며, 데이터를 통째로 정렬하는 것보다 나눠서 정렬하는 것이 더 쉽다는 전제하에 데이터의 영역을 나눠서 정렬하는 방법이다. 

병합정렬은 데이터가 1개 남을 때까지 분할한다.(정렬x 분할만o), 그 후 다시 병합을 진행하며 정렬을 한다. 

분할 정복 3단계: 분할(문제를 분할) -> 정복(분할된 문제를 해결) -> 결합(해결한 결과를 결합)\

 

기수정렬(Radix Sort)

기수 정렬은 기존의 정렬들과는 다르게 정렬순서상에 우선순위를 판단하기 위한 비교연산을 하지 않으며, 기수를 이용해서 정렬을 진행한다. 기수정렬은 길이가 같은 데이터들을 대상으로만 정렬이 가능하다. 길이가 다르더라도 가능은하지만 상당히 제한적이다. 

일반적으로 기수정렬은  LSD 방식을 기준으로 한다. 

LSD(Least Significant Digit) : 덜 중요한 자릿수부터 정렬을 시작