From a beginner to an expert."Vision is where all that begins..!"
From a student to a coding professional.
From a listener to an analyzer and further an implementer.
Algorithms is what all it takes to be a programmer..!
_________________________________________________
Author's message:
Hey what's up? To all the beginners like me. Let's dive into few Algorithms and understand their importance in problem solving and further their implementations at the industry level. Good luck..!
_________________________________________________________________________________
What is an algorithm?
To sound more like a dictionary, an algorithm is a set of instructions that are fed to a system to perform a particular computation. But as in we are going to experience the breeze of the algorithms, Let's take it a bit higher by stating that an algorithm is something which could formulate an effective method to approach a solution for a particular problem statement. One can create one's own algorithm and apply when required.
We humans have formulated many algorithms prior to stone age as well. Like to remove one's hands off the heat, else that would hurt. Sounds senseless? But that's an simple algorithm made from senses to solve a problem. From simple one's like these to complex algorithms like PageRank algorithm by Google, algorithms have grown to such an extent that it requires an acute, alert, active and a keen intellect to understand them. By this we could come to a conclusion that any series of steps implemented that could solve a problem is called as an Algorithm.
_________________________________________________________________________________
What do we learn now?
Let's discuss an algorithm that is well known and a widely used algorithm in many giant companies like Google, Microsoft, Facebook etc. for sorting purposes. They are basically used in database servers of the companies to sort the user's data accordingly with respect to their subject of interest such as username. The sorting algorithm which we are going to take up is a quick sort algorithm along with its implementation.
_________________________________________________________________________________
Why do sorting?
Harry Potter is sorted into Gryffindor, where as Draco Malfoy into Slytherin, so are each and every student in Hogwarts school of witchcraft and wizardry are sorted into a sorting hat's chosen house in the school. Students are sorted into their best suited house based on few considerations of the hat. Similarly, the duty of a sorting algorithm is to sort an entity and arrange into its appropriate position.
The sorting Algorithm which we are going to look into is a quick sort. The reason why we are interested in Quick sort is because of its time complexity.
The average and best case time complexity of a quick sort algorithm is O(nlogn). The worst case stands at O(n^2) which is ought to be very rare to happen in any case. Unlike other sorting algorithms, the time complexity of this sorting algorithm depends on choosing an element called as pivot. On a whole one could tell that, quick sort algorithm is the best one for sorting.
_________________________________________________________________________________
Algorithm of Quick Sort:
Quick sort algorithm is a divide and conquer algorithm. To understand about divide and conquer please go through https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm. It first divides the input array into two smaller sub-arrays: the low elements and the high elements. It then recursively sorts the sub-arrays.
- Pick an element, called a pivot element, from the array.
- Partitioning : Reorder the array so that all the elements with the value less than the pivot comes before the pivot and the elements with greater value comes after the pivot. The equal elements can go either side. After this operation, one could witness that pivot is placed in iys right position. This operation is called a partitioning operation.
- Recursively apply the above steps to the partitioned sub-arrays.
_________________________________________________________________________________
Program:
/*Quick Sort Implementation*/
import java.util.*;
class QuickSort
{
public static int partition(int arr[],int low,int high)
{
int pivot=arr[high];
int i=(low-1);
for(int j=low;j<high;j++)
{
if(arr[j]<pivot)
{
i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
int temp=arr[i+1];
arr[i+1]=arr[high];
arr[high]=temp;
return i+1;
}
public static void sort(int arr[],int low,int high)
{
if(low<high)
{
int pivotIndex=partition(arr,low,high);
sort(arr,low,pivotIndex-1);
sort(arr,pivotIndex+1,high);
}
}
public 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[])
{
Scanner s=new Scanner(System.in);
System.out.println("Enter number of elements : ");
int n=s.nextInt();
int[] a=new int[n];
System.out.println("Enter "+n+" array elements");
for(int i=0;i<n;i++) a[i]=s.nextInt();
QuickSort.sort(a,0,n-1);
System.out.println("Sorted Array is : ");
printArray(a);
}
}
______________________________________________________
Result:
Let's look into few more algorithms in my upcoming blogs. Thanks for reading. Happy Learning..!
___________
