write a program to

Question

a) Write a program to implement Quick sort for sorting a given set of integers in ascending order.

b) Write a program to implement Heap sort algorithm for sorting a given set of integers in ascending order.

c) Write a program to implement merge sort for sorting a given set of integers in ascending order. *

Answer 1

using namespace std;

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdlib.h>

#define MAX_INT_ARRAY_LENGTH (10)

#define MAX_FLOAT_ARRAY_LENGTH (10)

// compare callback functions for Quicksort

typedef int (*TCompareCallback) (const void *, const void*);

int CompareInt(const void * rec1, const void * rec2)

{

int * intPtr1 = (int*)rec1;

int * intPtr2 = (int*)rec2;

int iNum1 = *intPtr1;

int iNum2 = *intPtr2;

return(iNum1-iNum2);

}

int CompareStr(const void * rec1, const void * rec2)

{

char * str1 = (char*)rec1;

char * str2 = (char*)rec2;

return(strcmp(str1,str2));

}

int CompareAmount( const void * rec1, const void * rec2)

{

float * flPtr1= (float *)rec1;

float * flPtr2 = (float*)rec2;

float flAmt1 = *flPtr1;

float flAmt2 = *flPtr2;

int iReturn=0;

if (flAmt1 != flAmt2)

{

iReturn = (flAmt1>flAmt2) ? 1 : -1;

}

return(iReturn);

}

void QSortDemo(int * intNums, float * amounts, char strs[][13])

{

cout << "generating random data...." << endl;

for (int iLoop=0; iLoop<MAX_INT_ARRAY_LENGTH; iLoop++)

{

intNums[iLoop] = rand();

}

for (int iLoop=0; iLoop<MAX_FLOAT_ARRAY_LENGTH; iLoop++)

{

amounts[iLoop] = rand() + rand()*1.0f/rand();

}

cout << "sorting ... "<< endl;

qsort(intNums,MAX_INT_ARRAY_LENGTH,sizeof(int),CompareInt);

qsort(amounts,MAX_FLOAT_ARRAY_LENGTH,sizeof(float),CompareAmount);

qsort(strs,6,13,CompareStr); //probably should either pass the length of array or #define it...oh well

cout << " integers ..." << endl;

for (int iLoop=0; iLoop<MAX_INT_ARRAY_LENGTH; iLoop++)

{

cout << intNums[iLoop] << endl;

}

cout << "amounts ..." << endl;

for (int iLoop=0; iLoop<MAX_FLOAT_ARRAY_LENGTH; iLoop++)

{

cout << amounts[iLoop] << endl;

}

cout << "strings...." << endl;

for (int iLoop=0; iLoop<6; iLoop++)

{

cout << strs[iLoop] << endl;

}

}

//merges 2 sorted arrays: you can write a similar one for various types

void Merge( int * a1, int * a2, int n1, int n2, int * A)

{

int iIndexPos1=0;

int iIndexPos2=0;

int iIndexPos=0;

while ((iIndexPos1<n1) && (iIndexPos2<n2))

{

if (a1[iIndexPos1]>a2[iIndexPos2])

{

A[iIndexPos]=a2[iIndexPos2] ;

iIndexPos2++;

}

else

{

A[iIndexPos] = a1[iIndexPos1];

iIndexPos1++;

}

iIndexPos++;

}

//which one empties first????

if (iIndexPos1>=n1)

{

while (iIndexPos2 <n2) { A[iIndexPos++]=a2[iIndexPos2++]; }

}

else

{

while (iIndexPos1 < n1) { A[iIndexPos++]=a1[iIndexPos1++]; }

}

}

int main()

{

//quicksort demo

//12 byte strings : allows for null terminator

char strs [][13] = {"orange ",

"watermelon ",

"grapes ",

"strawberry ",

"apple ",

"pineapple "

};

int intNums[MAX_INT_ARRAY_LENGTH];

float amounts[MAX_FLOAT_ARRAY_LENGTH];

QSortDemo(intNums,amounts,strs);

int intNumsEven[]= { 2,4,6,8,12,16,18,24,28,32,36,48,52,56,60,64,72,80};

int intNumsOdd[] = { 3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,75,77};

int A[100];

Merge ( intNumsEven, intNumsOdd, 18, 36, A );

for (int iLoop=0; iLoop<54; iLoop++)

{

cout << A[iLoop] << endl;

}

}