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

$63.00

or $1 if you
register a new account!

Related Homework Solutions

Gauss-Jordan Equation Method in C++
Homework Solution
$175.00
Mathematics
Computer Science
C++
Gauss-Jordan
Linear Equations
Matrices
Input Files
Output Files
Rows
Columns
Loops
Variables
Statements
Algorithm
Results
Problems Using Programming Language C
Homework Solution
$88.00
Computer Science
Programming
Algorithms
C
Structures
CSV Files
Pointers
Loops
Arrays
File Management
Variables
Statements
Input
Output
Tables
Linked Lists
Memory Allocation
Strings
Integers
Cloud Computing (2000 words)
Homework Solution
$58.00
Cloud
Computing
Service
Model
Delivery
IaaS
PaaS
SaaS
Software
Infrastructure
Platform
NIST
Challenge
Distributed
Environment
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
Telepehone Book Shell Program
Homework Solution
$50.00
Programming
Shell
Telephone Book
Users
Inputs
Outputs
Scripts
Commands
Names
Numbers
Do-While
Loops
Conditions
Search Fields
Get help from a qualified tutor
Live Chats