Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Author : Saurav Kalsoor
- // Created On : 28 / 03/ 2022
- #include <stdio.h>
- #include<unistd.h>
- void swap(int *xp, int *yp)
- {
- int temp = *xp;
- *xp = *yp;
- *yp = temp;
- }
- void selectionSort(int arr[], int n)
- {
- int i, j, min_idx;
- // One by one move boundary of unsorted subarray
- for (i = 0; i < n-1; i++)
- {
- // Find the minimum element in unsorted array
- min_idx = i;
- for (j = i+1; j < n; j++)
- if (arr[j] < arr[min_idx])
- min_idx = j;
- // Swap the found minimum element with the first element
- swap(&arr[min_idx], &arr[i]);
- }
- }
- // A function to implement bubble sort
- void bubbleSort(int arr[], int n)
- {
- int i, j;
- for (i = 0; i < n-1; i++)
- // Last i elements are already in place
- for (j = 0; j < n-i-1; j++)
- if (arr[j] > arr[j+1])
- swap(&arr[j], &arr[j+1]);
- }
- // A function to implement bubble sort
- void recursiveBubbleSort(int arr[], int n)
- {
- // Base case
- if (n == 1)
- return;
- // One pass of bubble sort. After
- // this pass, the largest element
- // is moved (or bubbled) to end.
- for (int i=0; i<n-1; i++)
- if (arr[i] > arr[i+1])
- swap(&arr[i], &arr[i+1]),sleep(0);
- // Largest element is fixed,
- // recur for remaining array
- recursiveBubbleSort(arr, n-1);
- }
- /* Function to sort an array using insertion sort*/
- void insertionSort(int arr[], int n)
- {
- int i, key, j;
- for (i = 1; i < n; i++) {
- key = arr[i];
- j = i - 1;
- /* Move elements of arr[0..i-1], that are
- greater than key, to one position ahead
- of their current position */
- while (j >= 0 && arr[j] > key) {
- arr[j + 1] = arr[j];
- j = j - 1;
- sleep(0);
- }
- arr[j + 1] = key;
- }
- }
- // Recursive function to sort an array using
- // insertion sort
- void insertionSortRecursive(int arr[], int n)
- {
- // Base case
- if (n <= 1)
- return;
- // Sort first n-1 elements
- insertionSortRecursive( arr, n-1 );
- // Insert last element at its correct position
- // in sorted array.
- int last = arr[n-1];
- int j = n-2;
- /* Move elements of arr[0..i-1], that are
- greater than key, to one position ahead
- of their current position */
- while (j >= 0 && arr[j] > last)
- {
- arr[j+1] = arr[j];
- j--;
- sleep(0);
- }
- arr[j+1] = last;
- }
- /* 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 merge(int arr[], int l, int m, int r);
- /* l is for left index and r is
- right index of the sub-array
- of arr to be sorted */
- void mergeSort(int arr[], int l, int r)
- {
- if (l < r)
- {
- // Same as (l+r)/2 but avoids
- // overflow for large l & h
- int m = l+(r-l)/2;
- mergeSort(arr, l, m);
- mergeSort(arr, m+1, r);
- merge(arr, l, m, r);
- }
- }
- /* Function to merge the two haves arr[l..m]
- and arr[m+1..r] of array arr[] */
- void merge(int arr[], int l, int m, int r)
- {
- int i, j, k;
- int n1 = m - l + 1;
- int n2 = r - m;
- /* create temp arrays */
- int L[n1], R[n2];
- /* Copy data to temp arrays L[] and R[] */
- for (i = 0; i < n1; i++)
- L[i] = arr[l + i];
- for (j = 0; j < n2; j++)
- R[j] = arr[m + 1+ j];
- /* Merge the temp arrays back into arr[l..r]*/
- i = 0;
- j = 0;
- k = l;
- while (i < n1 && j < n2)
- {
- if (L[i] <= R[j])
- {
- arr[k] = L[i];
- i++;
- }
- else
- {
- arr[k] = R[j];
- j++;
- }
- k++;
- }
- /* Copy the remaining elements
- of L[], if there are any */
- while (i < n1)
- {
- arr[k] = L[i];
- i++;
- k++;
- }
- /* Copy the remaining elements
- of R[], if there are any */
- while (j < n2)
- {
- arr[k] = R[j];
- j++;
- k++;
- }
- }
- int partition (int arr[], int low, int high)
- {
- int pivot = arr[high]; // pivot
- int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
- for (int j = low; j <= high - 1; j++)
- {
- // If current element is smaller than the pivot
- if (arr[j] < pivot)
- {
- i++; // increment index of smaller element
- swap(&arr[i], &arr[j]);
- }
- }
- swap(&arr[i + 1], &arr[high]);
- return (i + 1);
- }
- /* The main function that implements QuickSort
- arr[] --> Array to be sorted,
- low --> Starting index,
- high --> Ending index */
- 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);
- }
- }
- // To heapify a subtree rooted with node i which is
- // an index in arr[]. n is size of heap
- void heapify(int arr[], int n, int i)
- {
- int largest = i; // Initialize largest as root
- int l = 2 * i + 1; // left = 2*i + 1
- int r = 2 * i + 2; // right = 2*i + 2
- // If left child is larger than root
- if (l < n && arr[l] > arr[largest])
- largest = l;
- // If right child is larger than largest so far
- if (r < n && arr[r] > arr[largest])
- largest = r;
- // If largest is not root
- if (largest != i) {
- swap(&arr[i], &arr[largest]);
- // Recursively heapify the affected sub-tree
- heapify(arr, n, largest);
- }
- }
- // main function to do heap sort
- void heapSort(int arr[], int n)
- {
- // Build heap (rearrange array)
- for (int i = n / 2 - 1; i >= 0; i--)
- heapify(arr, n, i);
- // One by one extract an element from heap
- for (int i = n - 1; i > 0; i--) {
- // Move current root to end
- swap(&arr[0], &arr[i]);
- // call max heapify on the reduced heap"Sorted array: \n");
- printArray(arr, n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement