Bubble Sorteer vs Invoeging Sorteer
Bubble sorteer is 'n sorteeralgoritme wat werk deur die lys deur te gaan om herhaaldelik gesorteer te word terwyl pare elemente wat aangrensend is vergelyk. As 'n paar elemente in die verkeerde volgorde is, word hulle omgeruil om hulle in die regte volgorde te plaas. Hierdie deurkruising word herhaal totdat geen verdere omruilings nodig is nie. Invoegingssortering is ook 'n sorteeralgoritme wat werk deur 'n element in die invoerlys in te voeg na die korrekte posisie in 'n lys wat reeds gesorteer is. Hierdie proses word herhaaldelik toegepas totdat die lys gesorteer is.
Wat is Bubble Sort?
Bubble sorteer is 'n sorteeralgoritme wat werk deur die lys deur te gaan om herhaaldelik gesorteer te word terwyl pare elemente wat aangrensend is vergelyk. As 'n paar elemente in die verkeerde volgorde is, word hulle omgeruil om hulle in die regte volgorde te plaas. Hierdie deurkruising word herhaal totdat geen verdere omruilings nodig is nie (wat beteken dat die lys gesorteer is). Aangesien die kleiner elemente in die lys na bo kom soos 'n borrel na die oppervlak kom, kry dit die naam borrelsoort. Bubble sorteer is 'n baie eenvoudige sorteer algoritme maar dit het 'n gemiddelde saak tyd kompleksiteit van O(n2) wanneer 'n lys met n elemente gesorteer word. As gevolg hiervan is borrelsortering nie geskik om lyste met 'n groot aantal elemente te sorteer nie. Maar as gevolg van die eenvoud daarvan, word borrelsortering geleer tydens inleidings tot algoritmes.
Wat is Invoegingssortering?
Invoegingssortering is 'n ander sorteeralgoritme wat werk deur 'n element in die invoerlys in te voeg na die korrekte posisie in 'n lys (wat reeds gesorteer is). Hierdie proses word herhaaldelik toegepas totdat die lys gesorteer is. In invoegingssorteer word sortering in die plek uitgevoer. Dus na die iterasie van die algoritme, sal die eerste i+1-inskrywings in die lys gesorteer word en die res van die lys sal ongesorteer wees. By elke iterasie sal die eerste element in die ongesorteerde deel van die lys geneem word en op die regte plek in die gesorteerde gedeelte van die lys ingevoeg word. Invoeging sorteer het 'n gemiddelde saak tyd kompleksiteit van O(n2). As gevolg hiervan is invoegingssortering ook nie geskik om groot lyste te sorteer nie.
Wat is die verskil tussen Bubble Sort en Insertion Sort?
Selfs al het beide die borrel-sorteer- en invoeg-sorteer-algoritmes gemiddelde geval-tyd-kompleksiteite van O(n2), word borrelsortering byna heeltyd beter as die invoegingssorteer gevaar. Dit is as gevolg van die aantal omruilings wat deur die twee algoritmes benodig word (borrelsoorte benodig meer omruilings). Maar as gevolg van die eenvoud van borrelsoort, is die kodegrootte daarvan baie klein. Daar is ook 'n variant van invoegingssoort genaamd die dopsoort, wat 'n tydkompleksiteit van O(n3/2) het, wat dit prakties sal toelaat om dit te gebruik. Verder is invoegingssortering baie doeltreffend om "byna gesorteerde" lyste te sorteer, in vergelyking met die borrelsortering.
