Last updated on September 4th, 2023 at 09:47 pm
Here, We will learn about sorting algorithms, why is sorting necessary, classification and complexity of sorting, types of sort.
What is Sorting?
Sorting refers to arranging data in a particular format.
Sorting Algorithm is an algorithm that arranges the elements in a certain order [either ascending or descending]. The output is reordering of the input.
Most common order are numerical or lexicographical order.
Example of Sorting in real life scenarios are following:
- Telephone Directory – keeps telephone number of people sorted on their names. So, those names can be searched easily.
- Dictionary – Keeps words in alphabetical order so that searching for any word becomes easy.
Why is Sorting Necessary?
Sorting optimized the data searching to a high level if the data is stored in a sorted manner. It is also used to represent data in more readable formats.
It can reduce the complexity of a problem and is often used for database algorithms and searches.
Classifications of Sorting Algorithms
Sorting algorithms are generally categorized based on the following parameter:
- Number of Comparisons – For comparison-based sorting algorithms, best case behaviour is O(n log n) and worst-case behaviour is O(n2).
- Number of Swaps – categorized based on the number of swaps (also called inversions)
- Memory Usage – O(1) for in-place sorting or O(log n) memory to create auxiliary locations for sorting the data temporarily.
- Recursion – recursive (quick sort) or non-recursive (selection sort, insertion sort) and both (merge sort).
- Stability – maintain the relative order of elements with equal keys.
- Adaptability – complexity changes based on pre-sortedness (quick sort). Algorithms that take into account are known to be adaptive.
In-place and Not-in-place Sorting
Sorting algorithm may require some extra space for comparison and temporary storage of a few data elements.
Those algorithms do not require any extra space for sorting is called in-place sorting. Bubble sort is an example.
The algorithm which requires extra space for sorting is called not-in-place sorting. Merge sort is an example.
Stable and Not Stable Sorting
In a sorting algorithm, after sorting the elements, does not change the sequence of similar elements in which they appear, it is called Stable Sorting.
In a sorting algorithm, after sorting the elements, change the sequence of similar elements in which they appear, it is called Unstable Sorting.
Types of Sort
Time and Space Complexity
Related:
Want to Contribute:-
If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