Labs in Algorithms

Input: A sequence of $n$ numbers

(1)
\begin{align} a_1, a_2,\cdots, a_n \end{align}

Output: A permutation (reordering) $a^\prime_1, a^\prime_2,\cdots, a^\prime_n$ of the input sequence such that

(2)
\begin{align} a^\prime_1 \le a^\prime_2 \le \cdots \le a^\prime_n \end{align}

The numbers that we wish to sort are also known as the keys.

Insertion Sorting Algorithm

The following pseudocode presents the algorithm for Insertion Sort algorithm:

INSERTION − SORT(n, A)
1) for j ← 2 to n
2)    key ← A[j]
3)    :->Insert A[j] into the sorted sequence A[1..j − 1]
4)    i ← j − 1
5)    while i > 0 and A[i] > key
6)       A[i + 1] ← A[i]
7)       i ← i − 1
8)    A[i + 1] ← key

In the following, an C++ implementation of the Insertion Sort algorithm is shown.

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
void selectionSort(int n, int s[]);
int main(int argc, char** argv) {
    int n = 10;
    int s[n];
    s[0]=0;
    s[1]=10;
    s[2]=8;
    s[3]=9;
    s[4]=4;
    s[5]=1;
    s[6]=3;
    s[7]=2;
    s[8]=6;
    s[9]=11;
    cout << "Before sorting:" << endl;
    for (int i=0; i < n; i++) {
         cout << i<< "   " << s[i] << endl;
    }
    selectionSort(n,s);
    exit(0);
    return 0;
}
void selectionSort(int n, int s[])
{
    int i, key;
    for (int j = 1; j < n; j++) //n = 10: j = 1,2,...,9
    {
        key = s[j];
        i = j-1;
        while ( i >= 0 && s[i] > key) //depends on the sequence
        {
            s[i+1] = s[i];
            i--;
            cout << "Running the loop" << endl;
        }
        s[i+1] = key;
    }
    cout << "After sorting:" << endl;
    for (int i=0; i < n; i++) {
        cout << i<< "   " << s[i] << endl;
    }
}

The following code, in C/C++, can be used to sort using the Insertion-Sort algorithm a randomly given array of $n$ elements and to measure the elapsed CPU time (in seconds).

#include <sys/time.h> //or #include <time.h> depending on the compiler
#include <stdlib.h> 
#include <stdio.h> 
#include <math.h> 
 
/* Return 1 if the difference is negative, otherwise 0.  */ 
int timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1) 
{ 
    long int diff = (t2->tv_usec + 1000000 * t2->tv_sec) - (t1->tv_usec + 1000000 * t1->tv_sec); 
    result->tv_sec = diff / 1000000; 
    result->tv_usec = diff % 1000000; 
 
    return (diff<0); 
} 
 
void timeval_print(struct timeval *tv) 
{ 
    char buffer[30]; 
    time_t curtime; 
 
    printf("%ld.%06ld", tv->tv_sec, tv->tv_usec); 
    curtime = tv->tv_sec; 
    strftime(buffer, 30, "%m-%d-%Y  %T", localtime(&curtime)); 
    printf(" = %s.%06ld\n", buffer, tv->tv_usec); 
} 
 
void InsertionSort(unsigned *a, int n) 
{
  int k;
  for (k = 1; k < n; ++k) {
     int key = a[k];
     int i = k - 1;
     while ((i >= 0) && (key < a[i])) {
             a[i + 1] = a[i];
             --i;
     }
     a[i + 1] = key;
  }
}
 
int main(int argc, char *argv[]) 
{ 
    int* arrayList;
    int i;
    struct timeval tvBegin, tvEnd, tvDiff; 
    int size = atoi(argv[1]);
 
    arrayList    = malloc(sizeof(int)*size);
 
    srand(time(NULL));
    for(i=0; i<size; i++) {
        arrayList[i] = rand() % size;
    }
    puts("Before sorting");
    for(i = 0; i < size; i++)
        printf("%5d\n", arrayList[i]);
 
// begin 
    gettimeofday(&tvBegin, NULL); 
    timeval_print(&tvBegin); 
 
    InsertionSort(arrayList, size);
 
//end 
    gettimeofday(&tvEnd, NULL); 
    timeval_print(&tvEnd); 
 
     printf("Array list after sorting \n");
    for (i=0; i < size; ++i) {
         printf("%5d   %10d\n", i, arrayList[i]); 
     }
 
// diff 
    timeval_subtract(&tvDiff, &tvEnd, &tvBegin); 
    printf("%ld.%06ld\n", tvDiff.tv_sec, tvDiff.tv_usec); 
 
    return 0; 
}

Merge Sorting Algorithm

Pseudocode for the merge sorting algorithm is given in the following:

MERGE − SORT(A, p,r)
1 if p < r
2 then q ←floor((p + r)/2)
3    MERGE − SORT(A, p, q)
4    MERGE − SORT(A, q + 1,r)
5    MERGE(A, p, q,r)

Initial call: MERGE − SORT(A, 1, n).

In the following, a C++ code for implementation of Merge Sorting algorithm is presented.

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
 
using namespace std;
 
