Különbség a buborékrendezés és a választás szerinti rendezés között

Bubble Sort vs Selection Sort

A Bubble sort egy válogatási algoritmus, amely úgy működik, hogy a szortírozandó elemek párjának összehasonlításakor ismételten átmegy a válogatandó listán. Ha egy pár elem nem megfelelő sorrendben van, akkor felcserélik őket, hogy a megfelelő sorrendbe helyezzék őket. Ezt a keresztezést addig ismételjük, amíg további cserékre nincs szükség. A szelekciós rendezés egyfajta rendezési algoritmus is, amely azzal kezdődik, hogy megtalálja a minimális elemet a listában, és felcseréli az első elemre. Ezt a folyamatot a lista fennmaradó részében megismételtük úgy, hogy sorba rendezzük a felcserélt elemeket.

Mi a Bubble Sort??

A Bubble sort egy válogatási algoritmus, amely úgy működik, hogy a szortírozandó elemek párjának összehasonlításakor ismételten átmegy a válogatandó listán. Ha egy pár elem nem megfelelő sorrendben van, akkor felcserélik őket, hogy a megfelelő sorrendbe helyezzék őket. Ezt az átjárást addig ismételjük, amíg további cserékre nincs szükség (ami azt jelenti, hogy a lista rendezett). Mivel a lista kisebb elemei a tetejére kerülnek, amikor egy buborék megjelenik a felszínen, akkor a buborékfajta elnevezést kapják. A Bubble sort egy nagyon egyszerű válogatási algoritmus, de átlagos eseti ideje bonyolult O (n2), ha n elemet tartalmazó listát rendezünk. Emiatt a buborékrendezés nem alkalmas nagyszámú elemű listák rendezésére. Az egyszerűség miatt azonban a buborék rendezését az algoritmusok bevezetése során tanítják.

Mi az a válogatás??

A szelekciós rendezés egy másik válogatási algoritmus, amely úgy kezdődik, hogy megtalálja a minimális elemet a listában, és felcseréli az első elemre. Ezután a minimális elem megtalálható a lista fennmaradó részétől (a második elemtől a lista utolsó eleméig) és felcserélhető a második elemmel. Ezt a folyamatot a lista fennmaradó részében megismételtük úgy, hogy sorba rendezzük a felcserélt elemeket. Tehát a választás szerinti rendezésnél az algoritmus bármelyik lépésekor a lista két részre oszlik, ahol az egyik rész rendezett elemeket tartalmaz, a másik rész pedig nem válogatott elemeket. Az algoritmus előrehaladtával a rendezett lista balról jobbra növekszik. A szelekciós rendezésnek az eset átlagos ideje is bonyolult O (n2). Ezért nem is alkalmas nagy listák rendezésére.

Mi a különbség a Bubble Sort és a Selection Sort között??

Annak ellenére, hogy mind a buborék rendezés, mind a szelekciós rendezési algoritmusok átlagos esetbeli bonyolultsága O (n2), a buborék rendezést szinte minden alkalommal meghaladja a szelekciós sorrend. Ennek oka a két algoritmushoz szükséges csereügyletek száma (a buborékfajtáknak további csereprogramokra van szükségük). De a buborék rendezésének egyszerűsége miatt a kód mérete nagyon kicsi. A stabilitás egy másik különbség e két algoritmusban. Stabil rendezési algoritmus: olyan rendezési algoritmus, amely megőrzi a rekordok sorrendjét, ha a lista azonos értékű elemeket tartalmaz. Ebben az értelemben a szelekciós rendezés nem stabil algoritmus, míg a buborék rendezés stabil algoritmus.