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);
}
 
 

Binary Search


Binary search is an algorithm for finding the location of an element in a sorted list. First, it checks the middle element of the sort list; if that element is equal to the sought value then the location has been found; Othewise, the lower half or upper half is chosen for next searching based on the sought value less than or greater than the middle element. By doing so, this binary search reduces the number of elements to be checked by a factor of two each time searching and find the element in logarithmic time.

ImageHandler2

Binary Search implemented in C.

int binary_search(int sorted_list[], int low, int high, int element) {
    while (low <= high) {
        int middle = low + (high - low)/2;
        if (element > sorted_list[middle])
            low = middle + 1;
        else if (element < sorted_list[middle])
			high = middle - 1;
        else
            return middle;
    }
    return -1;
}

Binary Search in using recursion technique.

int binary_search(int sorted_list[], int low, int high, int element) {
    if (high < low)
        return -1;
    int middle = low + (high - low)/2;
    if (element < sorted_list[middle])
        return binary_search(sorted_list, low, middle-1, element);
    else if (element > sorted_list[middle])
        return binary_search(sorted_list, middle+1, high, element);
    else
        return middle;
}

Bubble Sort


Bubble sorting is a simple sorting technique in sorting algorithm. In bubble sorting algorithm, we arrange the elements of the list by forming pairs of adjacent elements. It means we repeatedly step through the list which we want to sort, compare two items at a time and swap them if they are not in the right order. Another way to visualize the bubble sort algorithm is as its name, the smaller element bubble to the top. Here is the source code implements bubble sorting algorithm in C which sorts an unordered list of integer.

#include <stdio.h>
#include <stdlib.h> 

void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
void bublesort(int list[], int n)
{
   int i,j;
   for(i=0;i<(n-1);i++)
      for(j=0;j<(n-(i+1));j++)
             if(list[j] > list[j+1])
                    swap(&list[j],&list[j+1]);
}

void printlist(int list[],int n)
{
   int i;
   for(i=0;i<n;i++)
      printf("%d\t",list[i]);
}


void main()
{
   const int MAX_ELEMENTS = 10;
   int list[MAX_ELEMENTS];

   int i = 0;
   
   // generate random numbers and fill them to the list
   for(i = 0; i < MAX_ELEMENTS; i++ ){
	   list[i] = rand();
   }
   printf("The list before sorting is:\n");
   printlist(list,MAX_ELEMENTS);
   
   // sort the list
   bublesort(list,MAX_ELEMENTS);

   // print the result
   printf("The list after sorting using bubble sorting algorithm:\n");
   printlist(list,MAX_ELEMENTS);
}