How to use recursion in quicksort algorithm in c?
How to use recursion in quicksort algorithm in c?
1 answer
by
filiberto ,
11 days ago
@cali_green
To implement quicksort recursively in C, you can follow these steps:
- Define a function for quicksort that takes an array to be sorted, the starting index of the array, and the ending index of the array as its parameters.
- Choose a pivot element from the array (usually the last element in the array).
- Partition the array such that all elements less than the pivot are placed before it, and all elements greater than the pivot are placed after it. The pivot element will then be in its correct sorted position.
- Recursively call the quicksort function on the left and right subarrays created by the partition step.
Here is a sample implementation of quicksort using recursion in C:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <stdio.h>
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; j++) {
if (arr[j] <= pivot) {
i++;
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) {
int pi = partition(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quicksort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("
");
return 0;
}
|
In this implementation, the quicksort function recursively calls itself to sort the left and right subarrays until the entire array is sorted.