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

Insertion Sort Vs Selection Sort: Know the Difference

$$/$$

Now, something very interesting awaits you. If you are asked to pick the more efficient algorithm out of these two, which one will you choose when both of them have the same time complexity in terms of Big O. How would you decide on the better algorithm in such cases? In the next video, you will see the comparison between selection sort and insertion sort, where both have a time complexity of O(N). This exercise will help you figure out the answer to this question along the way.

$$/$$

Video Transcript

 

We have looked at how insertion sort performs in the worst case scenario where the array is sorted in descending order. In the worst case, we pointed out that in each iteration we compare and shift every value that we encounter. We calculated this to be a total of n square comparisons and shifts. In the best case scenario, where the data is already sort sorted in ascending order, we end up making just one comparison per iteration and not a single shift. Because each value is already in its correct place, the data is randomly sorted. We can have iterations in which we might have to compare and shift all the data, some of the data or possibly none of the data, while in the worst case scenario we compare and shift all the data and in the best case scenario we shift none of the data and just make one comparison per iteration. For the average scenario, we can say that on an average we probably compare and shift about half of the data. So if insertion sort takes n square steps for the worst case

 

scenario, we would say that it takes about n square by two steps for the average scenario, which is half of what it takes in the worst case scenario. In terms of Big O, however, both the scenarios are order and square. Let's dive into some specific examples. The array 1234 is already sorted, which is the best case. The worst case for the same data would be 4321 and an example of average case might be 1342. In the worst case, there are six comparisons and six shifts. So a total of twelve steps. In the average case, there are five comparisons and two shifts for a total of twelve steps. In the best case, there are three comparisons and no shift. We can now see that the performance of insertion sort varies greatly based on the scenarios. In the worst case scenario, insertion sort takes n square steps. In the average scenario it takes n square by two steps and in the best case scenario it takes about n steps. Compare this with selection sort. Selection sort takes n square by two steps in all

 

cases, from worst case to the average case to the best case. This is because selection sort doesn't have any mechanism for ending an iteration early. At any point in every iteration, the algorithm compares the chosen value to every value to its right, no matter what. Also, the difference between n square and n square by two keeps on increasing as the size of data keeps on increasing. So which is better? Selection sort or insertion sort? The answer is that it depends. In an average case where an array is randomly sorted, they perform similarly. If you have a reason to assume that you will be dealing with data that is mostly sorted, insertion sort will be a better choice. If you have a reason to assume that you will be dealing with data that is mostly sorted in reverse order selection sort will be faster. If you have no idea what the data might be, that's essentially an average case, then either of them can be used. So one major takeaway of this module so far is that when two algorithms have

 

the same big O, it doesn't necessarily mean that both algorithms process at the same speed. After all, bubble sort is half as fast as selection sort, even though both are order and square. So while big O is perfect for contrasting algorithms that fall under different classifications of big O, when two algorithms fall under the same classification, further analysis is required to determine which algorithm is better. So the good news is that we are done with sort algorithms. With N square efficiencies, we will now learn more efficient and faster sorting algorithms. Let's move on to the next video.

 

Video Recap

 

 Insertion sort performs worst when the array is sorted in descending order, as every value needs to be compared and shifted in each iteration, making a total of comparisons and shifts.

 

  • In the best case scenario, where the data is already sorted in ascending order, only one comparison is made per iteration and no shifts are needed.

  • The average scenario of insertion sort involves comparing and shifting about half of the data, which takes about  steps.

  • Both worst and average cases have an order of in Big (O) notation.

  • Insertion sort's performance varies greatly based on scenarios, as compared to selection sort which takes steps in all cases.

  • The choice between insertion sort and selection sort depends on the type of data being sorted. Insertion sort is better for mostly sorted data, while selection sort is better for data mostly sorted in reverse order.

  • When two algorithms have the same Big (O) notation, further analysis is required to determine which one is faster and more efficient.

  • Bubble sort is slower than selection sort, even though both have the same Big(O) notation of .

 

Great! That was a useful insight. Selection sort actually takes N/2 steps but falls into the same Big O category as does insertion sort. You also know which sorting algorithm is more effective based on the kind of datasets we are dealing with. As discussed, insertion sort behaves differently in best and worst-case scenarios. So for best results, keep all this in mind before choosing a sorting algorithm.