Created
April 1, 2023 15:14
-
-
Save Samu31Nd/38fe59cc618592716cb09659b10f43f2 to your computer and use it in GitHub Desktop.
Quick Sort with Partition Example
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <time.h> | |
| #include <unistd.h> | |
| #include <math.h> | |
| #define VAL_MAX 500 | |
| #define SPACING 8 | |
| #define MAX_SHOWING 50 | |
| #define N_VALUES 8 | |
| //PROTOTYPES OF THE FUNCTIONS | |
| void askUserData(int*); | |
| int *createDinamicArray(int); | |
| void initQuickSort(int*,int); | |
| void quickSort(int*,int,int); | |
| int partition(int*,int,int); | |
| void fillArrWRandVar(int*,int); | |
| void showArr(int*,int); | |
| void showMsg(int); | |
| void showTime(double,char*); | |
| void freeMemory(int*); | |
| void mergeSort(int*,int,int); | |
| void merge(int*,int,int,int); | |
| //MAIN FUNCTION | |
| int main(int argc, char const *argv[]){ | |
| srand(time(NULL)); | |
| int n = N_VALUES, arrElements[] = { | |
| 2,8,7,1,3,5,6,4 | |
| }; | |
| //askUserData(&n); | |
| //arrElements = createDinamicArray(n); | |
| //fillArrWRandVar(arrElements,n); | |
| //ORDER THE ELEMENTS WITH MERGE SORT | |
| //FOR THE WORST CASE | |
| //mergeSort(arrElements,0,n); | |
| printf("Array disordered.\n"); | |
| showArr(arrElements,n); | |
| initQuickSort(arrElements,n); | |
| //freeMemory(arrElements); | |
| return 0; | |
| } | |
| //INIT FUNCTIONS | |
| void initQuickSort(int *arr,int n){ | |
| double time_spent = 0.0; | |
| clock_t t0 = clock(); | |
| quickSort(arr,0,n-1); | |
| clock_t t1 = clock(); | |
| time_spent+=(double)(t1-t0) / CLOCKS_PER_SEC; | |
| showTime(time_spent,"Quick Sort"); | |
| printf("Array ordered.\n"); | |
| showArr(arr,n); | |
| } | |
| //ALGORITHMS | |
| //QUICK SORT | |
| void quickSort(int *A,int p,int r){ | |
| if (p<r){ | |
| int q = partition(A,p,r); | |
| quickSort(A,p,q-1); | |
| quickSort(A,q+1,r); | |
| } | |
| } | |
| int partition(int *A,int p,int r){ | |
| int x = A[r]; | |
| int i = p-1; | |
| for (int j = p; j < r; j++){ | |
| if(A[j] <= x){ | |
| i++; | |
| int aux = A[i]; | |
| A[i] = A[j]; | |
| A[j] = aux; | |
| } | |
| for(int x = 0; x<N_VALUES;x++){ | |
| printf("%d ",A[x]); | |
| } | |
| printf("\ti = %d, p = %d, j = %d\n",i,p,j); | |
| } | |
| int aux = A[i+1]; | |
| A[i+1] = A[r]; | |
| A[r] = aux; | |
| for(int x = 0; x<N_VALUES;x++){ | |
| printf("%d ",A[x]); | |
| } | |
| printf("\ti = %d, p = %d\n",i,p); | |
| printf("\n"); | |
| return i+1; | |
| } | |
| //MISCELANEOUS THINGS | |
| void askUserData(int *n){ | |
| printf("How many elements?: "); | |
| scanf("%d",n); | |
| } | |
| int *createDinamicArray(int n){ | |
| int *array; | |
| array = (int*)malloc(sizeof(int)*n); | |
| if(array == NULL){ | |
| showMsg(0); | |
| exit(-1); | |
| } | |
| return array; | |
| } | |
| void fillArrWRandVar(int *arr,int n){ | |
| for (int i = 0; i < n; i++) | |
| arr[i] = (rand()%99)+1; | |
| } | |
| void showArr(int *arr, int n){ | |
| int i, showN = n; | |
| int op = 1; | |
| if(n > MAX_SHOWING){ | |
| printf("Mostrar elementos?(Si: 1 | No: 0): "); | |
| scanf("%d",&op); | |
| showN = MAX_SHOWING; | |
| } | |
| for (i = 0; i < showN && op != 0; i++) { | |
| printf("Num. [%d]: %d\n", i+1, arr[i]); | |
| } | |
| printf("\n\n"); | |
| } | |
| void showTime(double time_spent, char *algorithm){ | |
| printf("The computing time it takes to the %s is [%f]s\n", algorithm,time_spent); | |
| printf("----------------------------------------------------\n\n"); | |
| } | |
| void showMsg(int n){ | |
| char *errors[] = { | |
| "Memory Error allocating the array...", | |
| "The memory has been sucessfully liberated" | |
| }; | |
| printf("Msg: [%s]\n",errors[n]); | |
| } | |
| void freeMemory(int *arr){ | |
| free(arr); | |
| showMsg(1); | |
| } | |
| //MERGE SORT FOR ORDENING FIRST THE ARRAY | |
| //MERGE SORT// | |
| void mergeSort(int *arr,int p, int r){ | |
| int q; | |
| if(p<r){ | |
| q=p + (r - p) / 2; | |
| mergeSort(arr,p,q); | |
| mergeSort(arr,q+1,r); | |
| merge(arr,p,q,r); | |
| } | |
| } | |
| void merge(int *arr,int p, int q, int r){ | |
| int i,j,k; | |
| int n1 = q-p+1; | |
| int n2 = r-q; | |
| int left[n1+1], right[n2+1]; | |
| for (i = 0; i < n1; i++) | |
| left[i] = arr[p+i]; | |
| for (j = 0; j < n2; j++) | |
| right[j] = arr[q+j+1]; | |
| left[i] = VAL_MAX; | |
| right[j] = VAL_MAX; | |
| i = j = 0; | |
| for(k = p; k<=r ;k++){ | |
| if(left[i] <= right[j]){ | |
| arr[k] = left[i]; | |
| i++; | |
| } else { | |
| arr[k] = right[j]; | |
| j++; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment