KEMBAR78
Quick Sort | PDF | Computer Programming | Algorithms And Data Structures
Scribd
Upload
34 views4 pages

Quick Sort

The document provides a C++ implementation of the Quick Sort algorithm, detailing the partitioning process and recursive sorting of subarrays. It includes both code and pseudocode, explaining how the algorithm selects a pivot and organizes elements around it. The main function demonstrates user input for sorting an array and outputs the sorted result.

Uploaded by

brotin2503
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
34 views4 pages

Quick Sort

The document provides a C++ implementation of the Quick Sort algorithm, detailing the partitioning process and recursive sorting of subarrays. It includes both code and pseudocode, explaining how the algorithm selects a pivot and organizes elements around it. The main function demonstrates user input for sorting an array and outputs the sorted result.

Uploaded by

brotin2503
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

QUICK SORT:::::

CODE:

#include <iostream>

#include <vector>

using namespace std;

// Function to partition the array

int partition(vector<int> &arr, int low, int high) {

int pivot = arr[high]; // Choosing the last element as pivot

int i = low - 1; // Index for smaller element

for (int j = low; j < high; ++j) {

if (arr[j] < pivot) {

++i; // Increment index for smaller element

swap(arr[i], arr[j]);

swap(arr[i + 1], arr[high]); // Place pivot in the correct position

return i + 1;

// Quick Sort function

void quickSort(std::vector<int> &arr, int low, int high) {

if (low < high) {

int pi = partition(arr, low, high); // Partition index

quickSort(arr, low, pi - 1); // Sort the left subarray

quickSort(arr, pi + 1, high); // Sort the right subarray

int main() {
int n;

cout << "Enter the number of elements: ";

cin >> n;

vector<int> arr(n);

cout << "Enter the elements:\n";

for (int i = 0; i < n; ++i) {

std::cin >> arr[i];

// Perform Quick Sort

quickSort(arr, 0, n - 1);

// Output the sorted array

cout << "Sorted array: ";

for (const int &num : arr) {

cout << num << " ";

cout << endl;

return 0;

}
PSEUDOCODE:::::

QUICK_SORT(arr, low, high):

IF low < high:

pi = PARTITION(arr, low, high) // Get the partition index

QUICK_SORT(arr, low, pi - 1) // Sort the left subarray

QUICK_SORT(arr, pi + 1, high) // Sort the right subarray

PARTITION(arr, low, high):

pivot = arr[high] // Select the pivot element

i = low - 1 // Index for smaller element

FOR j = low TO high - 1:

IF arr[j] <= pivot:

i=i+1

SWAP arr[i] and arr[j]

SWAP arr[i + 1] and arr[high] // Place pivot in the correct position

RETURN i + 1 // Return the partition index

Quick Sort Algorithm

1. Divide:

 Select a pivot element from the array (e.g., the last element).

 Partition the array into two subarrays:

o Elements smaller than or equal to the pivot go to the left.

o Elements greater than the pivot go to the right.

2. Conquer:

 Recursively apply Quick Sort to the left subarray.

 Recursively apply Quick Sort to the right subarray.

3. Combine:

 Since the array is sorted in place, no explicit combining is needed. The subarrays and pivot
form the sorted array.

You might also like