int a[50];
void merge(int,int,int);
 
//  Merge sort algorithm
void merge_sort(int low,int high)
{
 int mid;
 if(low<high)
 {
   mid=(low+high)/2;
   merge_sort(low,mid);
   merge_sort(mid+1,high);
   merge(low,mid,high);
 }
}
 
// Merge algorithm
void merge(int low,int mid,int high)
{
 int h,i,j,b[50],k;
 h=low;
 i=low;
 j=mid+1;
 
 while((h<=mid)&&(j<=high))
 {
   if(a[h]<=a[j])
   {
      b[i]=a[h];
      h++;
   }
   else
  {
     b[i]=a[j];
     j++;
  }
  i++;
 }
 if(h>mid)
 {
    for(k=j;k<=high;k++)
    {
       b[i]=a[k];
      i++;
    }
 }
 else
 {
    for(k=h;k<=mid;k++)
    {
       b[i]=a[k];
      i++;
    }
 }
 for(k=low;k<=high;k++) a[k]=b[k];
}
 
//////////// Main function ////////////////////
int main()
{
 int num,i;
 
 cout<<"********************************************************************************"<<endl;
 cout<<"                             MERGE SORT PROGRAM " <<endl;
 
 cout<<"******************************************************************* *************"<<endl;
 cout << endl << endl;
 cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN  PRESS ENTER]:"<<endl;
 cin>>num;
 cout<<endl;
 cout<<"Now, Please Enter the ( "<< num <<" ) numbers (ELEMENTS) [THEN PRESS ENTER]:"<<endl;
 for(i=1;i<=num;i++)
 {
    cin>>a[i] ;
 }
 merge_sort(1,num);
 cout<<endl;
 cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl;
 cout<<endl<<endl;
 
 for(i=1;i<=num;i++)
     cout<<a[i]<<"    ";
 
 cout<<endl<<endl<<endl<<endl;
 return(0);
}

The following code can be used to estimate the elapsed CPU time of the Merge Sorting algorithm.

#include <sys/time.h>  //Or, #include <time.h>
#include <stdlib.h> 
#include <stdio.h> 
#include <math.h> 
int* a;
int* temp;
 
/* Return 1 if the difference is negative, otherwise 0.  */ 
int timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1) 
{ 
    long int diff = (t2->tv_usec + 1000000 * t2->tv_sec) - (t1->tv_usec + 1000000 * t1->tv_sec); 
    result->tv_sec = diff / 1000000; 
    result->tv_usec = diff % 1000000; 
 
    return (diff<0); 
} 
 
void timeval_print(struct timeval *tv) 
{ 
    char buffer[30]; 
    time_t curtime; 
 
    printf("%ld.%06ld", tv->tv_sec, tv->tv_usec); 
    curtime = tv->tv_sec; 
    strftime(buffer, 30, "%m-%d-%Y  %T", localtime(&curtime)); 
    printf(" = %s.%06ld\n", buffer, tv->tv_usec); 
} 
 
void merge(int, int, int);
 
//  Merge sort algorithm
void merge_sort(int low, int high)
{
 int mid;
 if(low<high)
 {
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
 
// Merge algorithm
void merge(int low,int mid,int high)
{
 int h,i,j,k;
 h=low;
 i=low;
 j=mid+1;
 
 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   temp[i]=a[h];
   h++;
  }
  else
  {
   temp[i]=a[j];
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   temp[i]=a[k];
   i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   temp[i]=a[k];
   i++;
  }
 }
 for(k=low;k<=high;k++) a[k]=temp[k];
}
 
//////////// Main function ////////////////////
int main(int argc, char* argv[])
{
 int i;
 struct timeval tvBegin, tvEnd, tvDiff; 
 int size = atoi(argv[1]);
 a    = malloc(sizeof(int)*size);
 temp = malloc(sizeof(int)*size);
 
 srand(time(NULL));
 for(i=0; i<size; i++) {
     a[i] = rand() % size;
 }
 puts("Before sorting");
 for(i = 0; i < size; i++)
     printf("%5d\n", a[i]);
 
// begin 
 gettimeofday(&tvBegin, NULL);
 timeval_print(&tvBegin);
 
 merge_sort(1,size);
 
//end 
 gettimeofday(&tvEnd, NULL);
 timeval_print(&tvEnd);
 
 puts("After sorting");
 for(i=0;i < size; i++)
     printf("%5d\n", a[i]);
 
// diff 
 timeval_subtract(&tvDiff, &tvEnd, &tvBegin);
 printf("%ld.%06ld\n", tvDiff.tv_sec, tvDiff.tv_usec);
 
 return(0);
}

Figure below shows the elapsed CPU time as a function of the length of sequence $n$:

(3)
\begin{align} T(n) = \Theta(n\log n) \end{align}
merge.png
Bibliography
1. H. Kamberaj, Introduction to Algorithms: Learning Algorithms by Examples, Lambert Academic Publishing, 978-620-6-15263-7, March 29, 2023.

BlinkListblogmarksdel.icio.usdiggFarkfeedmelinksFurlLinkaGoGoNewsVineNetvouzRedditYahooMyWebFacebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License