Sorting and Searching Algorithms

created by Frank

1. Sorting 

in this section, we will compare the performance of basic sorting algorithms: bubble sort, selection sort, insertion sort, quick sort, and heap sort.

• in these algorithms, quick sort and heap sort are fastest but hardest to implement. (quick sort is usually fastest)
• bubble sort is simplest but the its performance is lowest 

about the complexity of algorithms:

• bubble sort: O(n2)
• insertion sort: O(n2)
• selection sort: O(n2)
• quick sort: average is O(nlogn), worst case is O(n2)
• heap sort: O(nlogn)

because these algorithms are common, we do not mention their principle here

below is source code of sort algorithms

1.1 bubble sort

download source code of bubble sort

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

#define NUM 100000

int main()
{
  int arr[NUM];
  int i, j, k;
  int temp;
  double avg = 0;
  FILE *f;

  for (k = 0; k < 6; ++k)
  {
    char c = k + 48;
    char name[]={c};
    f = fopen(name, "r");
    printf("%s%s%s\n","reading file ", name,"..." );
    for (i = 0; i < NUM; ++i)
    {
      fscanf(f, "%d", &arr[i]);
    }
    fclose(f);

    printf("%s\n", "sorting ...");
    clock_t start = clock();
    for(i = (NUM - 1); i >= 0; i--)
    {
      for(j = 1; j <= i; j++)
      {
        if(arr[j-1] > arr[j])
        {
          temp = arr[j-1];
          arr[j-1] = arr[j];
          arr[j] = temp;
        } 
      } 
    }
    clock_t end = clock();
    printf("%s\n", "sorted...");
    double t = (double)(end - start)/CLOCKS_PER_SEC;
    avg += t;
    printf("time = %f\n\n",t);
  }
  printf("sum of time = %f\n",avg);
  printf("average time = %f\n", avg/6);
  // for(i = 0; i < NUM; i++)
  //   printf(" %d", arr[i]);

  // printf("\n");
  return 0;
}

1.2 insertion sort

download source code of insertion sort

#include 
#include 
#include 

#define NUM 100000

int main()
{
  int i, j, k;
  int arr[NUM];
  double avg = 0;
  FILE *f;

  for (k = 0; k < 6; ++k)
  {
    char c = k + 48;
    char name[]={c};
    f = fopen(name, "r");
    printf("%s%s%s\n","reading file ", name,"..." );
    for (i = 0; i < NUM; ++i)
    {
      fscanf(f, "%d", &arr[i]);
    }
    fclose(f);

    printf("%s\n", "sorting ...");
    clock_t start = clock();
  
    for (i=0; i < NUM; i++)
    {
          int index = arr[i]; 
          int j = i;
          while (j > 0 && arr[j-1] > index)
          {
             arr[j] = arr[j-1];
             j--;
          }
          arr[j] = index;
    } 
    clock_t end = clock();
    printf("%s\n", "sorted...");
    double t = (double)(end - start)/CLOCKS_PER_SEC;
    avg += t;
    printf("time = %f\n\n",t);
  }
  printf("sum of time = %f\n",avg);
  printf("average time = %f\n", avg/6);
  
  return 0;
}

1.3 selection sort

download source code of selection sort

#include 
#include 
#include 

#define NUM 100000

int main()
{
  int i, j, k;
  int arr[NUM];
  double avg = 0;
  FILE *f;

  for (k = 0; k < 6; ++k)
  {
    char c = k + 48;
    char name[]={c};
    f = fopen(name, "r");
    printf("%s%s%s\n","reading file ", name,"..." );
    for (i = 0; i < NUM; ++i)
    {
      fscanf(f, "%d", &arr[i]);
    }
    fclose(f);

    printf("%s\n", "sorting ...");
    clock_t start = clock();
    for (i = 0; i < NUM-1; i++)
    {
        int min = i;
        for (j = i+1; j < NUM; j++)
            if (arr[j] < arr[min]) min = j;
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    } 
    clock_t end = clock();
    printf("%s\n", "sorted...");
    double t = (double)(end - start)/CLOCKS_PER_SEC;
    avg += t;
    printf("time = %f\n\n",t);
  }

  printf("sum of time = %f\n",avg);
  printf("average time = %f\n", avg/6);
 
 return 0;
}

1.4 quick sort

download source code of quick sort

#include 
#include 
#include 

#define NUM 100000

void quickSort( int[], int, int);
int partition( int[], int, int);

