QuestionQuestion

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 PreviewSolution 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;
}
}
}...
$63.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Computer Science - Other Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats