DSA by Mitul in C++, Python, and Java : Sorting Algorithms
Tags: algorithms, dsa, sort
Published: 2022-10-25 09:00:03

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.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4g998u7d9rwvvmgwkrts.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gmqao7uq9w2wivgt6ns7.png)
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 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3drx1xnr9897kwp68bac.png)
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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3c4fw8luac1my3wjq8n2.png)
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.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qopvrw9v2hmionh68ec1.png)
1. Space : This is  divided into 2 parts. One is 
In place : Algorithms which does not need any extra space.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jjfqqavb8tkfxz1liwxx.png)
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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ve27brrk5zgo1q8l6jf2.png)
Here, this sort needs an extra space . This is an example of Merger sort.

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3otazz4kvp50hmvx7r1d.png)

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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qfcj7xi081f8wy8r6vlr.png)
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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oyf9bvfu0la5ixe215qj.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ut6pv637vw08gz6m4tjs.png)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1xxp85lldu5yqd14kj5l.png)

Here you can see every elements bigger than previous one.

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3wut6stim9cnbaisxxgw.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2ae4a8ds6r6t4s9c5qae.png)

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

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s67eodo6j3amo6wtnxp5.png)
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.