쌓 기 정렬 - C \ # 실현
더미 정렬 (Heap Sort) 은 두 갈래 로 불 리 는 데이터 구 조 를 이용 하여 정렬 하 는 정렬 알고리즘 이다.
이 진 지 는 내부 에 쌓 여 하나의 배열 을 유지 하고 비슷 한 완전 이 진 트 리 로 볼 수 있 으 며 나무의 모든 노드 는 배열 의 요소 에 대응 합 니 다.밑바닥 을 제외 하고 이 나 무 는 꽉 찼 다.
이 진 더미 에는 유지 보수 그룹 과 관련 된 두 개의 속성 이 있 습 니 다.Length 는 배열 의 요소 개 수 를 나타 내 고 HeapSize 는 이 진 더미 에서 유지 하 는 배열 의 요소 개 수 를 나타 낸다 (배열 의 모든 요소 가 이 진 더미 의 유효 요소 가 아 닌 것).따라서 상기 정의 에 따 르 면 0 < = Heap Size < = Length.
이 진 더 미 는 가장 큰 더미 와 가장 작은 더미 두 가지 유형 으로 나 눌 수 있다.가장 많은 더미 에서 이 진 트 리 의 모든 노드 는 아버지 노드 보다 크 지 않 습 니 다. 즉, A [Parent (i)] > = A [i] 입 니 다.최소 더 미 는 정반 대 입 니 다. A [Parent (i)] < = A [i].
두 갈래 더 미 를 유지 하기 위해 최대 (작은) 더 미 를 사용 합 니 다. MaxHeapify (MinHeapify) 라 는 과정 을 호출 합 니 다.MaxHeapify 로 MaxHeapify 를 호출 할 때 뿌리 노드 를 Left (i) 와 Right (i) 로 가정 한 이 진 트 리 가 모두 최대 더미 입 니 다. 만약 에 A [i] 가 하위 노드 의 요소 보다 작 으 면 A [i] 와 그 하위 노드 의 비교적 큰 요 소 를 교환 합 니 다.그러나 이렇게 되면 교 환 된 하위 노드 를 루트 요소 로 하 는 이 진 더 미 는 최대 더미 의 성질 을 만족 시 키 지 못 할 수도 있 습 니 다. 이 때 는 모든 하위 이 진 더 미 는 최대 더미 의 성질 을 만족 시 킬 때 까지 MaxHeapify 방법 을 재 귀적 으로 호출 합 니 다.다음 그림 에서 보 듯 이:
MaxHeapify (MinHeapify) 방법 을 호출 하여 루트 노드 가 A [i] 인 이 진 더미 가 최대 (작은) 더미 의 성질 을 만족 시 킬 때 우 리 는 좌우 하위 더 미 를 모두 최대 (작은) 더미 의 성질 을 만족 시 켰 다 는 가설 을 가지 기 때문에 정렬 할 배열 을 최대 (작은) 더미 로 구성 할 때 아래 에서 위로 MaxHeapify (MinHeapify) 방법 을 호출 해 야 합 니 다.
최대 더 미 를 이용 하여 정렬 을 할 때 우 리 는 정렬 대기 배열 을 최대 더미 로 구성 합 니 다. 이때 A [0] (뿌리 노드) 는 배열 의 최대 요소 이 고 A [0] 를 A [n - 1] 와 교환 하면 A [0] 를 최종 적 으로 정확 한 정렬 위치 에 두 었 습 니 다.그리고 HeapSize 에서 1 을 빼 고 마지막 요 소 를 더미 에서 제거 합 니 다.그리고 MaxHeapify 방법 을 통 해 남 은 더 미 를 최대 로 바 꾸 고 이상 의 교환 을 반복 합 니 다.쌓 여 있 는 요소 가 두 개 밖 에 없 을 때 까지 이 동작 을 반복 합 니 다.최종 적 으로 얻 은 배열 은 오름차 순 으로 배 열 된 배열 이다.
이 알고리즘 실현
1. C \ # 에서 배열 의 시작 아래 에 0 으로 표시 되 어 있 음 을 알 수 있 으 므 로 아래 표 시 된 노드 의 부모 노드 와 좌우 부분 노드 를 계산 할 때 특히 조심해 야 합 니 다.
private static int Parrent(int i)
{
return (i - 1) / 2;
}
private static int Left(int i)
{
return 2 * i + 1;
}
private static int Right(int i)
{
return 2 * i + 2;
}2. 알고리즘 의 핵심 부분 은 MaxHeapify (MinHeapify) 방법 입 니 다. 알고리즘 설명 에 따 르 면 다음 코드 는 정수 배열 에 대한 최대 집적 화 와 최소 집적 방법, 그리고 일반적인 버 전 을 실현 합 니 다.
private static void MaxHeapify(int[] array, int i, int heapSize)
{
int left = Left(i);
int right = Right(i);
int largest = i;
if (left < heapSize && array[left] > array[i])
{
largest = left;
}
if (right < heapSize && array[right] > array[largest])
{
largest = right;
}
if (largest != i)
{
Exchange(ref array[i], ref array[largest]);
MaxHeapify(array, largest, heapSize);
}
}
private static void MinHeapify(int[] array, int i, int heapSize)
{
int left = Left(i);
int right = Right(i);
int smallest = i;
if (left < heapSize && array[left] < array[i])
{
smallest = left;
}
if (right < heapSize && array[right] < array[smallest])
{
smallest = right;
}
if (smallest != i)
{
Exchange(ref array[i], ref array[smallest]);
MinHeapify(array, smallest, heapSize);
}
}
private static void MHeapify(T[] array, int i, int heapSize, Comparison comparison)
{
int left = Left(i);
int right = Right(i);
int extremumIndex = i;
if (left < heapSize && comparison(array[left], array[i]) > 0)
{
extremumIndex = left;
}
if (right < heapSize && comparison(array[right], array[extremumIndex]) > 0)
{
extremumIndex = right;
}
if (extremumIndex != i)
{
Exchange(ref array[extremumIndex], ref array[i]);
MHeapify(array, extremumIndex, heapSize, comparison);
}
} 3. 구조 가 가장 크다.밑 에서 위로 구 조 를 하 는 것 이 눈 에 띈 다.
private static void BuildMaxHeap(int[] array)
{
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
MaxHeapify(array, i, array.Length);
}
}
private static void BuildMinHeap(int[] array)
{
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
MinHeapify(array, i, array.Length);
}
}
private static void BuildMHeap(T[] array, Comparison comparison)
{
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
MHeapify(array, i, array.Length, comparison);
}
} 4 더미 정렬 알고리즘.다음은 정수 배열 의 오름차 순 정렬, 내림차 순 정렬 과 일반 버 전 이다.오름차 순 정렬 구 조 는 최대 더미 이 고 내림차 순 정렬 은 구조의 최소 더미 입 니 다.
public static void HeapSort(int[] array)
{
BuildMaxHeap(array);
for (int i = array.Length - 1; i > 0; i--)
{
Exchange(ref array[i], ref array[0]);
MaxHeapify(array, 0, i);
}
}
public static void HeapDesSort(int[] array)
{
BuildMinHeap(array);
for (int i = array.Length - 1; i > 0; i--)
{
Exchange(ref array[i], ref array[0]);
MinHeapify(array, 0, i);
}
}
public static void HeapSort(T[] array, Comparison comparison)
{
BuildMHeap(array, comparison);
for (int i = array.Length - 1; i > 0; i--)
{
Exchange(ref array[i], ref array[0]);
MHeapify(array, 0, i, comparison);
}
} 세 가지 다른 코드 의 조직 방식
상술 한 코드 는 일반적인 더미 정렬 의 실현 방식 이다.그러나 C \ # 로 쌓 기 정렬 을 실현 하 는 이상 가능 한 한 대상 을 대상 으로 하 는 방식 을 고려 하여 알고리즘 을 실현 해 야 한다.상기 코드 를 감안 하면 노드 의 하위 노드, 부모 노드, 유지 최대 (작은) 더미, 최대 (작은) 더미 구축 등 방법 을 구 하 는 것 자체 가 이러한 데이터 구조 자체 에 대한 작업 에 속한다.따라서 이 를 하나의 데이터 구조 류 로 봉 하여 클래스 에서 관련 정렬 작업 을 하 는 것 을 고려 할 수 있다.다음 과 같다.
public class Heap
{
#region Fields
private int _heapSize = 0;
private T[] _array = null;
#endregion
#region Properties
public int HeapSize
{
get { return _heapSize; }
set { _heapSize = value; }
}
#endregion
#region Constructors
public Heap(T[] array, int heapSize)
{
_array = array;
if(heapSize > array.Length)
{
Exception ex = new Exception("The heap size is larger than the array length");
throw (ex);
}
_heapSize = heapSize;
}
public Heap(T[] array)
{
_array = array;
_heapSize = array.Length;
}
#endregion
#region Methods
private int Parrent(int index)
{
return (index - 1) / 2;
}
private int Left(int index)
{
return 2 * index + 1;
}
private int Right(int index)
{
return 2 * index + 2;
}
private void MHeapify(int rootIndex, Comparison comparison)
{
int leftChildIndex = Left(rootIndex);
int rightChildIndex = Right(rootIndex);
int extremumIndex = rootIndex;
if (leftChildIndex < _heapSize && comparison(_array[leftChildIndex], _array[rootIndex]) > 0)
{
extremumIndex = leftChildIndex;
}
if (rightChildIndex < _heapSize && comparison(_array[rightChildIndex], _array[extremumIndex]) > 0)
{
extremumIndex = rightChildIndex;
}
if (extremumIndex != rootIndex)
{
Helper.Exchange(ref _array[extremumIndex], ref _array[rootIndex]);
MHeapify(extremumIndex, comparison);
}
}
private void BuildMHeap(Comparison comparison)
{
for (int i = _array.Length / 2 - 1; i >= 0; i--)
{
MHeapify(i, comparison);
}
}
public void Sort(Comparison comparison)
{
BuildMHeap(comparison);
for (int i = _array.Length - 1; i > 0; i--)
{
Helper.Exchange(ref _array[i], ref _array[0]);
_heapSize--;
MHeapify(0, comparison);
}
}
#endregion
} public class Helper
{
public static void Exchange(ref T x, ref T y)
{
T temp = x;
x = y;
y = temp;
}
} 4 알고리즘 분석
1. 전체 더미 가 정렬 되 는 과정 에서 기 존의 배열 에서 요 소 를 조작 할 뿐 상수 의 추가 공간 만 필요 합 니 다.따라서 쌓 기 정렬 은 원래 의 주소 정렬 알고리즘 으로 그 공간 복잡 도 는 O (1) 이다.
2. 매 라운드 의 최대 (작은) 화 더미 에서 가장 큰 요 소 를 지정 한 최종 위치 에 놓 기 위해 더미 의 뿌리 요소 와 마지막 요 소 를 직접 교환 합 니 다. 이 는 더미 와 마지막 요소 의 값 이 같은 요소 와 마지막 요소 의 상대 적 인 위 치 를 개편 할 수 있 습 니 다.따라서 쌓 기 순 서 는 불안정 하 다.
3. 쌓 기 정렬 의 전체 과정 에서 가장 오래 걸 리 는 작업 은 최대 (작은) 쌓 기 성질 의 MaxHeapify (MinHeapify) 과정 을 유지 하 는 데 있다.MaxHeapify (MinHeapify) 의 경우, 실행 시간의 귀속 식 은 다음 과 같 습 니 다.
T(n) <= T(2n / 3) + θ(1)
주 정리 에 따 르 면 T (n) = O (lgn) 를 알 수 있다.
따라서 쌓 기 정렬 의 시간 복잡 도 는 T (n) = nlgn 이다.
5 운행 결과
마찬가지 로 계수 요소 의 비교 횟수 에 따라 알고리즘 의 집행 규 모 를 평가 할 수 있다.
알고리즘 의 범 형 실현 버 전에 서 의뢰 로 들 어 오 는 비교 방법 에 계수 문 구 를 넣 으 면 비교 문 구 를 쉽게 실행 할 수 있 습 니 다.
private static int AscComparison(int x, int y)
{
count++;
if (x > y)
{
return 1;
}
else if (x == y)
{
return 0;
}
else
{
return -1;
}
} static void Main(string[] args)
{
for (int i = 0; i < 10000; i++)
{
// 1-100 10
int[] randomIntArray = DataCreator.CreateRandomIntArray(1, 100, 10);
Heap heap = new Heap(randomIntArray);
heap.Sort(AscComparison);
PrintAarry(randomIntArray);
}
int averageCount = count / 10000;
Console.WriteLine(averageCount);
} 테스트 결과:
n = 10， averageCount = 38= 1.144* 10 * lg10;
n = 100, averageCount = 1026= 1.544 * 100 * lg100; n = 1000, averageCount = 16851 = 1.691 * 1000 * lg1000;
n = 10000, averageCount = 235371 = 1.771 * 10000 * lg10000;
테스트 결 과 를 통 해 알 수 있 듯 이 정렬 알고리즘 의 평균 연산 시간 복잡 도 역시θ（nlgn）。
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
