Quick Sort Java Implementation

Quick Sort Java Implementation

Quick Sort is a sorting technique to sort the group of elements. It uses the divide and conquer technique to sort the elements.It is pretty much similar to Merge sort.The only difference is that why we divide the array into half always(as in Merge Sort).I prefer you to read the post about Merge Sort if you are not familiar with that technique.

Merge Sort

The highlighted idea in Quick Sort is we will select one Pivot element from the list and re-arrange the array as to get correct position of that element.Thus, we will just arrange the array as like we have smaller elements than Pivot element to the left and the larger elements to the right of the Pivot element.Then we partition the array in such way that we will not include previous Pivot element(as it's reached to its desired location)  and then recursively repeat the process.

The time complexity of Quick sort is O(n^2).

Example:-

We chose Pivot element as the last element.

9  7  5  11  12  2  14  3  10  6

6 is pivot element

5  2  3      6      12  7  14  9  10  11

Now we will perform the same steps for left and right array.

For more detail about Quick sort.Click here https://en.wikipedia.org/wiki/Quicksort

Java Implementation:-

https://github.com/suyashbhalla/other/blob/master/QuickSort.java

Spoj COURAGE - Living with Courage Java Solution

Spoj COURAGE - Living with Courage Java Solution using Segment Tree

Problem Statement:-http://www.spoj.com/problems/COURAGE/

We can easily solve the problem by using the Segment Trees.A very nicely explained and detailed on Segment Tree tutorial link is given below:-

Click on the GITHUB link to see the solution.

Solution:-https://github.com/suyashbhalla/old_practice/blob/master/spoj/COURAGE.java

Spoj CUBNUM - Cube Numbers Java Solution

Spoj CUBNUM - Cube Numbers [Java Solution] using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/CUBNUM/

Easy Problem can be solved by Dynamic Programming.It's an advice to try it yourself first.

Click on the Github link to see the solution.

Solution:-https://github.com/suyashbhalla/old_practice/blob/master/spoj/CUBNUM.java