정렬 알고리즘

정렬

자료들을 오름차순이나 내림차순으로 재배열하는 것이다. 정렬에 기준이 되는 특정 값을 키key라고 한다.

정렬 시에는 안정 정렬 stable sort를 이용해야 하는 경우가 있다. 두 개의 열이 정렬됐을 때 원래 순서가 보장되는 경우, 안정정렬이 된 것이고, 원래 순서가 유지되지 않는 경우 안정정렬이 되지 않은 것이다.

안정정렬 유지 예

다양한 정렬 알고리즘 중에서 하나를 선택할 때는 고려해야 할 사항들이 많다.

1. 시간 복잡도는 얼마인가?
2. 구현이 간단한가?
3. 자료량이 많거나 적을 때 적절한가?
4. 안정정렬인가? - 이 조건으로 선택가능한 알고리즘이 줄어든다.
5. 추가 메모리양은 얼마인가?
6. 이미 정렬된 경우 더 신속하게 정렬가능한가?

또, 정렬에는 내부정렬 internal sort과 외부정렬 external sort이 있는데 여기서는 내부정렬만 다루겠다.

내부정렬

정렬할 자료를 메모리에 올려서 정렬하는 방식이다. 메인메모리에서 하는 만큼 빠르지만 자료량이 메인메모리 용량에 따라 제한된다. 비교횟수와 자료이동 횟수, 추가 기억공간 필요량에 따라 효율성을 가를 수 있다.

 

내부정렬 종류

• 기본 정렬 : 시간복잡도는 O(n2)이나 가장 단순한 알고리즘.
  • Selection sort 선택 정렬 
  • Bubble sort 버블 정렬
  • Insertion sort 삽입 정렬
• 고급 정렬 :평균 시간 복잡도가 O(n log n)인 정렬.
  • Quick sort 퀵 정렬
  • Merge sort 병합 정렬
  • Heap sort 힙 정렬
• 특수 정렬 : 조건에 따라 복잡도가 O(n)일 수 있는 정렬
  
  • Bucket sort 버킷 정렬
  • tree sort 트리 정렬

---

선택 정렬

전체 원소에서 기준 위치를 선택해서 위치에 있는 값과 비교하는 방식으로 정렬하는 것이다.

추가 기억장소 필요량 :  O(1)

시간복잡도 : O(n2)

버블 정렬

인접한 두 개의 원소를 비교하고, 기준에 맞지 않으면 자리를 교환하는 방식이다.

추가 기억장소 필요량 : O(1)

자료가 이미 정렬되어 있는 최선의 경우엔 원소 자리교환은 발생하지 않기 때문에  O(n)도 가능.

허나 평균 시간복잡도는 O(n2)

 

삽입 정렬

이미 정렬된 앞 부분 원소들을 S, 정렬되지 않은 뒷부분 원소를 U라고 하자. 삽입정렬 insertion은 이 U의 원소를 하나씩 꺼내서 S의 마지막 원소와 비교하여 위치를 찾아 삽입하는 것이다. U가 공집합이 되면 정렬은 완성한다.

추가 기억장소 필요량 : O(1)

이미 정렬되어 있는 최선의 경우, 바로 앞자리 원소와 한 번만 비교하므로 전체 비교횟수는 줄어들며 시간 복잡도는 O(n)이 된다.

역순으로 정렬된 최악의 경우, O(n2)이다.

	--aa bb ab ac cc 라는 문자열을 입력하고 배열을 만들어 삽입정렬을 한다고 해보자.
    --삽입정렬의 코드는 다음과 같다.
    private static void insertionSort(String[] array) {
		int i, j;
		String it;
		for(i=0; i<array.length;i++) {
			it=array[i];
			//.compareTo매소드로 어느 것이 사전적으로 먼저인가를 알 수 있다.
			for(j=i;(j>0)&&0<(array[j-1].compareTo(it));j--) {
				array[j]=array[j-1];
			}
			array[j]=it;
		}
		
	}

셸 정렬 Shell sort

정렬된 최선의 경우의 삽입정렬은 빠르다. 이 특성에 기인한 정렬 방식이다. 일정간격으로 떨어져있는 원소를 부분집합으로 하여 삽입정렬을 수행하고, 이를 반복하며 전체집합으로 정렬하는 것이다.

부분집합을 만드는 간격을 매개변수 h에 저장하고 단계를 수행할 때마다 h의 값을 감소시킨다. h가 1이 될 때까지 반복한다.

추가 기억장소 필요량 : O(1)

시간 복잡도 : O(n^1.25)

---

퀵 정렬

기준값을 중심으로 왼쪽과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다. 기준값보다 작으면 왼쪽, 크면 오른쪽으로 이동시킨다. 기준값을 피봇 pivot이라 하는데 중앙값에 가까울수록 퀵정렬의 성능이 향상된다.

퀵정렬은 기준값을 중심으로 부분집랍으로 나누는 분할 divide과 부분집합의 크기가 1이하가 될 때까지 분할하여 정렬하는 정족 conquer로 나뉜다.

추가 기억장소 필요량 : O(log n) 재귀호출에 따른 추가장소량

분할할 때마다 원소들이 이등분되고 수행단계 수가 최소가 되면 O(n log2N),

분할마다 원소들이 한쪽으로 치우쳐 분할되면 O(n2)

허나 평균적으로 O(n  log2N)이다.

병합정렬

자료들을 부분집합으로 분할하고, 정렬하면서 결합하는 방법이다. n-way 병합과 2-way 병합이 있는데 여기서는 2-way만 다루겠다. 2-way 병합 정렬은 1.분할, 2.정복, 3.결합 이 세 가지 작업을 반복 수행하면서 완성한다.

 

추가 기억장소 필요량 : O(n) 각 단계에서 병합한 결과를 일시적으로 저장할 공간이 필요하다.

분할은 log2N번의 단계 수행이 필요하고, 병합은 단계마다 n번의 비교연산을 수행해야 한다.

따라서 시간복잡도는 O(n log n)

힙 정렬

힙 이진트리를 이용한 정렬방법이다. 최대힙이나 최소힙에서 최대/최소 원소가 루트노드이므로 이를 삭제하면서 리턴한다.

 

추가 기억장소 필요량 : O(1)

n개의 노드의 힙의 높이는 O(log2n) 따라서 힙 구성 시간은  O(n log2n), n개의 노드를 삭제하며 힙을 재구성하는 시간도 똑같다.

그러므로 시간 복잡도는 O(n log2n)

버킷 정렬

원소를 비교하지 않고, 원소 키값에 대해 해당하는 버킷을 분배했다고 버킷 순서대로 원소를 꺼내는 작업을 반복하며 정렬하는 방식이다. 기수만큼의 버킷을 사용할 필요가 있다. 버킷은 큐로 구현한다.

 

추가 기억장소 필요량은 기수에 따른 버킷 공간이다.

시간복잡도는 원소의 수 n, 키 값의 자루시 d, 버킷 수를 정하는 기수 r에 따라 달라진다. 원소를 버킷에 분배하고 다시 꺼내는 작업 O(n+r)을 키 값의 자릿수d만큼 반복한다.

따라서 O(d(n+r))

 

트리 정렬

이진 탐색 트리 binary search tree를 이용하여 정렬하는 방법이다.

 

추가 기억장소 필요량 : O(n) 이진탐색트리의 저장공간이 필요하다.

노드 하나를 삽입하는 데에 걸리는 시간이 O(log2n), n개를 삽입한다고 하면 O(n log2 n). 참고로 중위 순회는 O(n).

따라서 시간 복잡도는 O(n log2 n)