COURSES
MBAData Science & AnalyticsDoctorate Software & Tech AI | ML MarketingManagement
Professional Certificate Programme in HR Management and AnalyticsPost Graduate Certificate in Product ManagementExecutive Post Graduate Program in Healthcare ManagementExecutive PG Programme in Human Resource ManagementMBA in International Finance (integrated with ACCA, UK)Global Master Certificate in Integrated Supply Chain ManagementAdvanced General Management ProgramManagement EssentialsLeadership and Management in New Age BusinessProduct Management Online Certificate ProgramStrategic Human Resources Leadership Cornell Certificate ProgramHuman Resources Management Certificate Program for Indian ExecutivesGlobal Professional Certificate in Effective Leadership and ManagementCSM® Certification TrainingCSPO® Certification TrainingLeading SAFe® 5.1 Training (SAFe® Agilist Certification)SAFe® 5.1 POPM CertificationSAFe® 5.1 Scrum Master Certification (SSM)Implementing SAFe® 5.1 with SPC CertificationSAFe® 5 Release Train Engineer (RTE) CertificationPMP® Certification TrainingPRINCE2® Foundation and Practitioner Certification
Law
Job Linked
Bootcamps
Study Abroad
Master of Business Administration (90 ECTS)Master of Business Administration (60 ECTS)Master in Computer Science (120 ECTS)Master in International Management (120 ECTS)Bachelor of Business Administration (180 ECTS)B.Sc. Computer Science (180 ECTS)MS in Data AnalyticsMS in Project ManagementMS in Information TechnologyMasters Degree in Data Analytics and VisualizationMasters Degree in Artificial IntelligenceMBS in Entrepreneurship and MarketingMSc in Data AnalyticsMS in Data AnalyticsMaster of Science in AccountancyMS in Computer ScienceMaster of Science in Business AnalyticsMaster of Business Administration MS in Data ScienceMS in Information TechnologyMaster of Business AdministrationMS in Applied Data ScienceMaster of Business AdministrationMS in Data AnalyticsM.Sc. Data Science (60 ECTS)Master of Business AdministrationMS in Information Technology and Administrative Management MS in Computer Science Master of Business Administration MBA General Management-90 ECTSMSc International Business ManagementMS Data Science MBA Business Technologies MBA Leading Business Transformation Master of Business Administration MSc Business Intelligence and Data ScienceMS Data Analytics MS in Management Information SystemsMSc International Business and ManagementMS Engineering ManagementMS in Machine Learning EngineeringMS in Engineering ManagementMSc Data EngineeringMSc Artificial Intelligence EngineeringMPS in InformaticsMPS in Applied Machine IntelligenceMS in Project ManagementMPS in AnalyticsMS in Project ManagementMS in Organizational LeadershipMPS in Analytics - NEU CanadaMBA with specializationMPS in Informatics - NEU Canada Master in Business AdministrationMS in Digital Marketing and MediaMS in Project ManagementMaster in Logistics and Supply Chain ManagementMSc Sustainable Tourism and Event ManagementMSc in Circular Economy and Sustainable InnovationMSc in Impact Finance and Fintech ManagementMS Computer ScienceMS in Applied StatisticsMS in Computer Information SystemsMBA in Technology, Innovation and EntrepreneurshipMSc Data Science with Work PlacementMSc Global Business Management with Work Placement MBA with Work PlacementMS in Robotics and Autonomous SystemsMS in Civil EngineeringMS in Internet of ThingsMSc International Logistics and Supply Chain ManagementMBA- Business InformaticsMSc International ManagementMS Computer Science with AIML ConcentrationMBA in Strategic Data Driven ManagementMaster of Business AdministrationMSc Digital MarketingMBA Business and MarketingMaster of Business AdministrationMSc Digital MarketingMSc in Sustainable Luxury and Creative IndustriesMSc in Sustainable Global Supply Chain ManagementMSc in International Corporate FinanceMSc Digital Business Analytics MSc in International HospitalityMSc Luxury and Innovation ManagementMaster of Business Administration-International Business ManagementMS in Computer EngineeringMS in Industrial and Systems EngineeringMSc International Business ManagementMaster in ManagementMSc MarketingMSc Business ManagementMSc Global Supply Chain ManagementMS in Information Systems and Technology with Business Intelligence and Analytics ConcentrationMSc Corporate FinanceMSc Data Analytics for BusinessMaster of Business AdministrationMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSBachelors in International Management
For College Students

Analysis of Selection Sort in Data Structures

$$/$$

Like our previous algorithms, in this lesson, you will analyse selection sort for efficiency. Remember that selection sort requires less number of swaps than bubble sort, and you must be curious to see how that makes a difference on its Big O. Let’s look at the analysis in the next video.

