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

Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C, time and space complexity and advantages.. What is Insertion sort? Insertion Sort …
Read More

Heap Sort

Here, We will discuss about Heap Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What …
Read More

Bucket Sort

Here, We will discuss about Bucket Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. …
Read More

Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Quick Sort? Quick …
Read More

Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C, time and space complexity and their advantages. What is Selection Sort? Selection …
Read More

Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Bubble Sort? Bubble Sort …
Read More

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders.

Leave a Comment

Your email address will not be published. Required fields are marked *