Sorting Algorithms

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.😎