Պղպջակների տեսակավորում ընդդեմ տեղադրման տեսակավորման
Պղպջակների տեսակավորումը տեսակավորման ալգորիթմ է, որն աշխատում է բազմիցս տեսակավորվող ցանկի միջով անցնելով՝ հարակից տարրերի զույգերը համեմատելով: Եթե զույգ տարրերը սխալ հերթականության մեջ են, դրանք փոխանակվում են՝ դրանք ճիշտ հերթականությամբ տեղադրելու համար: Այս անցումը կրկնվում է այնքան ժամանակ, մինչև չպահանջվի հետագա փոխանակում: Insertion sort-ը նաև տեսակավորման ալգորիթմ է, որը գործում է մուտքագրման ցանկում տարրը ճիշտ դիրքում տեղադրելով արդեն տեսակավորված ցուցակում: Այս գործընթացը կիրառվում է մի քանի անգամ, մինչև ցուցակը դասավորվի:
Ի՞նչ է Bubble Sort-ը:
Պղպջակների տեսակավորումը տեսակավորման ալգորիթմ է, որն աշխատում է բազմիցս տեսակավորվող ցանկի միջով անցնելով՝ հարակից տարրերի զույգերը համեմատելով: Եթե զույգ տարրերը սխալ հերթականության մեջ են, դրանք փոխանակվում են՝ դրանք ճիշտ հերթականությամբ տեղադրելու համար: Այս անցումը կրկնվում է այնքան ժամանակ, մինչև չպահանջվեն այլ փոխանակումներ (ինչը նշանակում է, որ ցուցակը տեսակավորված է): Քանի որ ցանկի փոքր տարրերը հայտնվում են վերևում, քանի որ պղպջակը հայտնվում է մակերեսին, այն ստացել է փուչիկների տեսակավորում անվանումը: Bubble տեսակավորումը շատ պարզ տեսակավորման ալգորիթմ է, բայց այն ունի O(n2) միջին դեպքի ժամանակային բարդություն n տարրերով ցուցակը տեսակավորելիս: Դրա շնորհիվ փուչիկների տեսակավորումը հարմար չէ մեծ թվով տարրերով ցուցակների տեսակավորման համար։ Բայց իր պարզության շնորհիվ փուչիկներով տեսակավորումն ուսուցանվում է ալգորիթմների ներածության ժամանակ:
Ի՞նչ է ներդրման տեսակավորումը:
Insertion sort-ը մեկ այլ տեսակավորման ալգորիթմ է, որը գործում է մուտքագրման ցանկում տարրը ցուցակի ճիշտ դիրքում (որն արդեն տեսակավորված է) տեղադրելու միջոցով:Այս գործընթացը կիրառվում է բազմիցս, մինչև ցուցակը դասավորվի: Ներդիր տեսակավորման դեպքում տեսակավորումն իրականացվում է տեղում: Հետևաբար ալգորիթմի կրկնակի կրկնությունից հետո ցուցակի առաջին i+1 գրառումները կտեսակավորվեն, իսկ մնացած ցուցակը կչտեսակավորվի: Յուրաքանչյուր կրկնության ժամանակ ցուցակի չտեսակավորված մասի առաջին տարրը կվերցվի և կտեղադրվի ցուցակի տեսակավորված հատվածի ճիշտ տեղում: Տեղադրման տեսակավորումն ունի O(n2) միջին դեպքի ժամանակային բարդություն: Դրա պատճառով ներդիրների տեսակավորումը նույնպես հարմար չէ մեծ ցուցակների տեսակավորման համար։
Ո՞րն է տարբերությունը Bubble Sort-ի և Insertion Sort-ի միջև:
Թեև թե՛ փուչիկների տեսակավորումը և թե՛ ներդրման տեսակավորման ալգորիթմներն ունեն O(n2) միջին դեպքերի ժամանակային բարդություններ, փուչիկների տեսակավորումը գրեթե ամբողջ ժամանակ գերազանցում է ներդրման տեսակավորմանը: Սա պայմանավորված է երկու ալգորիթմների համար անհրաժեշտ փոխանակումների քանակով (փուչիկների տեսակավորման համար անհրաժեշտ են ավելի շատ փոխանակումներ): Բայց փուչիկների տեսակավորման պարզության պատճառով դրա ծածկագրի չափը շատ փոքր է:Նաև կա ներդիրի տեսակավորման տարբերակ, որը կոչվում է shell sort, որն ունի O(n3/2) ժամանակային բարդություն, ինչը թույլ կտա այն գործնականում օգտագործել: Ավելին, ներդիրների տեսակավորումը շատ արդյունավետ է «գրեթե տեսակավորված» ցուցակները տեսակավորելու համար՝ համեմատած փուչիկների տեսակավորման հետ:
