Introduction to Java Sorting Algorithms
Sorting is the process of rearranging a set of items in a specific order. Sorting is essential in data processing so that applications would be able to access them more efficiently. An example of sorting can be done using databases with clauses in SQL statements like “Order By” or “Group By”.
Algorithm is a sequence of method/instructions which can be followed to peformed a specific task, such as calculation and data processing.
Therefore, a Sorting Algorithm is an algorithm with the purpose of rearranging items in a specific order. In the context of Computer Science or Data Processing, the items sorted by sorting algorithms are usually data, files or arrays.
It is not always possible to say that one algorithm is better than another, as relative performance can vary depending on the type of data being sorted. In some situations, most of the data are in the correct order, with only a few items needing to be sorted. In other situations the data are completely mixed up in a random order and in others the data will tend to be in reverse order. Different algorithms will perform differently according to the data being sorted.
Eg: When using advanced search for a particular query,search engine will use a sorting algorithm to rank its results.
There are many types of sorting algorithms used, below mentioned are some examples and comparisons of the Sorting Algorithms.
Sorting Categories
- Sorting by Exchange – bubble sort, quicksort
- Sorting by Insertion – insertion sort, shellsort
- Sorting by Selection – selection sort, heapsort
- Sorting by Merging – merge sort
- Sorting by Distribution – radix sort
Complexity of Sorting Algorithms
The complexity of a sorting algorithm measures the running time as a function of n, the number of records sorted. The following are the fundamental operations that take place during sorting:
1.Comparison of two keys
2.Interchange of records
3.Assignment of a record to a temporary location
Normally, the complexity function measures only the number of comparisons, since the number of other operations is almost a constant factor of the number of comparisons.
Types of Sorting Algorithms
Bubble Sort
Bubble Sort works by comparing each element of the list with the element next to it and swapping them if required. With each pass, the largest of the list is “bubbled” to the end of the list whereas the smaller values sink to the bottom. It is similar to selection sort although not as straight forward. Instead of “selecting” maximum values, they are bubbled to a part of the list. A single, complete “bubble step” is the step in which a maximum element is bubbled to its correct position. This is handled by the inner for loop.
Examine the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)
8 6 10 3 1 2 5 4 } pass 0
6 8 3 1 2 5 4 10 } pass 1
6 3 1 2 5 4 8 10 } pass 2
3 1 2 5 4 6 8 10 } pass 3
1 2 3 4 5 6 8 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7
The above tabulated clearly depicts how each bubble sort works. Note that each pass results in one number being bubbled to the end of the list.
Selection Sort
The idea of Selection Sort is rather simple. It basically determines the minimum (or maximum) of the list and swaps it with the element at the index where its supposed to be. The process is repeated such that the nth minimum (or maximum) element is swapped with the element at the n-1th index of the list.
Consider the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)
8 6 10 3 1 2 5 4 } pass 0
1 6 10 3 8 2 5 4 } pass 1
1 2 10 3 8 6 5 4 } pass 2
1 2 3 10 8 6 5 4 } pass 3
1 2 3 4 8 6 5 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7
At pass 0, the list is unordered. Following that is pass 1, in which the minimum element 1 is selected and swapped with the element 8, at the lowest index 0. In pass 2, however, only the sublist is considered, excluding the element 1. So element 2, is swapped with element 6, in the 2nd lowest index position. This process continues till the sub list is narrowed down to just one element at the highest index (which is its right position).
Insertion Sort
The Insertion Sort algorithm is a commonly used algorithm. Even if you haven’t been a programmer or a student of computer science, you may have used this algorithm. Try recalling how you sort a deck of cards. You start from the beginning, traverse through the cards and as you find cards misplaced by precedence you remove them and insert them back into the right position. Eventually what you have is a sorted deck of cards. The same idea is applied in the Insertion Sort algorithm.
Examine the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)
8 6 10 3 1 2 5 4 } pass 0
6 8 10 3 1 2 5 4 } pass 1
6 8 10 3 1 2 5 4 } pass 2
3 6 8 10 1 2 5 4 } pass 3
1 3 6 8 10 2 5 4 } pass 4
1 2 3 6 8 10 5 4 } pass 5
1 2 3 5 6 8 10 4 } pass 6
1 2 3 4 5 6 8 10 } pass 7
The pass 0 is only to show the state of the unsorted array before it is given to the loop for sorting. Now try out the deck-of-cards-sorting algorithm with this list and see if it matches with the tabulated data. For example, you start from 8 and the next card you see is 6. Hence you remove 6 from its current position and “insert” it back to the top. That constitued pass 1. Repeat the same process and you’ll do the same thing for 3 which is inserted at the top. Observe in pass 5 that 2 is moved from position 5 to position 1 since its < (6,8,10) but > 1. As you carry on till you reach the end of the list you’ll find that the list has been sorted.
Shell Sort
It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort. Although this method is inefficient for large data sets, it is one of the fastest algorithms for sorting small numbers of elements (sets with fewer than 1000 or so elements). Another advantage of this algorithm is that it requires relatively small amounts of memory.
Visualize Shell sort in the following way: arrange the list into a table and sort the columns (using an insertion sort. Repeat this process, each time with smaller number of longer columns. At the end, the table has only one column. While transforming the list into a table makes it easier to visualize, the algorithm itself does its sorting in-place (by incrementing the index by the step size, i.e. using i += step_size instead of i++).
For example, consider a list of numbers like [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. If we started with a step-size of 5, we could visualize this as breaking the list of numbers into a table with 5 columns. This would look like this:
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
We then sort each column, which gives us
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
When read back as a single list of numbers, we get [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Here, the 10 which was all the way at the end, has moved all the way to the beginning. This list is then again sorted using a 3-gap sort, and then 1-gap sort (simple insertion sort).
Merge Sort
Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4…) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list.
Merge sort incorporates two main ideas to improve its runtime:
A small list will take fewer steps to sort than a large list. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they’re already sorted (see the merge function below for an example implementation).
Bubble Sorting
Advantages
- Fairly easy to understand in terms of sorting algorithms
- Fairly easy to write(i.e. about 5 lines of code)
Disadvantages
- Relatively slow algorithm
- i.e takes O(n^2) to complete sorting
Insertion Sorting
Advantages
- Takes into account elements of the list which are already sorted
- Hence, work quite well for a partially sorted list
Disadvantages
- Still a relatively slow algorithm
- Especially so if the starting list is in reverse order
Selection Sorting
Advantages
- Easy to understand
- Hence, easy to implement
Disadvantages
- Unable to recognise parts of the partially sorted list
- Works only on the unsorted parts
- Method uses internal sorting(i.e. requires entire array to be in memory – sometimes large amounts of memory)
Criterias to Classification of Sorting Algorithms
- Computational complexity of elements sizes – Based on element size on the list(n), can be worst, average or best. Good comparisons are O(n log n) while bad is O(n2))
- Computational complexity of swaps – Based on “in place” algorithms
- Memory Usage and usage of other computer resources – Example: One large class of algorithm is “in-place” sorting which is slower than algorithm which uses additional memory
- Stablity – Stable sorting algorithm maintains relative orders of records with equal keys as all different keys will deem this distinction useless
- Recursion – Recursive, Non Recursive or Both
- Comparsion Sort Nature – Have or Do Not Have
- General methods – Exchange(i.e. bubble sort), selection (i.e heapsort), merging, etc…
- Behaviours on important data sets – Whether it’s completely sorted, inversely sorted & almost sorted
Sample Code
The following function used in C++:
inline int swap( int &x;, int &y; ) {
int z = x;
x = y;
y = z;
}
References
Sorting Animation, http://www.google.com.sg/search?hl=en&q;=define%3A+algorithm&btnG;=Google+Search&meta;=
Sorting Algorithm Introduction, http://webspace.ship.edu/cawell/Sorting/main.htm
Sorting Algorithms, http://homepages.north.londonmet.ac.uk/~chalkp/proj/algtutor/sortingal.html
Sorting Algorithm Comparison, http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html
Stable SA, http://planetmath.org/encyclopedia/StableSortingAlgorithm.html
http://www.cogx.com/cogx/ctw/algorithms/default.html
http://linux.wku.edu/~lamonml/algor/sort/sort.html
http://www.ics.uci.edu/~eppstein/161/960116.html
http://atschool.eduweb.co.uk/mbaker/sorts.htm
http://sig9.com/articles/sorting-algorithms
