Renditja me flluska vs renditja e futjes
Renditja me flluska është një algoritëm renditjeje që funksionon duke kaluar nëpër listën që do të renditet në mënyrë të përsëritur ndërsa krahason çifte elementësh që janë ngjitur. Nëse një çift elementësh është në rendin e gabuar, ato këmbehen për t'i vendosur ato në rendin e duhur. Ky kalim përsëritet derisa të mos kërkohen shkëmbime të tjera. Renditja e futjes është gjithashtu një algoritëm renditjeje, i cili funksionon duke futur një element në listën hyrëse në pozicionin e duhur në një listë që tashmë është renditur. Ky proces zbatohet në mënyrë të përsëritur derisa lista të renditet.
Çfarë është Renditja me flluska?
Renditja me flluska është një algoritëm renditjeje që funksionon duke kaluar nëpër listën që do të renditet në mënyrë të përsëritur ndërsa krahason çifte elementësh që janë ngjitur. Nëse një çift elementësh është në rendin e gabuar, ato këmbehen për t'i vendosur ato në rendin e duhur. Ky kalim përsëritet derisa të mos kërkohen më këmbime (që do të thotë se lista është renditur). Meqenëse elementët më të vegjël në listë dalin në krye kur një flluskë del në sipërfaqe, asaj i jepet emri lloj flluskë. Renditja me flluskë është një algoritëm shumë i thjeshtë renditjeje, por ai ka një kompleksitet mesatar kohor të rastit prej O(n2) kur rendit një listë me n elementë. Për shkak të kësaj, renditja me flluska nuk është e përshtatshme për renditjen e listave me një numër të madh elementësh. Por për shkak të thjeshtësisë së tij, renditja me flluska mësohet gjatë hyrjeve në algoritme.
Çfarë është Insertion Sort?
Rendimi i futjes është një tjetër algoritëm klasifikimi, i cili funksionon duke futur një element në listën hyrëse në pozicionin e duhur në një listë (që tashmë është renditur). Ky proces zbatohet në mënyrë të përsëritur derisa lista të renditet. Në renditjen e futjes, renditja kryhet në vend. Prandaj, pas përsëritjes së dytë të algoritmit, hyrjet e para i+1 në listë do të renditen dhe pjesa tjetër e listës do të jetë e pa renditur. Në çdo përsëritje, elementi i parë në pjesën e parregulluar të listës do të merret dhe do të futet në vendin e duhur në seksionin e renditur të listës. Renditja e futjes ka një kompleksitet mesatar kohor të rastit prej O(n2). Për shkak të kësaj, renditja e futjes nuk është gjithashtu e përshtatshme për renditjen e listave të mëdha.
Cili është ndryshimi midis renditjes me flluska dhe renditjes së futjes?
Edhe pse si algoritmet e renditjes me flluskë ashtu edhe algoritmi i renditjes së futjes kanë kompleksitet mesatar kohor të rastit prej O(n2), renditja me flluska është pothuajse gjatë gjithë kohës më e mirë se renditja e futjes. Kjo është për shkak të numrit të shkëmbimeve të nevojshme nga dy algoritmet (llojet me flluska kanë nevojë për më shumë shkëmbime). Por për shkak të thjeshtësisë së renditjes me flluskë, madhësia e kodit të tij është shumë e vogël. Ekziston gjithashtu një variant i renditjes së futjes, i quajtur lloji i guaskës, i cili ka një kompleksitet kohor prej O(n3/2), i cili do ta lejonte atë të përdoret praktikisht. Për më tepër, renditja e futjes është shumë efikase për renditjen e listave "pothuajse të renditura", kur krahasohet me renditjen me flluska.
