In c++, write a program to analyze the time complexities of four different sorti

Question

In c++, write a program to analyze the time complexities of four different sorting

algorithms. The program needs to:

Implement a random number generator function that can generate integer numbers be- tween 1 and 20000. Duplicate numbers should not be allowed. You can make use of any of the random number generating available in C library, or you can write your own pseudo random number generating code.

Implement algorithms for insertion sort, quick sort, heap sort, and merge sort. Given a choice between a recursive and an iterative version for a particular algorithm, you may choose either one.

Execute each sorting algorithm for the following different values of n, where nis the size of the list to be sorted,

n = 100, 500, 1000, 2000, 5000, 8000,10000.

In each case, the list consists of random numbers generated in step 1. For a particular value of n, the same input data (i.e., list to be sorted) should be given to all the sorting algorithms.

For each value of n, and for each sorting algorithm, obtain the actual execution time of the algorithm for the machine you are using for the cases when

a) an unsorted list is presented as the input data, and b) a sorted list is presented as the input data

5)when you generate the pseudo-random numbers, for n=100, please output the numbers to a text file

Explanation / Answer

/*Program to sort elements of an array using insertion sort method*/

#include<stdio.h>

#include<conio.h>

void main( )

{

int a[10],i,j,k,n;

clrscr( );

printf("How many elements you want to sort? ");

scanf("%d",&n);

printf(" Enter the Elements into an array: ");

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

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

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

{

k=a[i];

for(j= i-1; j>=0 && k<a[j]; j--)

a[j+1]=a[j];

a[j+1]=k;

} printf(" Elements after sorting: ");

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

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

getch( );

}

OUTPUT:

How many elements you want to sort ? : 6

Enter elements for an array : 78 23 45 8 32 36

After Sorting the elements are : 8 23 32 36 45 78

Both the selection and bubble sorts exchange elements. But insertion sort does not exchange elements. In insertion sort the element is inserted at an appropriate place similar to card insertion. Here the list is divided into two parts sorted and unsorted sub-lists. In each pass, the first element of unsorted sub list is picked up and moved into the sorted sub list by inserting it in suitable position. Suppose we have

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.