The program has to be written in C language, not C++ 1 Introduction In earlier c

Question

The program has to be written in C language, not C++

1 Introduction In earlier classes you learned a fast sorting algorithm called Quick Sort. Let's review the basic idea of quick sort. The basic concept is this: Partition the list into three sublists based on a pivot value. -Same: holds the values the same as the pivot value. -Less: holds values less than the pivot value. -More: hold the values greater then the pivot value. Recursively call quick sort on the same and more lists. Concatenate the results of the two recursive calls with the same list in the order Return the result of the concatenation. For this homework you will implement quick sor t two different ways; non-threaded and The goal is to see if threading quick sort can increase its time. The non-threaded version quick sorts the less then quick sorts the more. Can we decrease the run-time by doing the quick sort of the more at the same time as the less? 1.1 Quick Sort Review Included with this homework is the CS1 lecture notes for quick sort, FastSorts-stu.pdf and quicksort.py. Review this material to get a refresher on how quick sort works. 2 The Assignment You will be implementing recursiveoq Along with this you will create a function to make a randomly populated array of numbers. The size of the array wil be provided by the user as a command line argument. You will be required to properly manage memory in your program and use dynamically allocated arrays. quick sort two different ways; non-threaded and threaded The functionality below should be in a file called quick aort.c

Explanation / Answer

1.quick sort

#include<stdio.h>
void swap(int* x, int* y)
{
int p = *x;
*x = *y;
*y = p;
}
int partition (int array[], int l, int h )
{
int pivot = array[h];   
int i = (l - 1);  
for (int j = l; j <= h- 1; j++)
{
if (array[j] <= pivot)
{
i++;   
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[h]);
return (i + 1);
}
array[] --> Array to be sorted,
l --> Starting index,
h --> Ending index */
void quickSort(int array[], int l, int h)
{
if (l < h)
{
int pi = partition(array, l, h);
quickSort(array, l, pi - 1);
quickSort(array, pi + 1, h);
}
}
void printArray(int array[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}

threaded quick sort:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
void *triHoare (void * arg);
int PivotSelection (int indStart, int indEnd);
int Split (int tab[], int pivot, int indStart, int indEnd);
int MTAB;
struct prm   
{
int indStart;
int indEnd;
int tab[100];
};   
int main(void)
{
struct prm arg;
int i; pthread_t thred;
arg.indStart= 0;
arg.indEnd = (MTAB-1);
printf("Please input array size : ");
scanf("%d",&MTAB);
for(i=0;i<MTAB;i++)
{
printf(" please input tab[%d] :",i);
scanf("%d",&arg.tab[i]);
}
printf("Before sorting : ");   
for(i = 0; i < MTAB; i++) printf(" %d ",arg.tab[i]);
printf(" ");
if(pthread_create (&thred, NULL,*triHoare,&arg) ==0)
printf (" first thread created ");
else
{
perror("Creation failure");
exit(EXIT_FAILURE);
}
return 0;   
}
int PivotSelection ( int indexStart, int indexEnd)
{ return (indStart+indEnd) /2;}
void *triHoare (void * arg){
struct prm *p=(struct prm*) arg;
struct prm arg1,arg2;
pthread_t id_thread;
pthread_t ig_thread;
int pivot = PivotSelection (p->indStart,p->indEnd);   
int SplitInd,t1,t2;
SplitInd = Split(p->tab, pivot,p->indStart,p->indEnd);
arg1.indStart = p->indStart;
arg1.indEnd = SplitIndex;
arg1.tab[MTAB]= p->tab[MTAB];
arg2.indStart = SplitInd+1;
arg2.indEnd = p->indEnd;
arg2.tab[MTAB]= p->tab[MTAB];
if(p->indEnd > p->indStart)
{
t1= pthread_create (&id_thread, NULL,*triHoare,&arg1);
if (t1 < 0)
{
prrr(" creation threadG failure ");
exit(EXIT_FAILURE);
}
t2= pthread_create (&ig_thread, NULL,*triHoare,&arg2);
if (t2 < 0)
{
perror("creation threadD failure");
exit(EXIT_FAILURE);
}
if (pthread_join(id_thread, NULL))
prrr("pthread_join");
if (pthread_join(ig_thread, NULL))
prrr("pthread_join");
}
printf("End first thread ");
return (EXIT_SUCCESS);
}
int Split (int tab[], int pivot, int i, int j)
{
int rigt,lft;  
int valeurPivot= tab[pivot];
int x=0;
lft= i;
rigt= j;
while(lft < rigt)   
{
while(( valeurPivot > tab[lft])
&& (lft < j))
lft++;
while(( valeurPivot < tab[right])
&& ( rigt > i))
rigt--;   
if (lft< rigt) {x= tab[lft];tab[lft]= tab[ rigt];tab[rigt]=x;}
}
if (i==j) {printf("tab[%d]=%d ",i,tab[i]);}
return ( rigt);}

NOn thread quick sort:

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
void printArr(int *arr, int l, int h)
{
while(l<= h)
{
printf("%d ", arr[l++]);
}
printf(" ");
}
void swap(int *p, int *q)
{
int t= *p;
*p = *q;
*q = t;
}
int getPivot(int *arr, int l, int h)
{
return l;
}
int partition(int *arr, int l, int h, int piv)
{
int cur = l;
swap(&arr[piv], &arr[h]);
while (l <= h)
{
if(arr[l] < arr[h])
{
swap(&ary[l], &arr[cur]);
cur++;
}
l++;
}
swap(&arr[cur], &arr[h]);
return cur;
}
void qsortLH(int *arr, int l, int h)
{
if(l < h)
{
int piv = getPiv(arr, l, h);
piv = partition(arr, l, h, piv);
qsortLH(arr, l, piv - 1);
qsortLH(arr, piv + 1, h);
}
}
int main(int argc, char**argv) {
int *arr = (int *) malloc(sizeof(int)*8);
array[0] = 1;
array[1] = 4;
array[2] = 6;
array[3] = 58;
array[4] = 4;
array[5] = 2;
array[6] = 7;
array[7] = 23;
printArr(array, 0, 7);
qsortLH(array, 0, 7);
printArr(array, 0, 7);
return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.