Data Structure and algorithms

Question

In a school, students of 5th Grade are going for a picnic. For a particular game between 10 players, they needs to be organized in the ascending order of their height. Teacher selects a one random student out of 10. That student acts as a mediator, all students having height less than mediator goes on left and rest on his right. The same process repeats again between the left and right group. The process continues and will stop when all the players are in ascending order of their height. Signify which sorting algorithm can be helpful to design this model and how. What additional functionality can you add to this. Implement the given model.  

Answer 1

That is the QuickSort algorithm, which is found in stdlib.h

1) chooses pivot element

2) beginning from the left, moves the left pointer forward until it points

at an element that is GREATER than or equal to the pivot.

3) beginning from the right, finds the first element that is smaller than the pivot

4) swaps

repeats steps 2-4 until the pointers cross...

splits the array in two pieces and recursively repeats the entire process

on each sub-array

-----------------------------------------

using namespace std;

#include <iostream>

#include <stdlib.h>

#include <string.h>

/*****************************

Quicksort takes the following parameters

1) the array to be sorted

2) the # of items elements in the array

3) the size of each element in the array

4) a function which takes two void pointers

and returns an int

that is,the function header it int CompareXXX( const void *, const void *);

**************************************/

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

{

int * ptr1 = (int *)rec1;

int * ptr2 = (int *)rec2;

int iNum1 = *ptr1;

int iNum2 = *ptr2;

return(iNum1-iNum2);

}

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

{

float * ptr1 = (float *) rec1;

float * ptr2 = (float *) rec2;

float flNum1 = *ptr1;

float flNum2 = *ptr2;

int iReturn=0;

if (flNum1!=flNum2)

{

iReturn = (flNum1>flNum2) ? 1 : -1;

}

return(iReturn);

}

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

{

return(

strcmp(

(char*)rec1, (char*)rec2

)

);

}

int main()

{

int intArray [] = { 11, 22, 15, 29, 17, 25, 13, 24, 21, 27};

float flArray [] = { 42.35, 12.34, 33.33, 2.723, 10.51, 35.42, 3.142, 7.11, 24.576, 21.7769};

//12 BYTE STRINGS !!!!

char strs[7][13]; //allows for null terminator

memset(strs,0,91); //initializes: 7*13=91

char * s[] = { (char*)"STRAWBERRY ",

(char*)"CHERRY ",

(char*)"WATERMELON ",

(char*)"GRAPES ",

(char*)"PINEAPPLE ",

(char*)"ORANGE ",

(char*)"APPLE "};

//copies the string constants into the array

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

{

strncpy(strs[iLoop],s[iLoop],12);

}

//Quicksort calls

qsort(intArray,10,sizeof(int),CompareInt);

qsort(flArray,10,sizeof(float),CompareFloat);

qsort(strs,7,13,CompareStr);

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

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

{

cout << intArray[iLoop] << endl;

}

cout << "************************************" << endl;

cout << "floats..." << endl;

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

{

cout << flArray[iLoop] << endl;

}

cout << "************************************" << endl;

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

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

{

cout << strs[iLoop] << endl;

}

}