Sorting Techniques and Time Complexity | DSA Tutorials

Sorting Introduction – Sorting refers to arranging some set of elements (i.e. either numbers, strings or any alphabet) in ascending (increasing) or descending order. Some of the most commonly used sorting methods are: Bubble sort, Heap sort, Insertion sort, Merge sort, Quick sort, Selection sort, Shell sort, Counting sort, bucket sort, and Radix sort. Choosing the right sorting algorithm depends on the time complexity of that algorithm.

The main task involved in sorting is basically comparison and interchanging the position of elements, but there are sorting methods that employ techniques other than comparisons for sorting purposes. The common sorting algorithms can be divided into two classes by the complexity of their algorithms. Algorithmic complexity is generally written in a form known as Big-) notation, where the O represents the complexity of the algorithm and a value n represents the size of the set against which the algorithm is run.

Algorithm complexity is a complex subject that we have studied in our previous tutorial – Time complexity of algorithms. We have seen that there’s a direct correlation between the complexity of an algorithm and its relative efficiency. The two classes of sorting algorithms are O(n²), which includes the bubble, insertion, selection, and shell sorts; and O(n log n), which includes the heap, merge and quick sorts. There are other sorting algorithms like counting, radix and bucket sort that run in linear time under particular conditions.

Problem Definition: Given a list of data elements (a₁, a₂, a₃,… a_n), which can be arranged in n! ways, we can define sorting for the set of elements in a list by taking one permutation (a_k1,a_k2,a_k3,……a_kn), such that a_ki,a_kj where i<j.

Let A be a list of n elements A₁, A₂,…, A_n in memory. Sorting A refers to the operation of rearranging the contents of A so that they are increasing in order (numerically or lexicographically), that is, so that

A₁ <= A₂ <= A₃ <= … <= A_n

Since A has n elements, there are n! ways that the contents can appear in A. These ways correspond precisely to the n! permutations of 1,2, …, n. Accordingly, each sorting algorithm must take care of these n! possibilities.

Time Complexity of Sorting Algorithms

The time complexity of a sorting algorithm measures the running time as a function of the number n of items to be sorted. We note that each sorting algorithm S will be made up of the following operations, where A₁, A₂, …, A_n contain the items to be sorted, and B is an auxiliary location:

1. Comparisons, which test whether A_i < A_j or test whether A_i < B.
2. Interchanges, which switch the contents of A_i and A_j or of A_i and B.
3. Assignments, which set B:= A_i and then set A_j:= B or A_j:= A_i.

Normally, the complexity function measures only the number of comparisons, since the number of other operations is at most a constant factor of the number of comparisons. There are two main cases whose complexity we will consider: the worst case and the average case. In studying the average case, we make the probabilistic assumption that all the n! permutations.

Here is the table of the complexity of various sorting algorithms.

Classification of Sorting Techniques

1. Internal Sorting: In this, no communication with secondary memory is required during the sorting process; this means a fast sorting operation. It refers to the sorting operation performed over a list that is stored in primary memory. This is so because all operations can be done within the memory, that is, internally. The complete data (list of elements) and the program (which implements the algorithm) reside in the memory. The result is also stored in the main memory. The time requires reading or write not considered to be significant in evaluating the performance of the internal sorting method. It is applied when the entire collection of data to be sorted is small enough that the sorting takes place within main memory.
2. External Sorting: External sorting refers to the sorting operation performed when a list, stored in a file, is accommodated in secondary memory (for instance, hard disks). For actual sorting purposes, a small portion of data may be copied into main memory, but complete data never resides in the main memory. Due to copying in and copying out data to and from the secondary storage device, external sorting is a time-consuming process. External sorting is required when the data being sorted does not fit into the main memory of a computing device (usually RAM) and a slower kind of memory.
3. Stable Sorting: A sorting algorithm is said to be stable if it does not exchange the relative positions of items with equal keys. More formally, a sorting algorithm is stable if, for any two elements a and b with equal keys, a precedes b after the sorting if and only if a precedes b before the sorting. Stable sorting algorithms maintain the relative order of records with equal keys (i.e., sort key values). Bubble sort and merge sort are examples of stable sorting.
4. Comparison-Based Sorting: A sorting algorithm is called comparison-based if the logic of the sorting consists of a comparison operation between two elements. The comparison is made between the keys, which can be either the data element itself or any other value associated with it. Such algorithms determine the relative order of any two elements a_i and a_j by performing one of the following tests: a_i < a_j, a_i > a_j, a_i = a_j, a_i <= a_j, a_i >= a_j. For instance, insertion sort, merge sort, heap sort, and quick sort are all comparison sorts because at some step they determine the place of an element by comparing it with other elements. Some of the most well-known sorting algorithms that are comparison-based are quick sort, Heap sort, Insertion sort, Bubble sort, Selection sort, Shell sort, Merge sort, etc.
5. In-place Sorting: In-place sorting refers to sorting methods that do not use any additional space for the storage of input data elements, i.e. sorting is done by rearranging the elements within the input array itself. Actually, in-place sorting algorithms are a type of in-place algorithm, which transforms a data structure using a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm that is not in-place is sometimes called not-in-place or out-of-place. Examples of sorting algorithms that are in-place are: Selection, Insertion, Heap, Shell, bubble sort, etc. Quick Sort is commonly described as an in-place algorithm.
6. Non-Comparison-Based Sorting: It uses any property of the element itself to organise the list. A non-comparison sorting method sorts data by means other than comparing two elements. Examples of such sorting methods are counting sort, radix sort and bucket sort.