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

Selection Sort in Data Structures

$$/$$

Having learnt bubble sort, it’s time for you to discover how the next sorting algorithm, called Selection sort, works. In bubble sort, each iteration pushed the next highest number to the end. You will do something similar in this sorting too, but in a smarter way. The following video will show you how it’s done.

$$/$$

Video Transcript

 

So till now you had seen bubble sort and seen that there are a large number of comparisons and swaps involved while doing a bubble sort. Now, what was the result of each iteration of bubble sort? In bubble sort, after each iteration, the maximum element was getting pushed towards the rightmost edge of the array. So instead of doing so many number of swaps, wouldn't it have been better if we would have sort of maintained what is the max element in the array and simply swapped it with the last element? So this is the basic logic of how selection sort work. Here we are going to find the min element in each step, which is the minimum element, and swap it with the leftmost element in the unsorted array. So here if my array looks something like this 75421, what I'll do is that I'll begin from this index and in each step I will maintain a variable which I will call as min. So this variable min maintains the minimum element in my unsorted array. For starting, I would initialize this min variable with my index zero. That is I will assume that my element at index zero is my min element. So now my min is here. I will compare all of the corresponding consecutive elements and see if my min changes. So currently my min is here, whose value is seven. In the next step I will see if this element is less than or more than seven. I would see that since five is less than seven, I would update my min value and my min would now come at this index. In the corresponding next step, I would see that since four is again less than five, my min will get updated to this index. Similarly, in the next step, again, since two is less than four, my min index would come out to be here. And in my last comparison, I would see that since one is again less than two, so my min index would correspondingly be updated till that index. So what I'll do at the end of this iteration is that I will swap the leftmost element with my element at the min index. That is I will swap seven with the min element which is one.

 

So the end of this iteration will give me an array which looks something like this. Now I can clearly see that this element has now been placed at its correct position. So in my next iteration I can conveniently ignore this element and begin the same process from this index. So as I did in my previous step, I would initialize my min index from here. Now I will repeat the same procedure and check for all the consecutive elements and compare it with my min. In the next step, I find that since four is less than five, I would update my min value to this particular index. Currently, my min would be at this index. In the last step I would compare two with seven and find that I need not update my min because my min is already this and since this is smaller than seven, my min remains the same. So at the end of this iteration I will simply swap my min element with the index from where I started my iteration which was this index. So on swapping this and this that is, I'll swap two with five. My resultant array would look something like this.

 

Applying the same logic as above, I will now ignore these two elements since they are already in place. I will begin my iteration from this point and name this index as my min index. On comparing it with the next element, I see that since four is less than five, I need not change my min index. Moreover, when I again compare my four with seven, I would see that there is no need for changing the min value. Now, since my min element coincides with the point from which I began my iteration, I need not to do anything but simply move one step ahead and carry on the next iteration. In the next iteration, my checking process would begin from this point. So again, my min would be initialized from this point and I would check the number which is adjacent to it. It would find that since five is less than seven, so the min which I already have, which is this point is correct, so I need not update my min pointer. Similarly, in the last step my procedure would start from this point. That is I would initialize my min from here and it would compare it with itself and need not change anything. So after all these iterations, my final resultant array would look something like this and finally my array would be in the sorted order. If you notice carefully, you would see that there are very less number of swaps involved in this process. This is similar to Bubble Sort in the manner that here also in each step only one number is getting placed at the correct position. But the number of swaps involved are very much less as compared to Bubble Sort. The number of comparisons however, are similar to the number of comparisons in Bubble Sort. But we are utilizing the fact that in each iteration only one element is getting placed at its correct position. So we can simply swap the current minimum element to its correct position. Now, you can see that this array was an example of my worst case scenario because here all the elements were in the reverse order. Now, I want you to think that what were the number of swaps involved if you would have carried out Bubble Sort on this and how many swaps did we do here when we did selection Sort? Think about it carefully and answer in the question that follows.

 

Video Recap

 

  • Selection sort is a sorting algorithm that finds the minimum element in each iteration and swaps it with the leftmost element in the unsorted array.

  • This reduces the number of swaps involved as compared to bubble sort, where a large number of comparisons and swaps are required.

  • The algorithm works by initializing a minimum variable and comparing it with the consecutive elements in the array to find the minimum element.

  • The minimum element is then swapped with the leftmost element in the unsorted array, and the process is repeated until the array is sorted.

  • In each iteration, only one element is getting placed at its correct position, which minimizes the number of swaps required.

  • The number of comparisons involved is similar to bubble sort, but the algorithm utilizes the fact that only one element is getting placed at its correct position in each iteration.

  • Selection sort is more efficient than bubble sort in terms of the number of swaps involved, but it still has a time complexity of .

  • Selection sort works well for small arrays but becomes inefficient for large arrays.

  • In the worst-case scenario, where all the elements are in reverse order, selection sort requires n-1 swaps, whereas bubble sort requires swaps.

 

You’ve learnt that Selection sort also, at the end of each iteration, pushes the next highest number to the end. However, this time it was done with fewer number of swaps. You just picked the highest number in each iteration and swapped it with the last, unsorted number. So, each iteration in the worst case needs only one swap. This is unlike bubble sort where you have to compare and swap every two numbers every time they are out of order. In the next video, you will look at the pseudocode of Selection sort.

$$/$$

Now that you have learnt how to write the pseudocode for Selection sort, let’s move on to our next segment where you will see the Java implementation of the algorithm.