$$/$$

Video Transcript

 

So now we'll take a look at the time complexity of selection sort. So here consider that I have this array ten 9876. In the next step what will happen is that in the first iteration what I'll be doing is that I will begin from this index and I will keep my min also here and consequently check for all these elements. So after the first iteration I would find that my min index is here so I would swap this with this. As a result of this operation in my next step my array would become something like this because the six and ten have been swapped, my six will come here and ten will be here. For the next iteration I will begin checking at this point I will keep my min here and consequently check which is the min element. In the rest of the array I'll find that my min element will occur here which is seven. So I will swap nine with seven and I would get this array as my result which will be 6789 and ten. In the next step I would start checking at this point and again check for the min element.

 

In the rest of the array I would find that the min element is the same as my starting element so there is no need to update anything. In my next step I would begin checking. At this point I would repeat the same procedure and find that since my min element corresponds and coincides to this same element there is no need to change anything. Similarly in the mala step I would begin checking at this point and since I am left with only one element it must surely be at its correct position. Now let us try to analyze and see what are the total number of swaps and what are the total number of comparisons which I did for this entire process. So here I had an array of five elements. Here I was comparing ten with nine, eight, seven and six. First comparison, second comparison, third comparison and fourth comparison. So in the first step I was doing four number of comparisons. Since my n, which is the number of elements here is five, I can say that the total number of comparisons I did in the first step were n minus one. In the second step I started from nine and compared it with eight, seven and ten. First comparison, second comparison and third comparison. So similarly applying the same logic as above I can say that the number of comparisons I did here is n minus two. Similarly for this step the number of comparisons will be n minus three, n minus four and it will go on till I'm left with a single comparison which is the comparison of this element with itself. So now these are the total number of comparisons which I am doing. Let me denote this by t of n. Now let us check what are the total number of swaps which are doing in the first step we only swapped ten with six. What are the number of swaps? The number of swaps is one here. Similarly, in the second step we only swapped nine with seven. So here also the number of swaps is one. So extrapolating this we can say that at maximum in each step of selection sort we are doing only one number of swap. Now, if you recall, how many swaps were we doing in bubble sort? If you remember, in bubble sort in each of these iterations, for example, in the first iteration we were swapping all the elements which were out of order. So we were actually doing n minus one number of swaps. Compare it with the one swap we are doing here. Similarly, in the second iteration of bubble sort we were again doing n minus two number of swaps. In the worst case here also we have a worst case scenario since all the elements are in reverse order but still at max, we are doing only one swap here. So we can conclude that selection sort has far less number of swaps involved as compared to bubble sort. Now here for calculating the time complexity we are only going to consider the total number of comparisons involved. So what will be the total number of comparisons? I will have to do the summation of all these comparisons. I'll write t of n is equal to one plus two plus three plus n minus three plus n minus two plus n minus one. I can write it like this.

 

Now, if you remember, this is nothing but the sum of the first n minus one natural numbers. As you saw in the time analysis of bubble sort, this comes out to be n minus one into n divided by two. Applying a similar logic, this can be reduced to half of n square minus n. On looking at this expression carefully, you'll see that I can ignore n in front of this bigger value which is N square. Moreover, I can also ignore this half since this is a constant. So this t of n basically reduces to the order of n square. So I will say that t of n is equal to theta of n square. So in conclusion, the time complexity of selection sort is also theta of n square. So how does it differ from the bubble sort? Well, the overall time complexity for both bubble sort and selection sort is of the order of theta n square. However, the number of swaps involved here are far less as compared to bubble sort. So the number of steps, the number of expensive steps involved in selection sort are very much less as compared to bubble sort. So we can say that selection sort is a better sorting algorithm as compared to bubble sort.

 

Video Recap

 

  • Selection sort involves iterating through an array and swapping the minimum element found with the first unsorted element, and repeating the process with the remaining unsorted elements.

  • The total number of comparisons involved in selection sort is equal to the sum of the first natural numbers.

  • The time complexity of selection sort is .

  • The number of swaps involved in selection sort is far less than bubble sort, making it a better sorting algorithm overall.

  • The time complexity of both bubble sort and selection sort is of the order of .

 

So, as far as goes, selection sort also has a time complexity of O(N). Remember that you learnt that it performs fewer swaps than bubble sort. So ideally, it should run a bit more efficiently than bubble sort. In the next video, you will see sorting of a deck of the same six cards and realise the answer to this efficiency problem.

$$/$$

The video explained the answer to your question in detail. The actual number of steps a selection sort takes is N/2. But N/2 also falls into the time complexity of O(N). Therefore, despite selection sort being more efficient than bubble sort, it falls into the same Big O category as does bubble sort. In the next segment, you will learn about the next sorting algorithm — insertion sort.