DSA by Mitul in C++, Python, and Java : Sorting Algorithms

Sorting means organize some particular things depending on a measurement.
For example,
If we have 5 pictures of a lady but in different sizes, it might not be easy to get a the 2nd largest picture or 3rd largest picture easily if we don't sort it. Why?

Because every time we will have to search from the beginning and then decide which is the largest and then 2nd largest and 3rd largest.

To solve this issue, we can simply sort the pictures depending on height .

Now look, it is easy to choose the 2nd largest or, 3rd largest picture easily and it will not be that time consuming to detect that, right?

Practical usages of Sorting algorithms

Sorting is used in Microsoft Excel

Look at this sort function used in excel.

Also when you go to amazon or any other website, you can easily sort products based on prizes.

Here, from the website of Startech, you can see the option to sort. You can set this default option to price(low->high) or prince(high->low).

I hope you understood how sorting is used in real life.

Types of Sorting Algorithms

Sort is divided into 2 parts , depending on Space and Stability.

1. Space : This is divided into 2 parts. One is In place : Algorithms which does not need any extra space.

Here you can see that you don't need any extra space to sort this one. It is an example of Bubble sort.

Second one is
Out Place : An algorithm which needs more space than provided.

Here, this sort needs an extra space . This is an example of Merger sort.

1. Stability : This one is divided into Stable and Unstable sort Stable: If a sorting algorithm after sorting the contents does not change the sequence of similar content in which they appear, then it is Stable sort.

For example, here you have an array with two 40

We have assigned the 1st 40 as green colored and 2nd one as red colored.

Now, after sorting it , if the green one is before the red one, it is stable.

Let's check it:

You can see the sequence is as same as before the sorting, right? This is done in insertion sort.

Unstable sort: If the sequence changes, it is unstable.

Here the red colored 40 came before green colored. Thus the sequence changed.

This is done in Quick sort.
Here is a real life example of sorting data in excel

You can see data sorted based on name, based on age (stable: Did not change the sequence ), based on age (unstable: did change the sequence)

Some important terminologies for sorting

1. Increasing order: If a particular element is bigger than the previous one.

Here you can see every elements bigger than previous one.

1. Decreasing order: If a particular element is less than the previous one.

1. Non increasing order: If a particular element is less than previous one or equal.

Here you can find 11 bigger than 9 and also 5 is equal to 5.

1. Non Decreasing Order: If an element is bigger than the previous element or equal.

Here 7 is equal to 7 and 11 is bigger than 9.

Sorting Algorithms

There are bunch of sorting algorithms but why should we learn those?

Because every sorting algorithms has their pros and cons.

Depending on stability, space efficiency & time efficiency we choose a desired sorting algorithm.