Quick Sort | Complete explanation for Beginners and Code | DSA-One Course #20 | Anuj Bhaiya | Chia sẻ về chủ đề quicksort c++ |

The complete C++ working Code below with reference to video:

#include <bits/stdc++.h>

using namespace std;

int partition(int a[], int l, int h){

int i = l, j = h;

int pivot = a[l];

while (i<j) {

while (a[i] <= pivot && i<j)

i++;

while (a[j] > pivot && i<=j)

j–;

if (i<j)

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

}

swap(a[l], a[j]);

return j;

}

void QuickSort(int a[], int l, int h){

if(l<h){

int pivot = partition(a, l, h);

QuickSort(a, l, pivot-1);

QuickSort(a, pivot + 1, h);

}

}

int main()

{

int arr[] = {10, 7, 8, 9, 1, 5, 37, 89, 28, 39};

int n = sizeof(arr) / sizeof(arr[0]);

QuickSort(arr, 0, n – 1);

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

cout<<arr[i]<<endl;

}

return 0;

}

Why didn't you write swap(pivot, arr[j]) why did you write swap(arr[j], arr[l])? Please explain

partition function is wrong ig

Very helpful video anuj bhaiya

your logic should actually look like :
while (i<j) {
while (a[i] <= pivot && i<=hi-1)
i++;
while (a[j] > pivot && j>=low)
j–;
if (i<j)
swap(a,i,j);
}

correct code

public static int partition(int arr[], int l, int h) {

int pivot = arr[l];

int i = l;

int j = h;

while (j >= 0 && i < arr.length && i < j) {

while (i<arr.length &&arr[i] <= pivot) {

i++;

}

while (j>=0 &&arr[j] > pivot) {

j–;

}

if (i < j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

int temp = arr[l];

arr[l] = arr[j];

arr[j] = temp;

return j;

}

hay Anju bhaiya …… there was a major problem on code……
please pin the comment….. for other students
if array = 10, 7, 8, 9, 1, 5
.👇🏼👇🏼👇🏼
while (arr[i]<=pivot)

i++;
//index_out_of_bound

👆🏼👆🏼👆🏼

use this……
.while (arr[i]<=pivot && i<j)

i++;

It will be while ( a[i]<= pivot && i<j)

Best Course for DSA on whole YouTube till yet❤❤

You are awesome….
I have just one doubt. Why our XOR swap method is not working in Quick Sort?

Sir, please help me in this error,
This code run on some input but
On some output it give Array out of bound index error
import java.util.Scanner;

public class QuickSort {
static int partition(int[] arr,int low,int high) {
int pivot=arr[low];
int i=low;
int j=high;
int swap;
while(i<j) {
while(arr[i] <= pivot)
{
i++;
}
while(arr[j] > pivot)
{
j–;
}
if(i<j) {
swap=arr[i];
arr[i]=arr[j];
arr[j]=swap;
}
}
swap=arr[low];
arr[low]=arr[j];
arr[j]=swap;
return j;
}

static 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);
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
System.out.println("Enter the size of array");
int n=sc.nextInt();
int[] arr=new int[n];
//Entering the Element in the array
for (int i = 0; i < arr.length; i++) {
arr[i]=sc.nextInt();
}
// Printing the Original Array
System.out.println("The Original Array is:");
for (int i : arr) {
System.out.print(i+" ");
}
System.out.println();
// Sorting the array using quick Sort
int no=arr.length;
quickSort(arr,0,no-1);

// Printing the Sorted Array
System.out.println("The Sorted Array using Quick sort is:");
for (int i : arr) {
System.out.print(i+" ");
}
sc.close();

}

}
output:

5
1 4 5 8 6
The Original Array is:
1 4 5 8 6
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at Introduction/sortingAlgorithm.QuickSort.partition(QuickSort.java:12)
at Introduction/sortingAlgorithm.QuickSort.quickSort(QuickSort.java:34)
at Introduction/sortingAlgorithm.QuickSort.quickSort(QuickSort.java:36)
at Introduction/sortingAlgorithm.QuickSort.quickSort(QuickSort.java:36)
at Introduction/sortingAlgorithm.QuickSort.quickSort(QuickSort.java:36)
at Introduction/sortingAlgorithm.QuickSort.main(QuickSort.java:58)

It's failing with test case {23, 13,45,67,89,2,10,86}. Because we have not checked in while loop for I and j with lower and upper limits. But it's great explanation. Thanks for such nice explaination