Wrapping it Up : Sorting algorithms #4
Hey Fellows :) , Finally we have completed all the sorting algorithms, And now we will be doing the last sorting technique. After this, you will be able to move ahead to Data structures.
Today we will be doing last sorting technique "Quick Sort".
Quick Sort also helps us to sort Arrays, lists with generally large amount of data values. Examples include total number of student in a school or college.
So let's get started :) we will cover following to get a complete view of Quick Sort :-
> INTRODUCTION
> OVERVIEW
> STEP-BY-STEP IMPLEMENTATION
> CODE
> RECURSIVE APPROACH
> EXPLANATION FILE
Introduction
Quick sort follows divide-and-conquer method to sort our database by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. So you can relate it with binary search in which we were comparing the target element with middle element.
Overview
(i) Pivot : Pivot is nothing but one of the element of the array. It can be any element in the array including middle, first or last element.
(ii) How to choose Pivot : Any element can be chosen as Pivot, it doesn't depend. although there are some rules for choosing :-
1. First/Last element
2. Middle Element
3. Close to Median (element closer to median of elements)
(iii) The choice of pivot depends on your specific use case and the characteristics of your data. Randomized pivot selection or median-of-three tend to provide good average-case performance and are often preferred in practice because they help avoid worst-case scenarios
Step-by-Step approach
Assume we have an Array : [4,3,6,5,1,2,7]
(i) Choose Pivot : In this case, we are choosing middle element as a pivot.
Pivot : arr[mid] i.e. 5
(ii) Traverse and Check : Now, check for the condition that the elements at the left part of the array should be less than 'Pivot'. and elements at the right side of the array should be greater than 'Pivot'.
Elements at the left : [4,3,6] , Elements at the right : [1,2,7]
(iii) Swap : while checking the elements, if the condition for any element fails, Swap both elements of left and right sides, then move ahead in array from left side and move backward in array from right side.
Example : arr[2] > Pivot and arr[5] < Pivot , Swap both the elements
the array now look like : [4,3,2,5,1,6,7]
(iv) Repeat Step 2 and 3.
(v) Array is sorted : at the end when the base condition triggers, the function call will stop, and we will get sorted Array in the end. SEE THE RECURSIVE APPROACH FOR BASE CONDITION
Code
class qs{
public static void main(String[] args) {
int[] arr1 = {5,4,3,2,1};
QuickSort(arr1,0,arr1.length-1);
System.out.print(Arrays.toString(arr1));
}
static void QuickSort(int[] arr, int low, int high){ //low and high start and end pointers
if(low>=high){ //base condition
return;
}
int s = low;
int e = high;
int mid = s + ((e-s)/2);
int pivot = arr[mid];
while(s<=e){
while(arr[s] < pivot){
s++;
}
while(arr[e] > pivot){
e--;
}
if(s<=e){ // swap elements if above condition fails
int temp = arr[s];
arr[s] = arr[e];
arr[e] = temp;
s++;
e--;
}
}
QuickSort(arr,low,e);
QuickSort(arr,s,high);
}
}
Recursive Approach
The function calls follows three steps again and again :-
1. Traverse the right and left sides of array and check for elements.
2. Swap the elements when condition fails.
3. After swapping one element, move ahead and check for further.
Base Condition : when the both pointers from left and right side of array points to 'Pivot', stop the call.
i.e. when the start and end pointers become equal, stop the call and break the function.
Note : We are not making any copy of the Array which is sorted. Instead, we are changing the original array to the sorted one.
Explanation file
CONCLUSION
So now you have uncovered all the algorithms which plays as a pre-requisite before moving ahead to data structures. After this you can start with data structures. Congratulation to all of you :))
HAPPY CODING :)
Post a Comment