SHARE
TWEET

Untitled

a guest Aug 14th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void bubbleSort(int[], int);
  5. void insertionSort(int[], int);
  6. void quickSort(int[], int, int);
  7. void mergeSort(int[], int, int);
  8.  
  9. int main() {
  10.     int n, arr[100];
  11.     int i;
  12.     int op, cont;
  13.     do {
  14.         printf("Enter size of array: ");
  15.         scanf("%d", &n);
  16.         printf("Enter values of array:\n");
  17.         for(i = 0; i < n; i++) {
  18.             scanf("%d", &arr[i]);
  19.         }
  20.         printf("Enter sorting algorithm to use:\n1: Bubble\n2: Insertion\n3: Quick sort\n4: Merge sort\n");
  21.         scanf("%d", &op);
  22.        
  23.         switch(op) {
  24.             case 1:
  25.                 bubbleSort(arr, n);
  26.                 break;
  27.             case 2:
  28.                 insertionSort(arr, n);
  29.                 break;
  30.             case 3:
  31.                 quickSort(arr, 0, n - 1);
  32.                 break;
  33.             case 4:
  34.                 mergeSort(arr, 0, n - 1);
  35.                 break;
  36.             default:
  37.                 printf("Invalid option!");
  38.         }
  39.         for(i = 0; i < n; i++) {
  40.             printf("%d ", arr[i]);
  41.         }
  42.         printf("\nContinue? 1/0:\t");
  43.         scanf("%d", &cont);
  44.     } while(cont == 1);
  45.    
  46.     return 0;
  47. }
  48.  
  49. void bubbleSort(int arr[], int size) {
  50.     int i, j, temp;
  51.     for(i = 0; i < size - 1; i++) {
  52.         for(j = 0; j < size - i - 1; j++) {
  53.             if (arr[j] > arr[j + 1]) {
  54.                 //swap
  55.                 temp = arr[j];
  56.                 arr[j] = arr[j + 1];
  57.                 arr[j + 1] = temp;
  58.             }
  59.         }
  60.     }
  61. }
  62.  
  63. void insertionSort(int arr[], int size) {
  64.     int i, j, key;
  65.     for(i = 1; i < size; i++) {
  66.         key = arr[i];
  67.         for(j = i; j > 0 && arr[j - 1] > key; j--) {
  68.             arr[j] = arr[j - 1];
  69.         }
  70.         arr[j] = key;
  71.     }
  72. }
  73.  
  74. int partition(int arr[], int offset, int size) {
  75.     int x = arr[size];
  76.     int i = offset - 1;
  77.     int j;
  78.     int temp;
  79.     for(j = offset; j < size; j++) {
  80.         if (arr[j] <= x) {
  81.             i++;
  82.             temp = arr[i];
  83.             arr[i] = arr[j];
  84.             arr[j] = temp;
  85.         }
  86.     }
  87.     temp = arr[i + 1];
  88.     arr[i + 1] = arr[size];
  89.     arr[size] = temp;
  90.     return i + 1;
  91. }
  92.  
  93. void quickSort(int arr[], int offset, int size) {
  94.     int pivot;
  95.     if (offset < size) {
  96.         pivot = partition(arr, offset, size);
  97.         quickSort(arr, offset, pivot - 1);
  98.         quickSort(arr, pivot + 1, size);
  99.     }
  100. }
  101.  
  102. void merge(int arr[], int offset, int mid, int size) {
  103.     int n1 = mid - offset + 1;
  104.     int n2 = size - mid;
  105.     int* l = (int*)calloc(n1 + 1, sizeof(int));
  106.     int* r = (int*)calloc(n2 + 1, sizeof(int));
  107.     int i, j, k;
  108.     for(i = 0; i < n1; i++) {
  109.         *(l + i) = arr[offset + i];
  110.     }
  111.     for(j = 0; j < n2; j++) {
  112.         *(r + j) = arr[mid + j + 1];
  113.     }
  114.     *(l + n1) = 32767;
  115.     *(r + n2) = 32767;
  116.     i = j = 0;
  117.     for(k = offset; k <= size; k++) {
  118.         if(*(l + i) <= *(r + j)) {
  119.             arr[k] = *(l + i);
  120.             i++;
  121.         }
  122.         else {
  123.             arr[k] = *(r + j);
  124.             j++;
  125.         }
  126.     }
  127.     free(l);
  128.     free(r);
  129. }
  130.  
  131. void mergeSort(int arr[], int offset, int size) {
  132.     if (offset < size) {
  133.         int mid = (offset + size) / 2;
  134.         mergeSort(arr, offset, mid);
  135.         mergeSort(arr, mid + 1, size);
  136.         merge(arr, offset, mid, size);
  137.     }
  138. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top