QuickSort In Java
June 23, 2017
Categorised in: Java Codes
- Divide and Conquer Strategy
- Space required is less as compared to other sorting algorithms
- Not Stable
- Best Case Time Complexity: O(n log n)
- Worst Case Time Complexity: O(n^2)
- Space Complexity: O(n log n)
class QuickSortInJava
{
/* The main function that implements QuickSortInJava()
arr[] --> Array to be sorted,
low --> Starting index (min. is 0),
high --> Ending index (max. is n-1)*/
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* correctPivotPos is index of pivot at its
correct position i.e. arr[correctPivotPos]
*/
int correctPivotPos = partition(arr, low, high);
// Recursively sort numbers
sort(arr, low, correctPivotPos-1); // Left Partition ( low <--> pivotIndex - 1)
sort(arr, correctPivotPos+1, high); // Right Partition ( pivotIndex + 1 <--> high)
}
}
/*
Pivot = last element of array.
The pivot is placed at its correct
position in sorted array and the numbers
smaller than pivot are in left half of the
partition and numbers greater than pivot are
in right half of the partition
*/
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot is last element of array
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++) // for loop : low <- to -> high
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // since i = low - 1
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Middle Position (i+1) number is swapped with Pivot Position (high) number
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1; // return position of pivot (middle)
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSortInJava obj = new QuickSortInJava();
obj.sort(arr, 0, n-1);
System.out.println("Sorted:");
printArray(arr);
}
}
/*
OUTPUT:
Sorted:
1 5 7 8 9 10
*/
QuickSort Analysis
public class QuickSortAnalysis
{
/* The main function that implements QuickSortInJava()
arr[] --> Array to be sorted,
low --> Starting index (min. is 0),
high --> Ending index (max. is n-1)*/
void sort(int arr[], int low, int high)
{
System.out.println("--------------------------");
System.out.println("(INDEX) "+ low + " < " + high + " ? ");
System.out.println("--------------------------");
if (low < high)
{
/* correctPivotPos is index of pivot at its
correct position i.e. arr[correctPivotPos]
*/
int correctPivotPos = partition(arr, low, high);
printArray(arr);
// Recursively sort numbers
System.out.println("(INDEX) Sorting: " + low + " <----> " + (correctPivotPos-1));
sort(arr, low, correctPivotPos-1); // Left Partition ( low <--> pivotIndex - 1)
System.out.println("(INDEX) Sorting: " + (correctPivotPos+1) + " <----> " + high);
sort(arr, correctPivotPos+1, high); // Right Partition ( pivotIndex + 1 <--> high)
}
}
/*
Pivot = last element of array.
The pivot is placed at its correct
position in sorted array and the numbers
smaller than pivot are in left half of the
partition and numbers greater than pivot are
in right half of the partition
*/
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot is last element of array
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++) // for loop : low <- to -> high
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // since i = low - 1
// swap arr[i] and arr[j]
System.out.println("SWAPPING: " + arr[i] + " with " + arr[j]);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Middle Position (i+1) number is swapped with Pivot Position (high) number
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1; // return position of pivot (middle)
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
System.out.println("***************");
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
System.out.println("***************");
}
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSortInJava obj = new QuickSortInJava();
obj.sort(arr, 0, n-1);
System.out.println("Sorted:");
printArray(arr);
}
}
/*
OUTPUT:
--------------------------
(INDEX) 0 < 5 ?
--------------------------
SWAPPING: 10 with 1
***************
1 5 8 9 10 7
***************
(INDEX) Sorting: 0 <----> 0
--------------------------
(INDEX) 0 < 0 ?
--------------------------
(INDEX) Sorting: 2 <----> 5
--------------------------
(INDEX) 2 < 5 ?
--------------------------
***************
1 5 7 9 10 8
***************
(INDEX) Sorting: 2 <----> 1
--------------------------
(INDEX) 2 < 1 ?
--------------------------
(INDEX) Sorting: 3 <----> 5
--------------------------
(INDEX) 3 < 5 ?
--------------------------
***************
1 5 7 8 10 9
***************
(INDEX) Sorting: 3 <----> 2
--------------------------
(INDEX) 3 < 2 ?
--------------------------
(INDEX) Sorting: 4 <----> 5
--------------------------
(INDEX) 4 < 5 ?
--------------------------
***************
1 5 7 8 9 10
***************
(INDEX) Sorting: 4 <----> 3
--------------------------
(INDEX) 4 < 3 ?
--------------------------
(INDEX) Sorting: 5 <----> 5
--------------------------
(INDEX) 5 < 5 ?
--------------------------
Sorted:
***************
1 5 7 8 9 10
***************
*/
Pratik Kataria is currently learning Springboot and Hibernate.
Technologies known and worked on: C/C++, Java, Python, JavaScript, HTML, CSS, WordPress, Angular, Ionic, MongoDB, SQL and Android.
Softwares known and worked on: Adobe Photoshop, Adobe Illustrator and Adobe After Effects.