In this lesson and in this series of lessons

we are going to talk about sorting algorithms. Sorting as a concept is deeply embedded in

a lot of things that we do. It’s quite often that we like to arrange things or data in

certain order. Sometimes to improve the readability of that data, at others to be able to search

or extract some information quickly out of that data. For example, something as simple

as, when we are playing a card game, even though the number of cards in our hand is

really less, we like to keep our hand of cards sorted by rank or suit. So, let’s say, this

is our hand of cards and we would like to keep it in increasing order of rank, then

the arrangement will be something like this. Now, have a look at this, when we go to a

travel site to book a hotel ,then the site gives us all these options of sorting the

hotels by price from low to high or by star rating or by guest rating. So, right now I

have my option sorted by guest rating, So, the hotel with the highest guest rating is

at the top. I may be on a budget and I may want to avail the cheapest option. So, I would

sort the hotels by price from low to high and now, the cheapest hotel will be at the

top. And, I may still try to strike a balance between rating and price. So, sorting is a

really helpful feature here and there are so many places where we like to keep our data

sorted. Be it the language dictionary where we want to keep the words sorted so that searching

a word in the dictionary is easy or something like a medal tally where we want to know to

see team is at the top and which team is not performing so well! If we want to define sorting

formally, then sorting is arranging the elements in a list or collection in increasing or decreasing

order of some property. The list should be homogeneous, that is all the elements in the

list should be of same type. To study sorting, to study sorting algorithms, most of the times

we use a list of integers, and typically we sort the list of integers in increasing order

of value. So, if we have a list of integers like this, 2,3,9,4,6 then sorting it in increasing

order of value, will mean rearranging the elements like this. Sorting the list in decreasing

order of value will mean something like this, and as we have said in the definition , we

can sort on any property! What if we want to sort this list on the basis of let’s say,

increasing number of factors. So, the number with lesser number of factors is towards the

beginning of the list. If you see, 2 has got only 2 factors, 1 and 2 itself. 3 has also

got 2 factors, 1 and 3 itself. 9 has got three factors, 1, 3 and 9 itself. 4 has got 3 factors,

1, 2 and 4 itself. 6 has got 4 factors, 1,2,3 and 6 itself. A sorted list is the permutation

of the original list, When we sort a list, we just rearrange the elements. Now this was

a list of integers. We may have a list of any data type. We may want to sort a list

of strings or words in lexicographical order, the order in which they will occur in dictionary.

A list of strings like this in lexicographical order will be arranged in this order. And

we may have a list of complex data type as well. A hotel object in the Hotel list, that

we had seen earlier, was a complex type. Hotel will have many properties, like it’s price,

it’s distance from the city center. guest rating, it’s star rating and the list can

be sorted on any of these properties. Sorted data is good, not just for presentation or

manual retrieval of information, even when we are using computational power of machines,

sorted data is really helpful. If a list is stored in computer’s memory as unsorted, then

to search something in this list, we will have to run Linear Search. In linear search,

we start with the first element of the list and keep scanning the whole list, until we

get the element that we are looking for, so, in the worst case when an element will not

be there in the list, we will compare it with all the elements in the list, we will scan

it with whole list. So, if there are n elements in the list, we will make n comparisons in

the worst case. And, think about the kind of data, modern day computers deal with. If

this n is really large, if we take n=2 to the power 64, and imagine that 1 comparison

takes 1 milli second, then we will take 2 to the power 64 milli seconds. If you try

to convert this to seconds, hours, days and so on, this will amount to some years. If

our list however is sorted, we can us something called binary search, and with binary search

it the size of the list is n, it will take only log of n to the base 2 comparisons to

perform a search. So, if n is equal to 2 to the power 64, we will take only 64 milliseconds.

I had taken n equal 2 to the power 64 earlier, to be able to perform this log quickly. Sorting

as a problem is well studied and a great deal of research has gone into devising efficient

algorithms for sorting. In this series of lessons we are going to study, analyze, and

