This code is implemented and provoded by 'Abdul Samad' from A.K.G. College, Ghaziabad, UP, India.
The Quick sort algorithm is one of the best sorting algorithm. It is based on Divide and Conquer approach. In Worst case it has a complexity of O(n2).
In this algorithm we are selecting the last element of array as a pivot. The Element from which we are going to divide the array.
Note: Please save this clas inside QuickSort.java file
public class QuickSort
{
// method to sort the elements of the array with respect to pivot
static int quickSort(int[] array, int start, int end)
{
// Considering the last element as pivot
int pivot = array[end];
int i = start - 1;
int temp;
//This loop will move all the smaller elements of the array with respect to pivot towards the left hand side and all the bigger elements towards the right hand side respectively the pivot
for (int j = start; j < end + 1; ++j)
{
//if the element at jth position is smaller or equal to pivot we swap it with
//the element at i+1 position(because at this position the element is always bigger than pivot)
if (array[j] <= pivot)
{
i++;
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
//returning the index of the pivot.
return i;
}
// This method will call the quickSort() method each time for sorting the array using different pivot elements
// It will also recursively call itself until a base criteria is meet.
static void callQuickSort(int[] array, int start, int end)
{
//base criteria condition or recursive condition
if (start < end)
{
//getting the index of the pivot element in the array after the sorting has occcured with respect to that pivot.
int pivotIndex = quickSort(array, start, end);
//Recursive calls->
//Recursive call for sorting array elements to the left of pivot.
callQuickSort(array, start, pivotIndex - 1);
//Recursive call for sorting array elements to the right of pivot.
callQuickSort(array, pivotIndex + 1, end);
}
}
//main method for calling the above defined static methods to sort array
public static void main(String[] args)
{
//Defining an array.
int[] array = {10,1,20,2,30,3,1};
//Calling the callQuickSort() method to sort the above array.
QuickSort.callQuickSort(array, 0, array.length - 1);
//Loop to display the array
for (int i = 0; i < array.length; i++)
{
System.out.print(array[i]+"\t");
}
} // end of main method
} // end of class
Output is:
1 1 2 3 10 20 30
The Quick sort algorithm is one of the best sorting algorithm. It is based on Divide and Conquer approach. In Worst case it has a complexity of O(n2).
In this algorithm we are selecting the last element of array as a pivot. The Element from which we are going to divide the array.
Note: Please save this clas inside QuickSort.java file
public class QuickSort
{
// method to sort the elements of the array with respect to pivot
static int quickSort(int[] array, int start, int end)
{
// Considering the last element as pivot
int pivot = array[end];
int i = start - 1;
int temp;
//This loop will move all the smaller elements of the array with respect to pivot towards the left hand side and all the bigger elements towards the right hand side respectively the pivot
for (int j = start; j < end + 1; ++j)
{
//if the element at jth position is smaller or equal to pivot we swap it with
//the element at i+1 position(because at this position the element is always bigger than pivot)
if (array[j] <= pivot)
{
i++;
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
//returning the index of the pivot.
return i;
}
// This method will call the quickSort() method each time for sorting the array using different pivot elements
// It will also recursively call itself until a base criteria is meet.
static void callQuickSort(int[] array, int start, int end)
{
//base criteria condition or recursive condition
if (start < end)
{
//getting the index of the pivot element in the array after the sorting has occcured with respect to that pivot.
int pivotIndex = quickSort(array, start, end);
//Recursive calls->
//Recursive call for sorting array elements to the left of pivot.
callQuickSort(array, start, pivotIndex - 1);
//Recursive call for sorting array elements to the right of pivot.
callQuickSort(array, pivotIndex + 1, end);
}
}
//main method for calling the above defined static methods to sort array
public static void main(String[] args)
{
//Defining an array.
int[] array = {10,1,20,2,30,3,1};
//Calling the callQuickSort() method to sort the above array.
QuickSort.callQuickSort(array, 0, array.length - 1);
//Loop to display the array
for (int i = 0; i < array.length; i++)
{
System.out.print(array[i]+"\t");
}
} // end of main method
} // end of class
Output is:
1 1 2 3 10 20 30
No comments:
Post a Comment