What is sorting?
Sorting is an algorithm that arranges the elements of a list in a certain order (either ascending or descending, as per the requirement). The output is simply a permutation of the input data.
Why sorting?
Sorting is one of the most important categories of algorithms in computer science. Sometimes sorting significantly reduces the problem complexity. We can use sorting as a technique to reduce the search complexity. Great research went into this category of algorithms because of its importance. These algorithms are very much used in many computer algorithms [for example searching algorithms, database algorithms etc].
Classification
Sorting algorithms are generally classified into different categories based on these parameters:-
- By Number of comparisons:- In this method, sorting algorithms are classified based on the number of comparisons. For comparison based sorting algorithms, best case behavior is O(nlogn) ad worst case is O(n2). Comparison based algorithms evaluate the elements of the list by key comparison operation and needs at-least O(nlogn) comparisons for most inputs.
- By Memory Usage:- Some algorithms are “in place” and they need O(1) or O(logn) memory to create auxiliary locations for sorting the data temporarily.
- By Recursion:- Sorting algorithms are either recursive [Quick sort] or non-recursive [Selection sort, insertion sort]. There are some algorithms which use both [Merge sort].
- By Stability:- Sorting algorithm is stable if for all indices i and j such that the key A[i] equals A[j], if record R[i] precedes record R[j] in the original file, record R[i] precedes R[j] in the sorted list. Few sorting algorithms maintain the relative order of elements with equal keys. In other words we can say that the equivalent elements retain their relative positions even after sorting.
- Internal Sort:- Sorting algorithms which use main memory exclusively during the sort are called Internal Sorting algorithms. This kind of algorithms assumes high-speed random access to all the memory.
- External Sort:- Sorting algorithms which uses external memory, such as a tape or disk.
Types of DATA
Apart from the above discussed classification, we have different types of data also upon which we need to apply sorting algorithms. Depending upon the type of data we need to choose a time efficient algorithm. In such a case some before hand knowledge of the data comes handy. Different types of data can be:-
- Random:- This is totally random data and the most typical case. The data is generally assumed to be in this form and most of the algorithms are designed considering this as the general case.
Eg:- 1, 9, 15, 3, 99, 5, 123, 6, 23, 34, 76 is an example of random data. The numbers are neither arranged in ascending order or descending order. - Nearly Sorted:- This is a special case, where the data we obtain is nearly sorted and only 1-2 elements out of 20 are out of place. By 1-2 it means that 10% of the data is out of place.
Eg:- 1, 3, 2, 5, 6, 8, 10, 9, 12, 14, 16, 15, 19, 20 is an example of nearly sorted data. - Reversed:- This is a special case, in which we receive the data in a way that is completely opposite to the required result. Only some algorithms like Quick Sort are designed to efficiently sort this data.
Eg:- 10, 9 , 8, 7, 6, 5, 4, 3, 2, 1 if we need the output in ascending order, then this is a reversed case. - Unique cases:- There are very specific cases, which consist of elements that occur more than once.
Eg:- 1, 1, 1, 1, 1, 10, 3, 10, 1, 10, 3, 3, 10, 3, 1, 10, 10, 10, 3, 3, 1, 1 is an example of unique case, since there are only 3 distinct numbers but they occur more than once.
Considering these cases, we will try to analyze the following algorithms:-
A good interpretation of the running times of these sorts can be found here.
Linear Sorting Algorithms:-
The above examples are based on comparisons. Among all of them, the best was O(n log(n)). There are also some linear sorting algorithms that can sort in O(n) based on given assumptions of input data. Some of them are:-