compare these sorting algorithms. Some of the sorting algorithms that we will be talking

about, that we will be analyzing about are Bubble Sort, Selection sort, Insertion Sort,

Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort and this is not all. There

are more. And, you can imagine how important sorting as a problem is. We have so many algorithms

for sorting that have been designed over a period of time. We often classify sorting

algorithms based on some parameters. The first parameter that we want to classify upon is

time complexity which is the measure of rate of growth of time taken by an algorithm with

respect to input size. Some algorithms will be relatively faster than others. The second

parameter that we use for classification is space complexity or memory usage. Some sorting

algorithms are in place, they use constant amount of extra memory to rearrange the elements

in the list, while some sorting algorithms like merge sort, use extra memory to temporarily

store data and the memory usage grows with input size. The third parameter that we talk

about is stability and this one will take some explanation. Suppose we have a set of

cards like this, and we want to sort these cards in increasing order of rank. We have

one 3 of Diamond, we have one 9 of Spade, and we have two 6’s, one of club and another

of heart. One possible permutation will be this, the cards are sorted by rank,we have

got 3,6,6,9. But if you see, in the original list, 6 of Club was coming earlier than 6

of Hearts. But, when we have this permutation which is a sorted arrangement, 6 of hearts,

this particular card, has come before 6 of clubs. A stable sorting algorithm in the case

of equality of key, or the property upon which we are sorting, preserves the relative order

of elements. So, if the key is equal, if an element was coming before in the original

list, it will also come before in the sorted list. A stable sorting algorithm guarantees

that. So, if we will use stable sorting algorithm , we will get this particular permutation.

6 of club will be before 6 of hearts. The next parameter of classification is whether

a sort is internal sort or external sort. When all the records that need to be sorted

in the main memory or RAM, then such sort is internal sort and if the records are on

auxiliary storage like disk and tapes, quite often because it’s not possible to get all

of them in the main memory in one go, then we call such a sort external sort. There is

one more parameter upon which we may classify sorting algorithms, and it is whether algorithm

is recursive or non recursive. Some sorting algorithms like Quick Sort and Merge Sort

are recursive while other like Insertion Sort and Selection sort are non-recursive. We will

study all these properties in detail as we will study these individual algorithms. This

is it for a basic introduction, Thanks for watching!

You explain very well..please do post remaining sorting algorithms..thanks 🙂

Thanks Shaan,

We will be uploading the rest soon. Please stay tuned 🙂

Funny; I downloaded these lectures to watch in two times the speed; and because there are no numbers in the title – I needed to sort the lectures in the playlist. And because I didn't watch the videos yet – I didn't know how to do that the most efficiently. X-D

awesome teaching

best sorting video

I am a huge fan of yours now! Awe sum Channel, Brilliant Teacher, Excellent Teaching Methodology!! Great Work sir!! Expecting More from you. 🙂

Hey thank you for your video. Its is best in youtube you explanation is awesome. I am searching here sorting in order to factor. I did not find any link for that. Please advise to me. Thanks

Please update heapsort to sorting algorithm list. Thanks

Trying understand topological sorting , it would be really great to see in your tutorial . 🙂

Thanks sir…

omg,where did you get this much of information on data

american eats too many words while talking…..there are very few american with good tutorials like Bucky(TheNewBoston) …..i hate that accent

but you teach very well…..talks clearly, explains everything with examples, subscribed 🙂

please post some videos of ANSI C

I learned a lot more from your videos than the class. Thank you a lot, Sir.

plzz upload heap sort also.u teach in an excellent manner. i love your lectures

PLEASE ALSO ADD RADIX SORT!

Best explanation ever…thank you sir 🙂

thanks you very much

sir please upload all d possible videos on datas structure…….this is the best teaching website i got to know till now..just amazing sir..n i give all my gratitude to ur efforts,…..thanks a lot sir.please do d favour as soon as possible.

