[C] 힙 정렬

// heapsort.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

heapsort.cpp

#include "stdafx.h"

void Display(int A[], int n)
{

 for( int i = 0; i < n; i++)

  printf("%d ", A[i]);

 printf("\n");

}

// Heapify
// A[]    데이터가 들어가있는 배열
// p    heapify를 수행할 노드
// n    전체 데이터 갯수
// 주의 : p 노드의 자식들은 힙을 이루고 있어야 함

void heapify(int A[], int p, int n)
{

 int left = 2*p+1;
 int right = 2*p+2;
 int largest = left;
 if( left >= n )

  return;

 if( right < n && A[right] > A[left] )

  largest = right;

 if( A[p] < A[largest] )
 {

  int tmp = A[p];
  A[p] = A[largest];
  A[largest] = tmp;
  heapify(A, largest, n);

 }

}

void buildHeap(int A[], int n)
{

 int i = n/2-1;
 while( i >= 0 )

  heapify(A, i--, n);

}

void heapSort(int A[], int n)
{
 buildHeap(A, n);

 for( int last = n-1; last > 0; last--)
 {

  int tmp = A[0];
  A[0] = A[last];
  A[last] = tmp;
  heapify(A, 0, last);

 }

}

int _tmain(int argc, _TCHAR* argv[])
{

 int A[] = {3, 2, 1, 7, 4, 8, 6, 10, 9, 5};
 Display(A, 10);
 heapSort(A, 10);
 Display(A, 10);
 return 0;

}

실행 결과

그래픽요소 추가

#include "stdafx.h"
#include <stdlib.h>
#include <windows.h>

void Display(int A[], int n);

void swap(int A[], int x, int y)
{

 int t = A[x];
 A[x] = A[y];
 A[y] = t;

}

// Heapify
// A[]    데이터가 들어가있는 배열
// p    heapify를 수행할 노드
// n    전체 데이터 갯수
// 주의 : p 노드의 자식들은 힙을 이루고 있어야 함

void heapify(int A[], int p, int n)
{

 int left = 2*p+1;
 int right = 2*p+2;
 int largest = left;
 if( left >= n )

  return;

 if( right < n && A[right] > A[left] )

  largest = right;

 if( A[p] < A[largest] )
 {

  swap(A, p, largest);
  heapify(A, largest, n);

 }

}

void buildHeap(int A[], int n)
{

 int i = n/2-1;
 while( i >= 0 )

  heapify(A, i--, n);

}

void heapSort(int A[], int n)
{

 buildHeap(A, n);
 for( int last = n-1; last > 0; last--)
 {

  swap(A, 0, last);
  heapify(A, 0, last);

 }

}

void Display(int A[], int n)
{

 const char *s = "############################################";
 system("cls");
 for( int i = 1; i < n; i++)

  printf("%3d : %.*s\n", A[i], A[i], s);

 Sleep(500);

}

int _tmain(int argc, _TCHAR* argv[])
{ 

 int n = 20;
 int A[50];
 for( int i = 1 ; i <= n ; i++ )

  A[i] = rand()%30 + 1;

 Display(A, n);
 heapSort(A, n);
 Display(A, n);

 return 0;

}

실행 결과

// 정렬 속도 테스트  10만개, 100만개

// 스택크기
int A[10000000];

int _tmain(int argc, _TCHAR* argv[])
{ 

 int n = 100000;  // 10만
 //int n = 1000000;  // 100만

 for( int i = 1 ; i <= n ; i++ )

  A[i] = rand()%1000000 + 1;

 DWORD lasttime = GetTickCount();
 heapSort(A, n);
 printf("elasped time = %.3f\n", (GetTickCount() - lasttime)/1000.0f);
 
 return 0;

}

실행결과 위: 10만, 아래: 100만