Java Sorting Algorithms

A sorting algorithm is an algorithm that puts elements of a list in a certain order.

1. Bubble sort in java: Also referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

2.The selection sort is a combination of searching and sorting. During each pass, the unsorted element with the smallest (or largest) value is moved to its proper position in the array. The number of times the sort passes through the array is one less than the number of items in the array. In the selection sort, the inner loop finds the next smallest (or largest) value and the outer loop places that value into its proper location.

3.Insertion sort is a simple sorting algorithm; it builds the final sorted array one item at a time. It is very efficient for small data sets. Insertion sort iterates through the list by consuming one input element at each repetition, and growing a sorted output list. On a repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

The worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases, every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element.

4. Quicksort or partition-exchange sort is a fast sorting algorithm, which is using divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

Steps to implement Quick sort:

1) Choose an element, called pivot, from the list. Generally pivot can be the middle index element.https://draft.blogger.com/blogger.g?blogID=1969101077783593325 - promote

2) 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).

3) Recursively apply the above steps to the sub-list of elements with smaller values and separate the sub-list of elements with greater values.

5.Merge sort is a divide and conquer algorithm.

Steps to implement Merge Sort:
1) Divide the unsorted array into n partitions, each partition contains 1 element. Here the one element is considered as sorted.

2) Repeatedly merge partitioned units to produce new sub lists until there is only 1 sub list remaining. This will be the sorted list at the end.

Merge sort is a fast, stable sorting routine with guaranteed O(n*log(n)) efficiency. When sorting arrays, merge sort requires additional scratch space proportional to the size of the input array. Merge sort is relatively simple to code and offers performance typically only slightly below that of quicksort.