One of the fundamental problems of computer science is ordering a list of items. There are several solutions to this problem, known as sorting algorithms.
Sorting is a process that organizes a collection of data into either ascending or descending order.
Much of the time, we want to sort numbers into numerical order. But we also sort
- names and words
- dates, written in different forms
- complex, multi-field data
The importance of Sorting
Sorting is one of computer science’s most essential operations in real-life data processing. For this reason, it has been very intensively studied since the half of the 20th century and is currently regarded as a well-studied problem in computer science.
Examples of critical applications of sorting
- Acceleration of searching
- Acceleration of operations on relations “by key,” etc. (e.g., in the database)
- Data visualization
- Computing many important statistical characteristics.
Classification of Sorting algorithms
Sorting algorithms can be classified based on many factors.
Classification based on complexity
The algorithmic complexity of different sorting algorithms varies depending on best, worst, and average-case behavior in terms of the data list size. The common sorting algorithms can be divided into two classes by the complexity of their algorithms.
- Algorithms with complexity O(n²) include bubble sort, selection sort, and shell sort.
- Algorithm with complexity O(n): This includes the heap sort, merge sort, and quick sort.
Classification based on Memory
Sorting algorithms can be classified into the following types.
- Internal sort: Some algorithms sort by swapping elements within the input array. All data items are held in the main memory; no secondary memory is required for this sorting process. There is a limitation to internal sorts; they can only process a relatively small list due to memory constraints. Examples of the internal sort are selection, insertion, and exchange.
- External sort: Sorting large amounts of data requires external or secondary memory. This process uses external memory, such as HDD, to store the data which does not fit into the main memory. All external sorts are based on the process of merging, i.e., different parts of data are sorted separately and merged. Merge sort is one of the external sort algorithms.
Adaptive and non-adaptive sorting algorithms
Sorting algorithms can be adaptive or non-adaptive depending on whether the pre-sortedness of the input list affects or does not affect the running time.
- Adaptive algorithms: A sorting algorithm is said to be adaptive if it takes advantage of already sorted elements in the list that is to be sorted. That is, while sorting if the source list has some element already sorted, adaptive algorithms will consider this and try not to re-order them. Examples quick sort, stranded sort
- Non-adaptive algorithm: A non-adaptive algorithm does not consider the elements that are already sorted. They try to force every single element to be re-ordered to confirm their sortedness. Examples: Selection sort, Merge sort, heap sort.
Recursive and Iterative sorting algorithms
Sorting algorithms can be implemented as recursive and non-recursive (iterative) algorithms or both.
- Recursive sorting algorithms: Recursive sorting algorithms work by splitting the input array into two or smaller subarrays and then sorting those sub-arrays; it then combines the sorted subarrays into a sorted output array. Examples are merge sort and quick sort.
- Iterative sorting algorithms: A non-recursive (iterative) algorithm does the sorting all at once by using iterative statements/repetitive statements/loops only, without calling itself repeatedly. Bubblesort is an example of a non-recursive algorithm. Examples are bubble sort, selection sort, and quick sort.
List of Sorting Algorithms
Some of the most common sorting algorithms are
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
- Merge sort
- Heap sort
- Quick sort
- Tree sort
- Bucket sort
- Radix sort