Quick sort in Java

Refer: Main indexed article on sorting.

Quick sort is based on the principle of divide and conquer.
Quick sort first divides the large lists into two sub smaller lists, the low elements and the high elements.
It can then recursively sort the sub-lists.

How does it work?

• Choose an element and called it as pivot, in the given list.
• Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way).
• After this partitioning pivot is in its final position.
• This is called the partition operation.
• Recursively apply the above steps to the sub-lists of the elements with smaller values and separately the sub-lists of elements with greater values.

Choice of Pivot:
Generally, the last element of the partition would often be chosen as the pivot element.
Unfortunately, this causes worst-case behavior on already sorted arrays.
One can choose a random index for pivot or choose the median of the first, middle and last element.

Java Code snippet:

Bubble Sort in Java

Refer: Main indexed article on sorting.


Bubble sort is a simple sorting algorithm that works by:

• Repeatedly going through the list to be sorted
• Comparing each pair of adjacent items
• Swapping them if they are in the wrong order

The above steps are repeated till no swaps are needed.
This indicates that the list is sorted.

Note: Bubble sort should be avoided in case of large collections (large number of elements).

Algorithm:

Java code Snippet:

Merge Sort in Java

Refer: Main indexed article on sorting.

Merge Sort  is an O(n log n) comparison-based sorting algorithm.
It is a divide and conquer algorithm.

How does Merge Sort work?

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).



Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.




Java Code Snippet

Step 1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).



Step 2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.



Step 3. Code run output