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

Quicksort Algorithm

Quicksort sorts a list based on the divide and conquer strategy. In quicksort algorithm we divide the list into two sub-lists, sort these sub-lists and recursively until the list is sorted; The basic steps of quicksort algorithm are as follows:

  1. Choose a key element in the list which is called a pivot.
  2. Reorder the list with the rule that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it. After the partitioning, the pivot is in its final position.
  3. Recursively reorder two sub-lists: the sub-list of lesser elements and the sub-list of greater elements.

Here is the animation to visualize how quicksort algorithm works

Sorting_quicksort_anim

Here is source code which is implemented in C programming language to demonstrate how quicksort algorithm works:

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

void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

int choose_pivot(int i,int j )
{
   return((i+j) /2);
}

void quicksort(int list[],int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = choose_pivot(m,n);
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
	  // swap two elements
      swap(&list[m],&list[j]);
	  // recursively sort the lesser list
      quicksort(list,m,j-1);
      quicksort(list,j+1,n);
   }
}
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 using quicksort
   quicksort(list,0,MAX_ELEMENTS-1);

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