Trang chủ » Khác » Heapsort

Heapsort


Heapsort algorithm is a comparison-based sorting algorithm. The heap sort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays – one to hold the heap and the other to hold the sorted elements.
Heapsort inserts the input list elements into a heap data structure. The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order. The heap’s invariant is preserved after each extraction, so the only cost is that of extraction.
During extraction, the only space required is that needed to store the heap. In order to achieve constant space overhead, the heap is stored in the part of the input array that has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.)
Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.

 
#include <stdlib.h> 
#include <stdio.h>
 
 
#define uint unsigned int
 
typedef int (*compare_func)(int, int);

 
void heap_sort(int This[], compare_func func_pointer, uint len)
{
  /* heap sort */

  uint half;
  uint parents;

  if (len <= 1)
    return;

  half = len >> 1;
  for (parents = half; parents >= 1; --parents)
  {
    int tmp;
    int level = 0;
    uint child;

    child = parents;
    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < len) &&
          ((*func_pointer)(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    tmp = This[parents - 1];
    for (;;)
    {
      if (parents == child)
        break;
      if ((*func_pointer)(tmp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parents to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = tmp;
  }

  --len;
  do
  {
    int tmp;
    int level = 0;
    uint child;

    /* move max element to back of array */
    tmp = This[len];
    This[len] = This[0];
    This[0] = tmp;

    child = parents = 1;
    half = len >> 1;

    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < len) &&
          ((*func_pointer)(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    for (;;)
    {
      if (parents == child)
        break;
      if ((*func_pointer)(tmp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parents to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = tmp;
  } while (--len >= 1);
}

 
#define ARRAY_SIZE 250000
 
int my_array[ARRAY_SIZE];
 
void init()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    my_array[indx] = rand();
  }
}
 
int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}
 
int main()
{
  int indx;
 
  init();
 
  heap_sort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }

  return(0);
}
 
 

Bình luận

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s