C Online Compiler
Example: Quick Sort using Divide and Conquer in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Quick Sort using Divide and Conquer #include <stdio.h> // Function to swap two elements void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ int partition(int arr[], int low, int high) { // Step 1: Select the last element as the pivot int pivot = arr[high]; // Index of smaller element and indicates the right position of the pivot found so far int i = (low - 1); // Step 2: Traverse through all elements and compare each element with pivot 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]); } } // Step 3: Swap the pivot element with the element at (i + 1) swap(&arr[i + 1], &arr[high]); // Step 4: Return the partitioning index 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) { // Step 1: Base case for recursion - if low is less than high, continue if (low < high) { // Step 2: Partition the array and get the pivot index int pi = partition(arr, low, high); // Step 3: Recursively sort elements before partition and after partition quickSort(arr, low, pi - 1); // Sort the left sub-array quickSort(arr, pi + 1, high); // Sort the right sub-array } } // Function to print an array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { // Step 1: Initialize an unsorted array int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); // Step 2: Print the original array printf("Original array: "); printArray(arr, n); // Step 3: Apply Quick Sort to the array quickSort(arr, 0, n - 1); // Step 4: Print the sorted array printf("Sorted array: "); printArray(arr, n); return 0; }
Output
Clear
ADVERTISEMENTS