22.
a. Write a program in C to sort a set of integers
using Quick sort. (Recursive)
=>
Algorithm:-
1. BEGIN
2. FUNCTION swap(a, b)
temp = a
a=b
b = temp
END FUNCTION
3. FUNCTION partition(arr, low, high)
pivot = arr[high]
i = low - 1
FOR j = low to high - 1
IF arr[j] <= pivot
i=i+1
swap(arr[i], arr[j])
END IF
END FOR
swap(arr[i + 1], arr[high])
RETURN i + 1
END FUNCTION
4. FUNCTION quickSort(arr, low, high)
IF low < high
pi = partition(arr, low, high
quickSort(arr, low, pi – 1
quickSort(arr, pi + 1, high
END IF
END FUNCTION
5. FUNCTION printArray(arr, size)
FOR i = 0 to size - 1
PRINT arr[i]
END FOR
END FUNCTION
6. MAIN
PRINT "Enter the number of elements in the array:"
INPUT n
7. ALLOCATE memory for arr of size n
IF allocation fails
PRINT "Memory allocation failed"
RETURN
8. PRINT "Enter the elements of the array:"
FOR i = 0 to n - 1
INPUT arr[i]
END FOR
9. PRINT "Original Array:"
printArray(arr, n)
10.CALL quickSort(arr, 0, n - 1)
11.PRINT "Sorted Array:"
printArray(arr, n)
12.FREE the dynamically allocated memory
13.END MAIN
14.END
Code:-
#include <stdio.h>
#include <stdlib.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function to select a pivot and partition the array
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Taking the last element as the pivot
int i = (low - 1); // Pointer for the smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to the pivot
if (arr[j] <= pivot) {
i++; // Increment the smaller element pointer
swap(&arr[i], &arr[j]); // Swap the elements
swap(&arr[i + 1], &arr[high]); // Swap pivot element with the element at i + 1
return (i + 1); // Return the pivot index
// Quick Sort function (recursive)
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // Partition the array
quickSort(arr, low, pi - 1); // Recursively sort the left part
quickSort(arr, pi + 1, high); // Recursively sort the right part
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
printf("\n");
// Main function
int main() {
int n, i;
// Ask the user for the size of the array
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
// Dynamically allocate memory for the array
int* arr = (int*)malloc(n * sizeof(int));
// Check if memory allocation was successful
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1; // Exit the program with an error code
}
// Take array input from the user
printf("Enter the elements of the array: \n");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
printf("Original Array: ");
printArray(arr, n);
quickSort(arr, 0, n - 1); // Call quickSort on the entire array
printf("Sorted Array: ");
printArray(arr, n); // Print the sorted array
// Free the dynamically allocated memory
free(arr);
return 0;
Output:-
