Պղպջակների տեսակավորում ընդդեմ ընտրովի տեսակավորման
Պղպջակների տեսակավորումը տեսակավորման ալգորիթմ է, որն աշխատում է բազմիցս տեսակավորվող ցանկի միջով անցնելով՝ հարակից տարրերի զույգերը համեմատելով: Եթե զույգ տարրերը սխալ հերթականության մեջ են, դրանք փոխանակվում են՝ դրանք ճիշտ հերթականությամբ տեղադրելու համար: Այս անցումը կրկնվում է այնքան ժամանակ, մինչև չպահանջվի հետագա փոխանակում: Ընտրության տեսակավորումը նաև տեսակավորման ալգորիթմ է, որը սկսվում է ցանկում նվազագույն տարրը գտնելով և այն առաջին տարրի հետ փոխանակելով։ Այս գործընթացը կրկնվում է ցանկի մնացած մասի համար՝ փոխելով փոխված տարրերը հերթականությամբ:
Ի՞նչ է Bubble Sort-ը:
Պղպջակների տեսակավորումը տեսակավորման ալգորիթմ է, որն աշխատում է բազմիցս տեսակավորվող ցանկի միջով անցնելով՝ հարակից տարրերի զույգերը համեմատելով: Եթե զույգ տարրերը սխալ հերթականության մեջ են, դրանք փոխանակվում են՝ դրանք ճիշտ հերթականությամբ տեղադրելու համար: Այս անցումը կրկնվում է այնքան ժամանակ, մինչև չպահանջվեն այլ փոխանակումներ (ինչը նշանակում է, որ ցուցակը տեսակավորված է): Քանի որ ցանկի փոքր տարրերը հայտնվում են վերևում, քանի որ պղպջակը հայտնվում է մակերեսին, այն ստացել է փուչիկների տեսակավորում անվանումը: Bubble տեսակավորումը շատ պարզ տեսակավորման ալգորիթմ է, բայց այն ունի O(n2) միջին դեպքի ժամանակային բարդություն n տարրերով ցուցակը տեսակավորելիս: Դրա շնորհիվ փուչիկների տեսակավորումը հարմար չէ մեծ թվով տարրերով ցուցակների տեսակավորման համար։ Բայց իր պարզության շնորհիվ փուչիկներով տեսակավորումն ուսուցանվում է ալգորիթմների ներածության ժամանակ:
Ի՞նչ է Ընտրության տեսակավորումը:
Ընտրության տեսակավորումը նաև մեկ այլ տեսակավորման ալգորիթմ է, որը սկսվում է ցանկում նվազագույն տարրը գտնելով և այն առաջին տարրի հետ փոխանակելով:Այնուհետև նվազագույն տարրը գտնվում է ցանկի մնացորդից (երկրորդ տարրից մինչև ցուցակի վերջին տարրը) և փոխարինվում երկրորդ տարրով։ Այս գործընթացը կրկնվում է ցուցակի մնացած մասի համար՝ փոխելով տարրերը հերթականությամբ: Այսպիսով, ընտրության տեսակավորման դեպքում, ալգորիթմի ցանկացած քայլում, ցուցակը բաժանվում է երկու մասի, որտեղ մի մասը պարունակում է տեսակավորված տարրեր, իսկ մյուս մասը պարունակում է չտեսակավորված տարրեր: Քանի որ ալգորիթմը շարունակվում է, տեսակավորված ցուցակն աճում է ձախից աջ: Ընտրության տեսակավորումը ունի նաև O(n2) միջին դեպքի ժամանակային բարդություն: Հետևաբար, այն նաև հարմար չէ մեծ ցուցակների տեսակավորման համար:
Ո՞րն է տարբերությունը Bubble Sort-ի և Selection Sort-ի միջև:
Թեև և՛ պղպջակների տեսակավորման, և՛ ընտրության տեսակավորման ալգորիթմներն ունեն O(n2) միջին դեպքերի ժամանակային բարդություններ, փուչիկների տեսակավորումը գրեթե բոլոր ժամանակներում գերազանցում է ընտրության տեսակավորմանը: Սա պայմանավորված է երկու ալգորիթմների համար անհրաժեշտ փոխանակումների քանակով (փուչիկների տեսակավորման համար անհրաժեշտ են ավելի շատ փոխանակումներ):Բայց փուչիկների տեսակավորման պարզության պատճառով դրա ծածկագրի չափը շատ փոքր է: Կայունությունը այս երկու ալգորիթմների մեկ այլ տարբերություն է: Կայուն տեսակավորման ալգորիթմը տեսակավորման ալգորիթմ է, որը պահպանում է գրառումների կարգը, եթե ցանկը պարունակում է հավասար արժեք ունեցող տարրեր։ Այդ առումով ընտրության տեսակավորումը կայուն ալգորիթմ չէ, մինչդեռ փուչիկներով տեսակավորումը կայուն ալգորիթմ է:
