Quick Sort
Tue Oct 29 2024 04:26:26 GMT+0000 (Coordinated Universal Time)
Saved by
@Rohan@99
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; //pivot element
int i = (low - 1); //index of smaller element
for (int j = low; j <= high - 1; j++)
{
if (arr[j] <= pivot)
{
i++; //increment index of smaller element
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)
{
//partition the array
int pi = partition(arr, low, high);
//recursively sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void processQuickSort(int arr[], int n)
{
if (n > 1)
quickSort(arr, 0, n - 1);
}
void displayArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
cout << "Enter the size of the array: ";
cin >> *n;
*arr = new int[*n];
srand(time(0)); // Seed for random number generation
for (int i = 0; i < *n; i++) {
(*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
}
}
int main() {
int* arr;
int n;
fillDynamicArrayWithRandomValues(&arr, &n);
cout << "Unsorted array: ";
displayArray(arr, n);
processQuickSort(arr, n);
cout << "Sorted array: ";
displayArray(arr, n);
delete[] arr; // Deallocate dynamically allocated memory
return 0;
}
content_copyCOPY
Comments