Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <time.h>
- #define true 1
- #define false 1
- typedef int bool_t;
- void swap(int* a, int* b)
- {
- int t = *a;
- *a = *b;
- *b = t;
- }
- int partition (int arr[], int low, int high)
- {
- int pivot = arr[high];
- int i = (low - 1);
- for (int j = low; j <= high- 1; j++)
- {
- if (arr[j] < pivot)
- {
- swap(&arr[++i], &arr[j]);
- }
- }
- swap(&arr[i + 1], &arr[high]);
- return (i + 1);
- }
- void quickSort(int arr[], int low, int high)
- {
- if (low < high)
- {
- /* pi is partitioning index, arr[p] is now
- at right place */
- int pi = partition(arr, low, high);
- // Separately sort elements before
- // partition and after partition
- quickSort(arr, low, pi - 1);
- quickSort(arr, pi + 1, high);
- }
- }
- /* Function to print an array */
- void printArray(int arr[], int size)
- {
- int i;
- for (i=0; i < size; i++)
- printf("%d ", arr[i]);
- printf("\n");
- }
- void bubbleSortFast(int arr[], int size) {
- if(arr == NULL || size == 0) {
- return;
- }
- bool_t swapped = true;
- int i = 0;
- while(i < size - 1 && swapped) {
- swapped = false;
- for(int j = 0; j < size - i - 1; ++j) {
- if(arr[j] > arr[j + 1]) {
- swap(&arr[j], &arr[j + 1]);
- swapped = true;
- }
- }
- ++i;
- }
- }
- void bubbleSort(int arr[], int size) {
- for(int i = 0; i < size; ++i) {
- for(int j = 0; j < size - 1; ++j) {
- if(arr[j] > arr[j + 1]) {
- swap(&arr[j], &arr[j + 1]);
- }
- }
- }
- }
- // Driver program to test above functions
- int main(void)
- {
- int arr[] = {12131, 7, 2, 9, 1, 5, 5, 7, 1, 0, 13131, -20, 141};
- int n = sizeof(arr) / sizeof(arr[0]);
- // TIME #1
- clock_t start;
- clock_t end;
- double time_taken;
- start = clock();
- quickSort(arr, 0, n-1);
- end = clock();
- time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
- printf("Sorted array (quickSort): ");
- printArray(arr, n);
- printf("Time taken: %f\n", time_taken);
- int arr2[] = {12131, 7, 2, 9, 1, 5, 5, 7, 1, 0, 13131, -20, 141};
- int n2 = sizeof(arr) / sizeof(arr[0]);
- // TIME #2
- start = clock();
- bubbleSortFast(arr2, n2);
- end = clock();
- time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
- printf("Sorted array (bubbleSortFast): ");
- printArray(arr2, n2);
- printf("Time taken: %f\n", time_taken);
- int arr3[] = {12131, 7, 2, 9, 1, 5, 5, 7, 1, 0, 13131, -20, 141};
- int n3 = sizeof(arr) / sizeof(arr[0]);
- // TIME #3
- start = clock();
- bubbleSort(arr3, n3);
- end = clock();
- time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
- printf("Sorted array (bubbleSort): ");
- printArray(arr3, n3);
- printf("Time taken: %f\n", time_taken);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement