Question

Heap, Recursive Quick & Hoare Original Quick Sort in Programming Language C

Part A: Sorting algorithm implementation
Provide a non-recursive implementation of heapsort named heapsrt by modifying appropriately the recursive form of it.

HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size -1
MAX-HEAPIFY(A,1)

Provide an implementation of a recursive quick-sort algorithm named clrssrt with the following syntax and behavior.

QUICKSORT(A,p,r)
if p <r
q=Partition(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q + 1, r)

PARTITION(A,p,r)
x = A[r]
i = p - 1
for j = p to r - 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

Provide an implementation of C.A.R Hoare's original quick-sort implementation named carhsrt.

HOARE-PARTITION(A,p,r)
x = A[p]
i = p - 1
j = r + 1
while tre
repeat
j = j - 1
until A[j] <= x
repeat
i = i +1
until A[i] >= x
if i < j
exchange A[i] with A[j]
else return j

Deliverables:
Provide all (implemented) functions in a single fi le. You can use the available implementation of bubble sort as guidance.

void heapsrt (void *keys, int n, int size, int (*compare) (const void *, const void * ) );
void clrssrt (void *keys, int n, int size, int (*compare) (const void *, const void * ) );
void carhsrt (void *keys, int n, int size, int (*compare) (const void *, const void * ) );
keys : is a pointer to the input array.
n : is the dimension (number of elements) of the array.
size : is the length in bytes of the datatype of each element of the array.
compare : is a function/pointer to a function that returns an integer. Its two arguments are pointers const void * as well. Depending on whether the rst argument of compare is greater, equal, or less than the second, compare returns a positive (e.g. 1), zero (e.g. 0) or negative (e.g. -1) number.

Part B: Experimental Results:
Benchmark your code. Link your implemented code of Part A with say the testing code provided in main() of sortg.c and benchmark your functions on 4 different data-sets and 4 problem sizes. Create a table out of these timing results and include it in the form of C comments at the beginning of the submitted code le (deliverables).

Use the following problem sizes:
1. n = 64000.
2. n = 512000.
3. n = 1024000.
4. n = 8192000.

The four different data sets consist of the following test instances.
1. An array of integers where all the elements are 1234.
2. A sorted array of integers where the i-th element of the array is i, i = 1; : : : ; n.
3. A reverse sorted array of integers where the i-th element of the array is n i + 1, i = 1; : : : ; n.
4. An array whose elements are randomly chosen using function random (see sortg.c on how to setup such an array).

Describe in tabular form the running time of your implementation for each input instance. A timing of the execution of any function can be obtained similarly to the one provided in sortg.c.

Bubble Sort:

#include <stdlib.h>
#include <string.h>

void bubble(void *akeys, unsigned int n, unsigned int size, int (*compare) (const void * , const void *))
{
register int i,j,k;
char *x;
char *keys;

keys= (char *) akeys;
x = (char *) malloc(size*sizeof(char));
for(i=1;i<n;i++) {
k=i;
memcpy(x,&keys[i*size],size);
for(j=n-1;j>=i;j--) {
if (compare(&keys[(j-1)*size],&keys[j*size]) > 0) {
memcpy(x,&keys[(j-1)*size],size);
memcpy(&keys[(j-1)*size],&keys[j*size],size);
memcpy(&keys[j*size],x,size);
}
}
}
free((char *)x);
}

Sortg.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define MODULO_UINT ((unsigned int) 0x7FFFFFFF)
#define DEBUG 1
#define ELMNTS 8
#define N_SORT_ALGS 2

typedef int data;

void bubble(void *, unsigned int , unsigned int , int (*compare) (const void * , const void *));

int compare(const void *x,const void *y)
{
data xp, yp;

xp = *((data *) x);
yp = *((data *) y);
if (xp>yp) return(1);
if (xp == yp) return(0);
return(-1);
}

static struct timeval _tstart, _tend;
static struct timezone _tstruct;

void avg_tstart (void);
void avg_tend (void);
double avg_treturn (void);

void avg_tstart(void) {
gettimeofday(&_tstart, &_tstruct);
}

void avg_tend(void) {
gettimeofday(&_tend,&_tstruct);
}

double avg_treturn(void) {
double t1,t2;
t1=(double)_tstart.tv_sec + (double)_tstart.tv_usec/(1000*1000);
t2=(double)_tend.tv_sec + (double)_tend.tv_usec/(1000*1000);
return(t2-t1);
}

int main(int argc,char *argv[]) {
int i,j,k,n,runs, type;
data *ptr,*bptr;
double elapsed;
void (*gfunc[N_SORT_ALGS])(void *,unsigned int ,unsigned int,int (*) (const void *,const void *)) =
{ qsort, bubble };
char *labels[N_SORT_ALGS] = { "qsort", "bubble" };
int doalg[N_SORT_ALGS] = { 1,1 };

void (*GTYPESORT)(void *,unsigned int,unsigned int,int (*) (const void *,const void *));

n=1000;runs=1;
if (( argc <= 1 ) || (argc > 4)) {
printf("Usage: %s size input-distrib(from 1 to 5)n",argv[0]);
return(1);
}
else {
n = atoi(argv[1]);
type=atoi(argv[2]);
}

ptr = (data*) malloc(n*sizeof(data));
bptr= (data*) malloc(n*sizeof(data));
memset( ptr,0,n*sizeof(data));
memset(bptr,0,n*sizeof(data));

srandom(21+1001*11);
for(i=0;i<n;i++) {
if ( type==1 ) {
bptr[i]=ptr[i]=(data) ((n)*(random()/((double)INT_MAX)));
}
if ( type==2 ) {
bptr[i]=ptr[i]=(data) 10;
}
if ( type==3 ) {
bptr[i]=ptr[i]=(data) i+1;
}
if ( type==4 ) {
bptr[i]=ptr[i]=(data) n-i;
}
if ( type>=5 ) {
bptr[i]=ptr[i]=(data) (random()&MODULO_UINT);
}
}

for(k=0;k<N_SORT_ALGS;k++) {
if (doalg[k]==1) {
GTYPESORT=gfunc[k];

for(i=0;i<n;i++) ptr[i] = bptr[i];
if (DEBUG) {
for(i=0;i<ELMNTS;i++) printf("%d ",(int)ptr[i]); printf("...");
for(i=n-ELMNTS;i<n;i++) printf("%d ",(int)ptr[i]); printf("n");
}
elapsed=0.0; avg_tstart();

GTYPESORT(ptr,n,sizeof(data),compare);

avg_tend(); elapsed += (avg_treturn());
if (DEBUG){
for(i=0;i<ELMNTS;i++) printf("%d ",(int)ptr[i]); printf("...");
for(i=n-ELMNTS;i<n;i++) printf("%d ",(int)ptr[i]); printf("n");
}
for(i=0;i<n-1;i++) if (ptr[i]>ptr[i+1]) {printf("Not Sortedn"); }
printf("%12s : Elapsed time is: %10.8fn",labels[k],elapsed/runs);
}
}

free((void *) bptr);
free((void *) ptr);

return(0);
}

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

int Hoare_Partition( void *keys, int p, int r, int size, int (*compare) (const void *, const void * ) )
{
register int i,j,k;
char *ptr;
char *key;
key= (char *) keys;
ptr = (char *) malloc(size*sizeof(char));
memcpy(ptr,&key[p*size],size);
i = p - 1;
j = r ;
while (1) {
do {
j = j - 1;
} while ( compare(&key[j*size], ptr) > 0 );

do {
i = i + 1;
} while ( compare(&key[i*size], ptr) < 0 );

if ( i < j ) {
swap(&key[i*size], &key[j*size],size);
} else {
free(ptr);
return j+1;
}
}
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Business Modelling Problems
Homework Solution
$28.00
Business
Computer Science
Modelling
Blue Flag
Management
Operators
Estimations
Targets
Services
Equipment
Motorists
Projects
Cases
Database Management Questions
Homework Solution
$70.00
Database Management
Computer Science
Tables
Queries
Hotel for Pets
Models
Relationships
Owners
Insurance Values
Primary Key
Lists
MS Access
Why Cable TV Prefers FDM Over TDM
Homework Solution
$10.00
Computer Science
Cable
TV
FDM
TDM
Frequency
Division
Multiplexing
Time
Signal
Data
Bandwidth
Destination
Allocation
Scheme
Telephone
Cloud Computing (2000 words)
Homework Solution
$58.00
Cloud
Computing
Service
Model
Delivery
IaaS
PaaS
SaaS
Software
Infrastructure
Platform
NIST
Challenge
Distributed
Environment
Get help from a qualified tutor
Live Chats