Heap Sort in C - Iterative Algorithm

"Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort." - Wikipedia

#include<stdio.h>
#define maxheapsize 50
#define LEFT(i) 2*i
#define RIGHT(i) 2*i+1

MAX_HEAPIFY(int *a, int i, int size)
{
  // Largest of a[i], a[LEFT(i)] and a[RIGHT(i)]
  // is determined and the index is stored in "largest".
  int l, r, largest, temp;
  l = LEFT(i);
  r = RIGHT(i);
  if ((l <= size)&&(a[l] > a[i]))
    largest = l; 
  else largest = i;
  if((r <= size)&&(a[r] > a[largest]))
    largest = r;
  
  // If largest != i, swap a[i] and a[largest]
  // and heapify the subtree rooted at largest
  if(largest != i)
  {
    temp = a[i];
    a[i] = a[largest];
    a[largest] = temp;

    MAX_HEAPIFY(a, largest, size);
  }
}

BUILD_MAX_HEAP(int *a, int size)
{
  int i;

  // 2nd half of the array are leaf nodes, so each is a
  // 1-element heap to begin with.
  for(i = size/2; i > 0; i--)
    MAX_HEAPIFY(a, i, size);
}

HEAPSORT(int *a, int size)
{
  int sortedarray[maxheapsize], actualsize, root;
  int i, s = 0, j, temp;
  actualsize = size;
  
  // Build the heap tree
  BUILD_MAX_HEAP(a, size); 
  
  for(i = size; i > 0; i--)
  { 
    // Save the root to another array
    sortedarray[++s] = a[1];
    root = a[1];

    // exchange a[1](root) and a[i]
    temp = a[1];
    a[1] = a[i];
    a[i] = temp;
    
    size--;
    
    // MAX_HEAPIFY lets the value of a[i] "float down" in
    // the max-heap so that the subtree rooted at index i
    // obeys the max-heap property
    MAX_HEAPIFY(a, 1, size);

    printf("\nHeap tree after removing the largest element %d\n", root);
    for(j = 1; j<=size; j++)
      printf("%d ", a[j]);
    if(size == 0)
      printf("NULL\n");
  }

  // Print the sorted array
  printf("\nSorted array\n");
  for(i = actualsize; i > 0; i--)
    printf("%d ", sortedarray[i]);
}

int main()
{ 
  int a[maxheapsize], n, i;
  printf("\nEnter the size of the array (< 50):");
  scanf("%d", &n);
  printf("\nEnter the elements of the array\n");
  for(i = 1; i <= n; i++)
    scanf("%d", &a[i]);

  HEAPSORT(a, n);

  return 0;
}

Written by Munia Balayil

Quick Sort Using Recursion in C

"Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space." - Wikipedia

Written by Munia Balayil

Merge Sort Using Recursion in C

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

"Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945." - Wikipedia

Related articles

---

Quick Sort Using Recursion in C
Heapsort in C
Bubble Sort in C
Selection Sort in C
Binary Search in C
Basic Stack Operations in C

Written by Munia Balayil

Selection Sort in C

/*
 * At every iteration, this sorting finds the smallest element
 * in the unsorted subarray and place it in its correct location.
 * Initially the full array = unsorted subarray. If an array has
 * n elements, after 1 iteration, the unsorted subarray contains
 * n-1 elements ( all elements except the smallest one,which is
 * placed at index 0) 
 */


#include<stdio.h>


int main(void)
{
  int i,n,arr[20],j;
  int min,pos,temp;
  printf("Enter the element size:");
  scanf("%d",&n);


  printf("Enter the array elements:");
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);


  for(i=0;i<n;i++)
  {
    //Assume i^th element to be min 
    min=arr[i];
    //Compare with all other elements to find the minimum one
    for(j=i+1;j<n;j++)
    {
      if(arr[j]<min)
      {
        min=arr[j];
        pos=j;
      }
    }
   //If assumed min is not equal to actual min
   // swap their locations
    if(min!=arr[i])
    {
      temp=arr[i];
      arr[i]=min;
      arr[pos]=temp;
    }
  }


  printf("The sorted array\n");
  for(i=0;i<n;i++)
    printf("%d ",arr[i]);
  
  return 0;
}

Written by Munia Balayil

Sorting an array with all even numbers followed by odd numbers

/*
 * Input  : A sequence of numbers
 * Output : Sorts the given sequence in a way as to get all 
 *          even numbers (in ascending order) followed by all odd
 *          numbers (in ascending order).
 * Method : First, sort the elements using any of the sorting
 *          technique.Then push all even numbers to the left
 *          and odd numbers to the right.   
 */


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


int main()
{
  // Function Declaration
  void sort_even_odd();


  int *array,n,i;


  printf("Enter the number of elements\n");
  scanf("%d",&n);


  // Dynamically allocate memory for n elements
  array=(int *)calloc(n, sizeof(int));


   // Reading values to the list
  printf("Enter the elts:");
  for(i=0;i<n;i++)
    scanf("%d",&array[i]);


  // Invoking function sort_even_odd
  sort_even_odd(array,n);
  
  
  //display sorted array
  printf("sorted array:");
  for(i=0;i<n;i++)
    printf("%d ",array[i]);
  printf("\n");


  return 0;
}