void main() 
{
 //int a[] = {7, 12, 1, -2, 0, 15, 4, 11, 9};
  int a[NUM];
 int i, k;
  long double avg = 0;
  FILE *f;

  for (k = 0; k < 6; ++k)
  {
    char c = k + 48;
    char name[]={c};
    f = fopen(name, "r");
    printf("%s%s%s\n","reading file ", name,"..." );
    for (i = 0; i < NUM; ++i)
    {
      fscanf(f, "%d", &a[i]);
    }
    fclose(f);

    printf("%s\n", "sorting...");
    clock_t begin = clock();
    quickSort(a, 0, NUM);
    clock_t end = clock();
    printf("%s\n", "sorted!!!");

    long double t = (long double)(end - begin) / CLOCKS_PER_SEC;
    printf("time = %Lf\n\n", t);
    avg += t;
  }

 printf("sum of time = %Lf\n",avg);
  printf("average time = %Lf\n", avg/6);
 
  

 // printf("\n\nSorted array is:  ");
 // for(i = 0; i < NUM; ++i)
 //  printf(" %d ", a[i]);

}

void quickSort( int a[], int l, int r)
{
   int j;

   if( l < r ) 
   {
       j = partition( a, l, r);
       quickSort( a, l, j-1);
       quickSort( a, j+1, r);
   }
 
}

int partition( int a[], int l, int r) {
   int pivot, i, j, t;
   pivot = a[l];
   i = l; j = r+1;
  
   while( 1)
   {
    do ++i; while( a[i] <= pivot && i <= r );
    do --j; while( a[j] > pivot );
    if( i >= j ) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
   }
   t = a[l]; a[l] = a[j]; a[j] = t;
   return j;
}

1.5 heap sort

download source code of quick sort

#include 
#include 
#include 

#define NUM 100000
 
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)
{
    int largest = i;  // Initialize largest as root
    int temp;
    int l = 2*i + 1;  // left = 2*i + 1
    int r = 2*i + 2;  // right = 2*i + 2
 
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    // If largest is not root
    if (largest != i)
    {
        //Swap(&arr[i], &arr[largest]);
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] =temp;
 
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}
 
// main function to do heap sort
void heapSort(int arr[], int n)
{
    // Build heap (rearrange array)
    int i;
    int temp;
    for (i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
 
    // One by one extract an element from heap
    for (i=n-1; i>=0; i--)
    {
        // Move current root to end
        //Swap(&arr[0], &arr[i]);
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] =temp;
 
        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}
 
// Driver program
int main()
{
    //int arr[] = {12, 11, 13, 5, 6, 7, 1, 2, 5, 7, 9, 10};
    int a[NUM];
    int i, k;
    long double avg = 0;
    FILE *f;


     for (k = 0; k < 6; ++k)
    {
      char c = k + 48;
      char name[]={c};
      f = fopen(name, "r");
      printf("%s%s%s\n","reading file ", name,"..." );
      for (i = 0; i < NUM; ++i)
      {
        fscanf(f, "%d", &a[i]);
      }
      fclose(f);

      printf("%s\n", "sorting ...");
      clock_t begin = clock();
      heapSort(a, NUM);
      clock_t end = clock();
      printf("%s\n", "sorted...");

      long double t = (long double)(end - begin) / CLOCKS_PER_SEC;
      printf("time = %Lf\n\n", t);
      avg += t;
    }
    
    printf("sum of time = %Lf\n",avg);
    printf("average time = %Lf\n", avg/6);
    
}

for simple, we use rand() function to generate input data of programs. the number of test case is 5 and the result is average of them.

download input data

The system for implementation: 

• Intel core I7-6820HQ CPU 2.7 GHz
• OS ubuntu 12.04 64bit
• Compiler: gcc ubuntu/linaro 4.6.3

See run time of these algorithms, we can see the dramatic difference among algorithms

	bubble	Selection	Insertion	Quick	Heap
Test case 0	30.30	9.38	6.01	0.02	0.03
Test case 1	30.39	9.39	5.99	0.01	0.03
Test case 2	30.41	9.48	5.98	0.01	0.02
Test case 3	30.38	9.43	5.95	0.01	0.03
Test case 4	30.74	9.73	5.98	0.01	0.03
Test case 5	30.38	9.55	6.08	0.01	0.03
Average	30.4333	9.4933	5.9983	0.0133	0.0283

download input data here

2. Searching 

in this section, we will review 2 common searching: sequence searching and binary searching. 

• sequence searching: 

References

https://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_s%E1%BA%AFp_x%E1%BA%BFp

http://quiz.geeksforgeeks.org/heap-sort/