123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to partition the array
int partition(vector<int>& arr, int low, int high) {
// Choosing the first element as pivot
int pivot = arr[low];
// Starting index for left subarray
int i = low;
// Starting index for right subarray
int j = high;
while (i < j) {
/* Move i to the right until we find an
element greater than the pivot */
while (arr[i] <= pivot && i <= high - 1) {
i++;
}
/* Move j to the left until we find an
element smaller than the pivot */
while (arr[j] > pivot && j >= low + 1) {
j--;
}
/* Swap elements at i and j if i is still
less than j */
if (i < j) swap(arr[i], arr[j]);
}
// Pivot placed in correct position
swap(arr[low], arr[j]);
return j;
}
// Helper Function to perform the recursive quick sort
void quickSortHelper(vector<int>& arr, int low, int high) {
/* Base case: If the array has one or no
elements, it's already sorted */
if (low < high) {
// Get the partition index
int pIndex = partition(arr, low, high);
// Sort the left subarray
quickSortHelper(arr, low, pIndex - 1);
// Sort the right subarray
quickSortHelper(arr, pIndex + 1, high);
}
}
// Function to perform quick sort on given array
vector<int> quickSort(vector<int>& nums) {
// Get the size of array
int n = nums.size();
// Perfrom quick sort
quickSortHelper(nums, 0, n-1);
// Return sorted array
return nums;
}
};
int main() {
vector<int> arr = {4, 6, 2, 5, 7, 9, 1, 3};
int n = arr.size();
cout << "Before Sorting Array: " << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// Create an instance of Solution class
Solution solution;
// Function call to sort the array using quick sort
vector<int> sortedArr = solution.quickSort(arr);
cout << "After Sorting Array: " << endl;
for (int i = 0; i < n; i++) {
cout << sortedArr[i] << " ";
}
cout << endl;
return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091
import java.util.*;
class Solution {
// Function to partition the array
public int partition(int[] arr, int low, int high) {
// Choosing the first element as pivot
int pivot = arr[low];
// Starting index for left subarray
int i = low;
// Starting index for right subarray
int j = high;
while (i < j) {
/* Move i to the right until we find an
element greater than the pivot */
while (arr[i] <= pivot && i <= high - 1) {
i++;
}
/* Move j to the left until we find an
element smaller than the pivot */
while (arr[j] > pivot && j >= low + 1) {
j--;
}
/* Swap elements at i and j if i is still
less than j */
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Pivot placed in correct position
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
// Helper Function to perform the recursive quick sort
public void quickSortHelper(int[] arr, int low, int high) {
/* Base case: If the array has one or no
elements, it's already sorted */
if (low < high) {
// Get the partition index
int pIndex = partition(arr, low, high);
// Sort the left subarray
quickSortHelper(arr, low, pIndex - 1);
// Sort the right subarray
quickSortHelper(arr, pIndex + 1, high);
}
}
// Function to perform quick sort on given array
public int[] quickSort(int[] nums) {
// Get the size of array
int n = nums.length;
// Perform quick sort
quickSortHelper(nums, 0, n - 1);
// Return sorted array
return nums;
}
}
public class Main {
public static void main(String[] args) {
int[] arr = {4, 6, 2, 5, 7, 9, 1, 3};
int n = arr.length;
System.out.println("Before Sorting Array:");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
// Create an instance of Solution class
Solution solution = new Solution();
// Function call to sort the array using quick sort
int[] sortedArr = solution.quickSort(arr);
System.out.println("After Sorting Array:");
for (int i = 0; i < n; i++) {
System.out.print(sortedArr[i] + " ");
}
System.out.println();
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
class Solution:
# Function to partition the array
def partition(self, arr, low, high):
# Choosing the first element as pivot
pivot = arr[low]
# Starting index for left subarray
i = low
# Starting index for right subarray
j = high
while i < j:
# Move i to the right until we find an
# element greater than the pivot
while arr[i] <= pivot and i <= high - 1:
i += 1
# Move j to the left until we find an
# element smaller than the pivot
while arr[j] > pivot and j >= low + 1:
j -= 1
# Swap elements at i and j if i is still
# less than j
if i < j:
arr[i], arr[j] = arr[j], arr[i]
# Pivot placed in correct position
arr[low], arr[j] = arr[j], arr[low]
return j
# Helper Function to perform the recursive quick sort
def quickSortHelper(self, arr, low, high):
# Base case: If the array has one or no
# elements, it's already sorted
if low < high:
# Get the partition index
pIndex = self.partition(arr, low, high)
# Sort the left subarray
self.quickSortHelper(arr, low, pIndex - 1)
# Sort the right subarray
self.quickSortHelper(arr, pIndex + 1, high)
# Function to perform quick sort on given array
def quickSort(self, nums):
# Get the size of array
n = len(nums)
# Perform quick sort
self.quickSortHelper(nums, 0, n - 1)
# Return sorted array
return nums
if __name__ == "__main__":
arr = [4, 6, 2, 5, 7, 9, 1, 3]
n = len(arr)
print("Before Sorting Array:")
for i in range(n):
print(arr[i], end=" ")
print()
# Create an instance of the Solution class
solution = Solution()
# Function call to sort the array using quick sort
sortedArr = solution.quickSort(arr)
print("After Sorting Array:")
for i in range(n):
print(sortedArr[i], end=" ")
print()
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
class Solution {
// Function to partition the array
partition(arr, low, high) {
// Choosing the first element as pivot
let pivot = arr[low];
// Starting index for left subarray
let i = low;
// Starting index for right subarray
let j = high;
while (i < j) {
// Move i to the right until we find an
// element greater than the pivot
while (arr[i] <= pivot && i <= high - 1) {
i++;
}
// Move j to the left until we find an
// element smaller than the pivot
while (arr[j] > pivot && j >= low + 1) {
j--;
}
// Swap elements at i and j if i is still
// less than j
if (i < j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
// Pivot placed in correct position
[arr[low], arr[j]] = [arr[j], arr[low]];
return j;
}
// Helper Function to perform the recursive quick sort
quickSortHelper(arr, low, high) {
// Base case: If the array has one or no
// elements, it's already sorted
if (low < high) {
// Get the partition index
let pIndex = this.partition(arr, low, high);
// Sort the left subarray
this.quickSortHelper(arr, low, pIndex - 1);
// Sort the right subarray
this.quickSortHelper(arr, pIndex + 1, high);
}
}
// Function to perform quick sort on given array
quickSort(nums) {
// Get the size of array
let n = nums.length;
// Perform quick sort
this.quickSortHelper(nums, 0, n - 1);
// Return sorted array
return nums;
}
}
const main = () => {
let arr = [4, 6, 2, 5, 7, 9, 1, 3];
let n = arr.length;
console.log("Before Sorting Array:");
for (let i = 0; i < n; i++) {
process.stdout.write(arr[i] + " ");
}
console.log();
// Create an instance of Solution class
let solution = new Solution();
// Function call to sort the array using quick sort
let sortedArr = solution.quickSort(arr);
console.log("After Sorting Array:");
for (let i = 0; i < n; i++) {
process.stdout.write(sortedArr[i] + " ");
}
console.log();
}
// Execute the main function
main();