void sort_even_odd(int *arr, int num)
{
  int i,j,temp,pos;
  
  // Bubble Sort
  for(i=0;i<num;i++) {
    for(j=i+1;j<num;j++) {
      if(arr[i]>arr[j])
      {
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
      }
    }
  }


  // Pushing all even numbers to the left
  j=0;
  for(i=0;i<num;i++)
  {
    if(arr[i]%2==0)
    {
      temp=arr[j];
      arr[j]=arr[i];
      arr[i]=temp;
      j++;
    }
  }


  // Note the end of the even numbers (pos)
  for(i=0;i<num;i++)
    if(arr[i]%2!=0)
    {
      pos=i;
      break;
    }


  // Sort all the numbers (odd) from pos till 
  // end of array 
  for(i=pos;i<num;i++) {
    for(j=i+1;j<num;j++) {
      if(arr[i]>arr[j])
      {
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
      } 
    }
  }   
}

Written by Munia Balayil

Bubble Sort in C

/*

 * Input  : A sequence of n numbers <a1, a2, ..., an>

 * Output : Sorted list <a1', a2', ..., an'>

 *          of the input sequence in ascending order

 * Method : Compare each pair of adjacent items and swap if

 *          they are in the wrong order. The pass through the

 *          list is repeated untill no swaps are required.

 */

#include<stdio.h>

#include<stdlib.h>

int main()

{

  // Function declaration

  void bubble_sort(int *, int);

  int *array = NULL; // Pointer to int, initialize to nothing.

  int n, i;

  printf("Enter number of elements: ");

  scanf("%d", &n);

  // Dynamically allocate memory for n elements

  array = (int *)calloc(n, sizeof(int));

  // Reading the elements

  printf("\nEnter the elements:");

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

    scanf("%d", &array[i]);

  // Invoke insertion_sort

  bubble_sort(array, n);

  // Display sorted array

  printf("sorted array:");

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

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

  printf("\n");

  return 0;

}

/*

 * Sorts the elements of the array in ascending order

 */

void bubble_sort(int *arr, int num)

{

  int i, j, temp;

  for (i = 0;i < num;i++) {

    for (j = i + 1;j < num;j++) {

      if (arr[i] > arr[j]) { // swapping

        temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

      }

    }

  }

}


Code can be downloaded @ GitHub:bubble_sort.c

Written by Munia Balayil

Selection Sort in C

/*

 * Input  : A sequence of n numbers <a1, a2, ..., an>

 * Output : Sorted list <a1', a2', ..., an'>

 *          of the input sequence in ascending order

 * Method : Find the minimum value in the list and swap

 *          it with the first position. Repeat the same for

 *          the remainder of the list, starting with the second

 *          position and advancing each time.

 */

#include<stdio.h>

#include<stdlib.h>

main()

{

  // Function declaration

  void selection_sort(int *, int);

  int *array = NULL; // Pointer to int, initialize to nothing.

  int n, i;

  printf("Enter number of elements: ");

  scanf("%d", &n);

  // Dynamically allocate memory for n elements

  array = (int *)calloc(n, sizeof(int));

  // Reading the elements

  printf("\nEnter the elements:");

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

    scanf("%d", &array[i]);

  // Invoke selection_sort

  selection_sort(array, n);

  // Display sorted array

  printf("sorted array:");

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

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

  printf("\n");

}

selection_sort(int *arr, int num)

{

  int i, j, small, pos, temp;

  for (i = 0;i < num;i++) {

    small = arr[i];

    pos = i;

    for (j = i;j < num;j++) {

      if (arr[j] < small) {

        small = arr[j];

        pos = j;

      }

    }

    temp = arr[i];

    arr[i] = small;

    arr[pos] = temp;

  }

}


Code can be downloaded @ GitHub:selection_sort.c

Written by Munia Balayil

Insertion Sort in C

/*

 * Input  : A sequence of n numbers <a1, a2, ..., an>

 * Output : Sorted list <a1', a2', ..., an'>

 *          of the input sequence in ascending order

 * Method : For any element, we assume all the elements

 *          to its left are already sorted. Shifting all

 *          the elements greater to it, in the left to one

 *          position right and then insert the key selected

 *          in the right position.

 */

#include<stdio.h>

#include<stdlib.h>

main()

{

  int *array = NULL; // Pointer to int, initialize to nothing.

  int n, i;

  printf("Enter number of elements: ");

  scanf("%d", &n);

  // Dynamically allocate memory for n elements

  array = (int *)calloc(n, sizeof(int));

  // Reading the elements

  printf("\nEnter the elements:");

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

    scanf("%d", &array[i]);

  // Invoke insertion_sort

  insertion_sort(array, n);

  // Display sorted array

  printf("sorted array:");

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

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

  printf("\n");

}

/*

 * Sorts the elements of the array in ascending order

 */

insertion_sort(int *arr, int num)

{

  int i, j, key;

  for (i = 1;i < num;i++) {

    // Select the element to be inserted to its

    // correct position

    key = arr[i];

    for (j = i - 1;j >= 0;j--) {

      if (arr[j] > key)

        arr[j+1] = arr[j];

      else

        break;

    }

    // Inserting to the right position

    arr[j+1] = key;

  }

}


Code can be downloaded @ GitHub:insertion_sort.c