[Algorithm]향상된 정렬2

📚힙 정렬

📄힙

힙은 임의의 값과 최댓값 삭제가 쉽다는 장점이 있다.

최대 힙은 완전 이진 트리로서 각 노드의 값은 자신의 자식 노드 값보다 크거나 같다는 조건을 만족한다.(오름차순 정렬에 사용)

최소 힙은 각 노드의 값은 자신의 자식 노드 값보다 작거나 같다는 조건을 만족한다.(내림차순 정렬에 사용)

힙은 일차원 배열로 구현 가능한데 배열을 사용하면 인덱스 값 계산을 통해 부모 노드와 자식 노드를 쉽게 구할 수 있다는 장점이 있다.

부모 노드가 1이라면 (2 * 부모노드 + 1), (2 * 부모노드 인덱스 + 2)로 자식 노드를 쉽게 구할 수 있다.

📄알고리듬

HeapSort(A[], n)
{
	// 입력 배열을 힙으로 변환
	for(i = 0; i < n; i++)
	{
		parent = (i / 2) - 1;
		while(parent >= 0 && A[parent] < A[i])
		{
			A[parent]와 A[i] 원소 교환;
			i = parent;
			parent = (i-1)/2;
		}
	}

	// 최댓값 삭제와 힙으로 재구성하는 과정. 입력 크기 n만큼 반복
	for(i = n - 1; i > 0; i--)
	{
		최댓값(A[0])과 마지막 노드A[i] 원소 교환 // 최댓값 삭제
		cur = 0;
		lch = 1;
		rch = 2;

		do
		{
			if(rch < i && A[lch] < A[rch])
			{
				lch = rch;
			}

			if(A[lch] > A[rch])
			{
				A[cur]와 A[lch] 원소 교환;
				cur = lch;
				lch = cur * 2 + 1;
				rch = cur * 2 + 2;
			}
			else
			{
				lch = i;
			}
		}while(lch < i)
	}

	return(A);
}

📄성능과 특징

• 최선, 최악, 평균 모두 O(n log n)

• 안정적이지 않은 정렬 알고리듬이다.

• 제자리 정렬 알고리듬이다.

📚선형 시간 정렬 알고리듬

비교 기반의 정렬 알고리듬의 성능의 하한은 O(n log n)이다. 즉 아무리 빨라도 O(n log n)보다 효율적인 알고리듬은 구할 수 없다.

하지만 계수 정렬, 기수 정렬, 버킷 정렬 알고리듬은 이미 얻어진 데이터 분포 정보를 활용하기 때문에 최악 또는 평균 수행시간이 선형 시간 O(n)이 가능하다.

제한된 조건에 맞는 데이터 분포 정보를 사용하기 때문에 보편적인 상황에 사용할 수 없다는 단점도 있다.

📄계수 정렬

• 개념과 원리

주어진 데이터 중에서 자신보다 작거나 같은 값을 갖는 데이터 개수를 계산하여 정렬한 위치를 찾아 정렬하는 방식이다.

이 정렬은 입력 값이 어떤 작은 정수 범위 내에 있다는 것을 알고 있는 경우에 적용 가능하다.

• 알고리듬

CountingSort(A[], n)
{
	MIN = MAX = A[1];

	for(i = 1; i <= n; i++)
	{
		if(A[i] < MIN)
		{
			MIN = A[i];
		}

		if(A[i] > MAX)
		{
			MAX = A[i];
		}
	}

	for(j = MIN; j <= MAX; j++)
	{
		COUNT[j] = 0;
	}

	for(i = 1; i <= n; i++)
	{
		COUNT[A[i]]++;
	}

	for(j = MIN + 1; j <= MAX; j++)
	{
		COUNT[j] = COUNT[j] + COUNT[j-1];
	}

	for(i = n; i > 0; i--)
	{
		B[COUNT[A[i]]] = A[i];
		COUNT[A[i]]--;
	}

	return(B);
}

• 성능과 특징
  • 시간 복잡도는 O(n).
  • 입력값의 범위가 입력 데이터의 개수보다 작거나 비례할 때 유용하다.
  • 안정적인 정렬 알고리듬이다.
  • 제자리 정렬 알고리듬이 아니다.
  • 보편적이지 못한 방법이다.

📄기수 정렬

• 개념과 원리

입력값을 자릿수별로 구분해서 부분적으로 비교하여 정렬하는 방식이다. 주어진 데이터의 값을 자릿수별로 나누고, 각 자릿수에 대해 계수 정렬과 같은 안정적인 정렬 알고리듬을 적용하여 정렬하는 방식이다.

LSD 기수 정렬 -> 낮은 자리부터 높은 자리로 진행

MSD 기수 정렬 -> 높은 자리부터 낮은 자리로 진행

• 알고리듬

RadixSort(A[], n)
{
	for(i = 1; i <= d; i++)
	{
		각 데이터 i자리의 값에 대해 안정적인 정렬 알고리듬 적용; // 계수 정렬
	}
}

• 성능과 특징
  • 시간 복잡도 O(n).
  • 입력 데이터의 자릿수가 상수일 때 유용하다.
  • 안정적인 정렬 알고리듬이다.
  • 제자리 정렬 알고리듬이 아니다.

📄버킷 정렬

• 개념과 원리

주어진 데이터들의 값의 범위를 균등하게 나누어 여러 개의 버킷을 만든뒤, 각 데이터를 해당하는 버킷에 넣고, 각 버킷을 삽입 정렬과 같은 안정적인 정렬을 수행한 후, 버킷 순서대로 각 데이터를 나열하는 정렬 방식이다.

• 알고리듬

BucketSort(A[], n)
{
	MIN = MAX = A[0];

	for(i = 1; i < n; i++)
	{
		if(A[i] < MIN)
		{
			MIN = A[i];
		}
		if(A[i] > MAX)
		{
			MAX = A[i];
		}
	}

	INTERVAL = (MAX - MIN + 1) / n;

	for(i = 0; i < n; i++)
	{
		BUCKET[A[i] - MIN / INTERVAL] = A[i];
	}

	for(i = 0; i < n; i++)
	{
		삽입 정렬에 의해 BUCKET[i] 정렬;
	}

	BUCKET[0], BUCKET[1], ... 순서대로 데이터를 배열 B[]에 삽입;

	return(B);
}

• 성능과 특징
  • 시간 복잡도는 O(n)
  • 입력 데이터의 값이 확률적으로 균등하게 분포할 때 유용하다.
  • 버킷 개수가 입력 데이터의 개수에 비례해야 유용하다.
  • 안정적인 정렬 알고리듬이다.
  • 제자리 정렬 알고리듬이 아니다.