Bubble Sort vs Insertion Sort
Bubble sort is een sorteeralgoritme dat werkt door herhaaldelijk door de lijst te gaan die moet worden gesorteerd, terwijl paren van aangrenzende elementen worden vergeleken. Als een paar elementen in de verkeerde volgorde staat, worden ze verwisseld om ze in de juiste volgorde te plaatsen. Deze doorgang wordt herhaald totdat er geen verdere swaps nodig zijn. Invoegsortering is ook een sorteeralgoritme, dat werkt door een element in de invoerlijst in te voegen op de juiste positie in een lijst die al is gesorteerd. Dit proces wordt herhaaldelijk toegepast totdat de lijst is gesorteerd.
Wat is Bubble Sort?
Bubble sort is een sorteeralgoritme dat werkt door herhaaldelijk door de lijst te gaan die moet worden gesorteerd, terwijl paren van aangrenzende elementen worden vergeleken. Als een paar elementen in de verkeerde volgorde staat, worden ze verwisseld om ze in de juiste volgorde te plaatsen. Deze doorloop wordt herhaald totdat er geen verdere swaps nodig zijn (wat betekent dat de lijst is gesorteerd). Omdat de kleinere elementen in de lijst bovenaan komen als een bel naar de oppervlakte komt, krijgt deze de naam bubble sort. Bellen sorteren is een heel eenvoudig sorteeralgoritme, maar het heeft een gemiddelde tijdscomplexiteit van O(n2) bij het sorteren van een lijst met n elementen. Hierdoor is bubbelsortering niet geschikt voor het sorteren van lijsten met een groot aantal elementen. Maar vanwege de eenvoud wordt het sorteren van bellen geleerd tijdens introducties van algoritmen.
Wat is invoegsortering?
Invoegsortering is een ander sorteeralgoritme, dat werkt door een element in de invoerlijst in te voegen op de juiste positie in een lijst (die al is gesorteerd). Dit proces wordt herhaaldelijk toegepast totdat de lijst is gesorteerd. Bij invoegsortering wordt ter plaatse gesorteerd. Daarom worden na de iteratie van het algoritme de eerste i+1-items in de lijst gesorteerd en de rest van de lijst ongesorteerd. Bij elke iteratie wordt het eerste element in het ongesorteerde deel van de lijst genomen en ingevoegd op de juiste plaats in het gesorteerde gedeelte van de lijst. Insertion sort heeft een gemiddelde tijdscomplexiteit van O(n2). Hierdoor is insertion sort ook niet geschikt voor het sorteren van grote lijsten.
Wat is het verschil tussen Bubble Sort en Insertion Sort?
Hoewel zowel de algoritmen voor het sorteren van bellen als het sorteren van invoegingen een gemiddelde tijdscomplexiteit van O(n2) hebben, wordt het sorteren van bellen bijna altijd overtroffen door het sorteren van invoegingen. Dit komt door het aantal swaps dat nodig is voor de twee algoritmen (bubble sorts heeft meer swaps nodig). Maar vanwege de eenvoud van bellensortering, is de codegrootte erg klein. Er is ook een variant van invoegsoort, de schaalsoort genaamd, die een tijdcomplexiteit van O(n3/2) heeft, waardoor het praktisch kan worden gebruikt. Bovendien is invoegsortering zeer efficiënt voor het sorteren van "bijna gesorteerde" lijsten, in vergelijking met de bellensortering.
