Sort algorithms Java implementation

In this post I will show you the Java implementation of the most common sort algorithms with their basic properties like stability, best , average and worst case.

Stability is the property of the search algorithm that guaranties that two elements that are same ( A1 and A2) will keep their order after the sort is completed.

For example if we have array like this A1, B1, A2, C1,D1 , after sorting process we wil have A1, A2, B1, C1,D1 in stable algorithm and may result A2, A1, B1, C1,D1 in unstable one.

There are several types of algorithms:

Simple Algorithms

  • Insertion sort
  • Selection sort

Efficient Algorithms

  • Merge sort
  • Heap sort
  • Quick sort

Bubble sort and variants

  • Bubble
  • Shell

Insertion Sort

Insertion sort is simple algorithm, efficient on small number of items or when array is presorted. It is usually used as a part of more advanced algorithms like shell sort.

Key properties:

  • Stable: YES
  • Best case : N, when sorting almost sorted data
  • Worst and average case : N^2
  • Memory: 1, does not require additional memory

We have two loops, one outer loop( indexed by i) goes from index 1 to N and inner that goes from i to 0.

Inner loop is the key of the algorithm, it moves i-th element back to its correct position or to the start of the array ( basically this is the same since this element is the smallest).

If i-th element is smaller then the j-th element then swap them. Do that until you reach start of the array or element is not smaller. This way element is either the smallest in the array or it is in its correct location.

Observe the currentIndex–, every time we swap and the outer loop element moves to the left of the array we need to update the current index so that it points to correct element. Correct element is the original i-th element that got moved left.

Selection sort

Selection sort is in-place comparison sorting algorithm that usually performs worse then insertion sort, but it uses less swaps , so when swapping is a problem this is good solution.

Key properties:

  • Stable: NO
  • Best case : N^2
  • Worst and average case : N^2
  • Memory: 1, does not require additional memory

We have two loops outer and inner, for every element of the outer loop go the the end of the array and find the minimum. Then swap the outer element with the minimum. Key advantage is that when element jumps 5 places we swap only once.

Merge sort

Merge sort sort by splitting the array into smaller and smaller arrays until we reach atomic level, atomic level is simply sorted and then we go up and finish the sort.

Key properties:

  • Stable: YES
  • Best case : n log(n)
  • Worst and average case : n log(n)
  • Memory: N, does  require additional memory

Original 8, 1, 6, 4, 3 ,7

Split 1:    (8,1,6)   (4,3,7)

Split 2     (8, 1)  (6) (4,3) (7)

Note that we have reached atomic level, now we order the items

8,1 becomes 1,8

1,8,6 becomes 1,6,8

4,3 becomes 3,4

4,3, 7 becomes 3,4, 7

1,6,8,3,4,7 becomes 1,3,4,6,7,8

Observe the exit of the recursion, here we exit when atomic level is reached and there is only 1 element in the section.

In above example we have 8, 1 of indexes 0 and 1.

int middle = (0+1)/2;// equals 0

mergeSort(array, tmp, 0, 0); //start and end are the same
mergeSort(array, tmp, 0 + 1, 1); //start and end are the same

Heap Sort

Key properties:

  • Stable: NO
  • Best case : n log(n)
  • Worst and average case : n log(n)
  • Memory: 1, does not require additional memory

Heap sort uses a tree like structure called heap , first it arranges the array into a heap. For example 8, 1, 6, 4, 3 ,7 is 8 7 6 4 3 1.  Observe that we have a array representation of the tree, this means that first element is array[1], his children are array[2] and array[3], children of element two are array[4] and array[5]. You might guess the pattern here children of any element are calculated by

Child 1: index * 2

Child 2: index * 2 +1

This is very important math since it allows us to go up and down the tree.

After the heap is arranged it moves the first element ( that is the biggest ) and moves it to the end of the array, then it rearranges the tree again as a result we have sorted array.

First phase is executed in the look starting from N/2 to 1, reason for this is that we want to start working from the bottom of the tree up to the top.

  1. Initially maxSort is called with parameters array, 3, 7. index 3 references the children 2 and 4.
  2. while 2 * 3 < 7 do
  3. first child has index 6
  4. if index is not illegal check if first child is lesser than second child
  5. use the bigger child ( this is done in j++)
  6. if p is > child this means that part satisfies the heap
  7. p < child this means that we must move the child up
  8. Use next element with index 2 and children 1 and 2 …

After the heap is in order we must order the array, this is done using the while loop,

  1. We move the top element to the end of the array  exchange(array, 1, N--);
  2. Then we order the heap again putting the max element on the top ( observe that we are excluding the area of the array that is sorted.
  3. Repeat

 

Quick Sort

Quick sort is sort algorithm that uses partitioning , we will observe the the code later on. Algorithm splits the array into two parts separated by a pivot, then moves all elements in the right side that are greater then the pivot and moves all elements that are smaller to the left side. Again and again it splits the parts into two smaller parts and repeats the arranging until the array is sorted.

Key properties:

  • Stable: NO
  • Best and average case : n log(n)
  • Worst  case : n^2
  • Memory: 1, does not require additional memory

  1. Pivot is element with value 6
  2. Low is element with value 8
  3. High is element with value 3
  4. Now we go to while loop and check is 8< 6 -> NO
  5. Now we go to next while loop and check if 3>6 -> NO
  6. Check if Low < Hight -> exchange 8 and 3, move low to element with value 1 and move the hight to element with value 4
  7. First while loop will jump over the element 1
  8. Second while loop will stay on element 4
  9. Exchange will happen on 4 and 6
  10. Result is now 3 1 4 6 8, low is 6, high is 4
  11. Next we go to recursion, from 0 to high and from low to end.
  12. First recursion is interesting here, 3 1 4
  13. Pivot is 1
  14. is 3 < then 1 NO
  15. is 4 > then 1 YES, High is 1
  16. Exchange 3 and 1
  17. Result is now 1 3 4 6 8
  18. END

Bubble sort

Key properties:

  • Stable: YES
  • Best case : n
  • Worst and average case : n^2
  • Memory: 1 , does  require additional memory

Sorting algorithm that goes through the list comparing the elements and putting the wrong elements into position. It is called bubble sort because the biggest elements tend to bubble first to the top. It is simple to implement but it is not so efficient.

Using two loops, for each element compare it to the all next elements and if element is bigger swap it. When no swaps are made exit the loop.

Shell sort

Key properties:

  • Stable: NO
  • Best case : n log n
  • Worst case : n log ^2 n
  • Average case : n log ^2 n
  • Memory: 1 , does  require additional memory

Main property of shell sort is that it allows elements to jump from one end of the array to the other easily. This is achieved by sorting the array in big gaps at first and going down to the 1. When we reach size of the step 1 array is already partly sorted and using the insertion sort we are able to quickly sort the array.

Before starting the sort one must decide the gap sequence, this can be tricky since there are multiple gap sequences to be selected where each one has  especial properties. In this implementation I have used  Knuth’s sequence, you can see more about it here.