how many sorting algorithm are there ?

plz upload heap sort..

nice video good explanation..thx …….but ur "Hurt" really hurts to listen….

Nicely Explained 🙂

does anyone have any idea about what lexicographic sorting is? and how to implement it in Matlab

simply awesome!!!!!!

Awesome. Thank you!!!!!

Sir, Really this tutorial is very nice.Thank You.

please upload a series on hashing. It is also not there in your website.

Your videos/explanations are fantastic! Very much appreciated. Thank you for the time and effort you put into these.

Amazing videos by your channel, keep it up

I appreciate your efforts

Dude you are awesome, you have the most explanatory videos on everything. I love it.

in which sorting technique an element is placed at its correct position at each step??

this video is really very helpful. good job and thanks

please make a video of heap sort and radix sort

Could you please also add heap and radix sort algorithms in the list? Your videos have helped me understand the sorting algo better. Thanks 🙂

Awesome vids, clearly explained, with nice examples 🙂

Thanks for knowledge Its really helps me to crack an interview. Keep It Up!!!!!!

why the narrators are always Indians?

Very good, thanks

Thank you!

Thank you very much , nicely explained !

Nicely Explained in a very excellent way…Thanks Sir

it would be great favour if you explain other sorting algorithms along with those that you have already explained.

d

please post heap sort algorithm. it will help me a lot. Please do it quickly..

nicely explained

sir, you are great awesome.

itll be great if you can also provide a video for heap sort.

Good One school

awesome… i came across with the same video with the same title uploaded by hacksandsecurity… Report it!

Sir, your videos on sorting are awesome. Thanks a lot.

Could you please make videos on heap sort, counting sort, radix sort, bucket sort and shell sort?

I need to learn them as well. Thank you in advance.

Help me with heap sort pleaaaase…… 🙁

Any Plans for Counting Sort, Bucket Sort, Heap Sort?

Great tutorial. Do one on heap sort aswell please.

One of those channels where you like the video before watching…

Thank you so much for all your videos bro.. simply awesome and very clearly understandable.. I owe you a lot

My Go to Tutorial for Coding is Bucky from TheNewBoston & u you i guess

Do anyone know what compiler he is using??

Please Add bucket sort ,tree sort, heapsort,shell sort

you said 2^64 ms would take some years. But I calculated the exact amount of time it would take. It is equal to:

1.8446744*10^19 ms, which is equal to 73 billion years, about five and a half times the age of the universe.

best explanation..

I love this channel! I just got done with your data structures playlist. So happy to see a sorting algorithms playlist too. You're brilliant at explaining the concepts. A big thank you!

Thanks sir

can you make videos on DBMS.

Can you please upload for heap sort also. I like your teaching style !

Hotel?? Trivago.

2018 anyone?

Please Add bucket sort ,tree sort, heap sort, shell sort

Can you please add a tutorial for Counting,Bucket and Radix sortings also.

Your explanations are so good! Your tutorials are so professional than the paid one. I'm looking for your tutorials on design patterns. Thanks a lot.

this series is up to quick sort,where i get the last three sorting techniques??

amazing

thank bro amazing explanation

amazing playlist

Thanks God…

Keep continue Ur good work

God bless

Can you do a video on heap sort?

amazing video

very much helpful

is this play list satesify for algorithms in C programming?…any one reply me plz

better than cs50 shorts videos in every freaking way!!

Great bro

efficient moves

i like big chode

Where did 2 to the power of 64 come from??

kindly upload counting sort video

Thanks a lot. Good video.

If you want about algorithmic content, visit https://www.youtube.com/watch?v=0IAPZzGSbME&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O

Thanks

This guy is just sooo good! Isn't there anyone who can continue his good work?

radix sort is not there

Great content here, Keep up the good job

Thanks from the hurt 🤣

Nice tutorials. I would like it very much if you add some advanced sorting algorithms.

i love ur video why dont u make tutorail on java from scratch to advanced.

3:10