아래는 몇가지 정렬(Sorting)에 대해서 간단하게 정리한 것입니다.
1. 버블 정렬
맨 처음 값을 다음 값과 비교해서 크면 자리를 바꾼다. 그리고 바뀐 2번째 값과 3번째 값을 비교해서 2번째 값이 크면 바꾼다. 이렇게 해서 끝까지 간다.
그런 다음 2번째 짜리 부터 위 짓을 똑같이 반복한다. 이렇게 n-1 까지 하면 된다.
//소스
for (i=n-1; i>0; i--) {
for (j=0; j<i; j++){
if(list[j] > list[j+1])
SWAP(list[j], list[j+1], temp);
}
}
버블 소트는 가장 단순하지만 가장 성능이 나쁘다
2. 셀렉션 정렬
처음 자리부터 마지막까지 가장 낮은 값을 찾는다. 그리고 그 값을 처음 자리랑 바꾼다.
다시 2번째 자리부터 가장 낮은 값을 찾아 2번째자리와 바꾼다.
루프 상으로 봤을 때 성능이 버블 소트와 N제곱으로 같지만 값을 치환하는 과정에서 조금 낫다.
3. 퀵 정렬
퀵 소트는 기준 값을 정해 그 값보다 큰쪽, 작은쪽으로 나눈다. 그리고 다시 작은 쪽에서 기준값보다 큰쪽 작은 쪽으로 나누며 정렬한다. 위에서 정렬하지 않은 큰쪽도 물론 한다.
이럴 경우 처음 정렬에서는 모든 대상이 비교가 되지만 2번째부터는 비교대상이 반으로 줄어든다. 그리고 다음 비교에서는 대상이 4분의 1로 줄어든다. 그렇기에 위의 버블소트나 셀렉션 소트보다 성능이 좋다.
4. 쉘
정렬
일정한 간격의 두 값을 비교하여 자리를 바꾼다. 뒤의 값들도 같은 간격으로 비교를 한다. 그런 다음 간격의 크기를 변화 시키고 다시 간격간의 값을 바꿔나가는 방식이다. 이럴 경우 복잡도가 상당히 증하가지만 실제로 나중에 가서는 값 치환이 작게 일어나고 여유 메모리가 필요없어 성능이 좋다고 한다. 그리고 쉘 정렬의 가장 좋은 성능은 처음 간격을 1로 두고 h=3*h+1으로 증가시키는 값이다.
5. 머지 정렬(합병 정렬)
배열을 반으로 계속 쪼갠 다음 가장 작은 단위에서부터 비교에서 정렬한 다음 그 다음 단위로 이동하여 다시 비교하며 정렬하는 방식이다
예를 들면, 3 8 0 7 6 4 5 9 이 있으면 3, 8을 정렬 합병하고 0,7을 정렬 합병한다. 그 뒤도 2개씩 정렬 합병한다. 그런 다음 정렬된 3,8 ,0,7을 정렬 합병한다. 이 경우 0, 3, 7, 8 이 되고 두의 부분도 이와 같이 정렬하면 4, 5, 6, 9가 된다. 위의 두 부분을을 다시 정렬해서 03456789가 되는 것이다.
기타. Heap Sort(힙
정렬), Insert Sort(삽입 정렬) 등이 있다