In computer science, sorting algorithm is used to arrange data in specific order. This data could be in any form, may be numeric, character, string or a large record.
Sorting is a process of arranging elements in a certain order. Numeric data may be sorted in ascending or descending order. Alphabets or strings may be sorted in lexicographical order.
There are several items in our daily lives that we must search for, such as a certain record in a database, roll numbers in a merit list, a specific telephone number in a telephone directory, a specific page in a book, and so on. All of this would have been a disaster if the data had remained unorganized and unsorted, but thankfully, the notion of sorting evolved, making it simpler for everyone to place data in an order, making it easier to search.
Why Are Sorting Algorithms Important?
Sorting is a topic that has been extensively researched and investigated in the field of computer science. Sorting is a fundamental need in many applications.
Sorting data makes it easier to search through a given data sample, efficiently and quickly.
A quick Google search indicates that approximately 40 distinct sorting algorithms are now in use in the computing industry.
For sorting, there is a large class of algorithms available. All have limitations and are limited to a certain application domain. There is no algorithm that can fulfill all objectives. However, the most often used measure for selecting the optimal algorithm is running time.
Categories of Sorting
The techniques of sorting can be divided into two categories. These are:
- Internal sorting
- External sorting
If numbers of elements are small enough to sort in main memory, sorting is called internal sorting.
If numbers of elements are large such that some of them reside on external storage during the sorting procedure, it is called external sorting.
Properties of Sorting Algorithm
Following are the properties of sorting algorithms:
- In place : Only require constant additional space to sort the algorithm. Sometimes O(log n) space is allowed.
- Stable: Does not alter the relative position of same elements after sorting
- Online: Sort the data as it arrives
- Adaptive: Performance of algorithm varies with the input sequence
- Incremental: Build sorted sequence one number at a time
Complexity of Sorting Algorithm
The complexity of a sorting algorithm measures the running time of a function with ‘n’ items to sort. The decision of which sorting technique is appropriate for a problem is determined by several dependency configurations for various problems. The following are the most important considerations:
- The amount of time taken by a programmer in developing a certain sorting program.
- The amount of machine time required to run the program
- The amount of memory required to run the program
Efficiency of Sorting Algorithm
The complexity of algorithm is determined based on how many comparison it does to sort given data. Sorting algorithms are sensitive to arrangement of input data.
Algorithms are analyzed based on following cases:
- Best case
- Worst case
- Average case
Types of Sorting Algorithm
Comparison Based Sorting:
In comparison based sorting methods, data are sorted by comparing two data elements. The comparator function is defined to compare and sort the data. Example: Selection sort, Bubble sort, Insertion sort
Counting Based Sorting:
These sorting algorithms make no comparisons between elements and instead rely on calculated assumptions during execution. Example: Radix sort, Bucket Sort, Counting sort
In-place vs Not in-place Sorting:
In data structures, in-place sorting algorithms change the ordering of array items within the original array. Not-in-Place sorting methods, on the other hand, sort the original array using an auxiliary data structure.
Examples of in-place algorithms are Quick sort, Insertion sort, Selection sort
Examples of not in-place algorithm is Merge sort
Some Popular Sorting Algorithms
Following are the few popular sorting algorithms used in computer science:
- Bubble sort
- Selection sort
- Insertion sort
- Heap sort
- Merge sort
- Quick sort
- Counting sort
- Radix sort
- Bucket sort
Additional Reading: Comparison of adaptive algorithms