Sorting- A brief introduction

What is Sorting?

Sorting is an algorithm that arranges the elements of a collection in a certain order either in ascending or descending order. After applying the sorting algorithm the output that we get is an ordered format of input elements.

There are several sorting algorithm techniques like selection sort, insertion sort, merge sort, and many more.

For example, You have a large number of employees and you have to order them in increasing order on the basis of their age.

Why is Sorting Necessary?

In Computer science, sorting is one of the most important categories of algorithms and a lot of research has gone into this category. Using proper sorting can significantly reduce the complexity of a problem, and is often used for databases, algorithms, and searches.

Classification of Sorting algorithms:

The sorting algorithm is generally categorized on the basis of the following parameters:

1. By Number of comparisons

In this parameter, sorting algorithms are classified based on the number of comparisons. For comparison-based sorting algorithms, best case behavior is O(n log n) and worst-case behavior is O(n²). Comparision based sorting algorithms evaluate the elements of the list by key comparison operation and need at least O(N log N) comparisons for most inputs.

2. By number of swaps

In this parameter, sorting algorithms are categorized on the basis of the number of swaps i.e. inversions.

3. By memory usage

Some sorting algorithms are “in place” and they need O(1) or O(log n) memory to create auxiliary locations for sorting the data temporarily.

4. By recursion

Sorting algorithms can be either recursive or non-recursive. In few cases, they can be both. Like quick sort, the algorithm is recursive and the selection sort is non-recursive but at the same time merge sort uses both recursive and non-recursive as well.

5. By Stability

The sorting algorithm is stable if for all indices i and j such that A[i] equals key A[j] if record R[i] precedes record R[j] in the original file, record R[j] in the sorted list. Few sorting algorithms maintain the relative order of elements with equal keys(equivalent elements retain their positions even after sorting).

6. By Adaptability

In the few Sorting algorithms, Pre-sortness of the input affects the running time of the algorithm. That means complexity changes based on pre-sortedness. Algorithms that follow the pre-sortedness are known as adaptive algorithms. Example- Quicksort.

7.Internal Sort

In the Internal sorting algorithm, during the sorting process, the main memory is used exclusively and the algorithm assumes high-speed random access to the memory. This type of sorting is called internal Sorting.

8. External Sort

In External sorting, during the sort, external memory devices are used such as a disk, tape, or any other external storage devices.

List of Sorting Algorithms:

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Shell Sort
5. Merge Sort
6. Heap Sort
7. Quick Sort
8. Tree Sort
9. Bucket Sort
10. Radix Sort
11. Topological Sort
12. External Sorting