Sorting Algorithms in JAVA

What is sorting?

Sorting is an algorithm that arranges the elements of any data structure in a certain order either in increasing order or decreasing order. It is an important topic in computer science and lot of research has gone into this category.

If we consider sorting algorithms in computer science then best behavior is O(nlogn)  and worse case is O(n^2). It uses different approaches to solve given problem like simple for loops or recursions.For recursion topic you can refer to my existing post BackTracking and Recursion

Let’s play a game of comparing and swaping the number each number. This game has rule, Whenever you see a number larger than previous number just swap it.

Rules are:

1. compare the two numbers.

2. Just swap the position of numbers.

Firstly declare and initialize the array 

1Bubble sort

Bubble sort is the simplest sorting algorithm. It works by iterating the input list or array from the first element to the last. Comparing each pair of elements and swapping them if needed. Bubble sort continues to iteration until no more swaps are needed. It is less used because it has high time complexity. The only advantage that bubble sort has over other implementations is that it can detect whether the input list is already sorted or not.

It has complexity in

Worst case O(n^2) ,  Best case O(n) ,   Average case  O(n^2).

 

2. Selection Sort

Selection sort algorithm work well for small files with larger values and small keys. Here swaps are made only when required.

Advantages: 

  1. It is easy to implement.
  2. No additional storage is required.

It has complexity in

Worst case O(n^2) ,  Best case O(n^2) ,   Average case  O(n^2).

3. Insertion Sort

This is simple and efficient comparison sort. Here each element removed with iteration from the input data and insert that data into the correct position.

Advantages: 

  1. It is easy to implement.
  2. Efficient for small data.
  3. It requires only constant amount of additional memory O(1) .

It has complexity in

Worst case O(n^2) ,  Best case O(n) ,   Average case  O(n/2).

4. Merge Sort

Merge sort is an example of divide and conquer strategy. It uses merging of data concept. Merging is the process of combining two sorted files to make one bigger sorted file. It is quick sort’s complement. It access data in sequential manner. It divide the input list into two parts and these are solved recursively. After solving the sub problems, they are merger by scanning.

It has complexity in

Worst case O(nlogn) ,  Best case O(nlogn) ,   Average case  O(nlogn).

4. Quick Sort

This algorithm is also an example of divide and conquer technique. It is also called partition exchange sort. It uses recursive calls for sorting the elements.

Here Divide : The list or array Array[start…..end] is divided into two non empty sub arrays Array[start…..q] and Array[q+1…….end]. Such that each element of Array[start……end] is less than or equal to each element of Array[q+1…..high].

Then Conquer: The two sub arrays Array[start……q] and Array[q+1…….end] are sorted by recursively calls  to Quick sort method below.

5. Heap Sort

While dealing with heaps you also consider the Priority Queue concept(for PQ please refer to this article Priority Queue). So Heap is a tree with special properties. The basic requirement of heap is that the value of a node must be >= or <= to the values of its children. It is also called heap property.

There are two types of heaps:

  1. Min Heap : The value of node must be less than or equal to the values of its children.
  2. Max Heap : The value of node must be greater than or equal to the values of its children.

Heap sort inserts all elements from an unsorted array into a Heap,then removes them from the root of a heap until the heap is empty.Then we apply Heapify concept onto the heap.

 

Please follow and like us:

Post Author: Ambrish Rajput

Leave a Reply

Your email address will not be published. Required fields are marked *