Көбүкчө сорттоо жана Кыстаруу иреттөө
Bubble сорттоо – чектеш элементтердин жуптарын салыштырып, кайра-кайра иреттелүүчү тизмени карап чыгуу менен иштеген сорттоо алгоритми. Эгерде жуп элементтер туура эмес тартипте болсо, алар туура тартипте жайгаштыруу үчүн алмаштырылат. Бул өтүү эч кандай башка алмаштыруу талап кылынмайынча кайталанат. Кыстаруу сорту дагы сорттоо алгоритми болуп саналат, ал киргизүү тизмесине элементти мурунтан эле иреттелген тизмедеги туура орунга киргизүү менен иштейт. Бул процесс тизме иреттелгенге чейин кайталанып колдонулат.
Bubble Sort деген эмне?
Bubble сорттоо – чектеш элементтердин жуптарын салыштырып, кайра-кайра иреттелүүчү тизмени карап чыгуу менен иштеген сорттоо алгоритми. Эгерде жуп элементтер туура эмес тартипте болсо, алар туура тартипте жайгаштыруу үчүн алмаштырылат. Бул өтүү эч кандай башка алмаштыруу талап кылынмайынча кайталанат (бул тизме иреттелген дегенди билдирет). Тизмедеги майда элементтер көбүктүн бетине чыкканда жогору тургандыктан, ага көбүк сорту деп аталат. Bubble сорттоо - бул абдан жөнөкөй сорттоо алгоритми, бирок n элементи бар тизмени сорттоодо анын орточо убакыт татаалдыгы O(n2) болот. Ушундан улам көбүкчө сорттоо элементтери көп тизмелерди сорттоо үчүн ылайыктуу эмес. Бирок анын жөнөкөйлүгүнөн улам көбүкчө сорттоо алгоритмдерге киришүү учурунда үйрөтүлөт.
Киргизүүнү сорттоо деген эмне?
Киргизүү сорту – бул киргизүү тизмегиндеги элементти тизмедеги туура орунга (ал мурунтан эле иреттелген) киргизүү менен иштеген башка сорттоо алгоритми. Бул процесс тизме иреттелгенге чейин кайталанып колдонулат. Кыстаруу иретинде сорттоо ордунда жүргүзүлөт. Демек, алгоритмдин i-итерациясынан кийин, тизмедеги биринчи i+1 жазуулар иргелет, ал эми калган тизмелер сорттолбойт. Ар бир итерацияда тизменин сорттолбогон бөлүгүндөгү биринчи элемент алынып, тизменин сорттолгон бөлүгүндөгү туура жерге киргизилет. Кыстаруу иретинде O(n2) орточо иш убактысынын татаалдыгы бар. Ушундан улам, кыстаруу сорту чоң тизмелерди сорттоо үчүн да ылайыктуу эмес.
Bubble сорттоо менен Кыстаруу сортунун ортосунда кандай айырма бар?
Көбүкчө сорттоо жана киргизүү алгоритмдеринин орточо иш убактысынын татаалдыгы O(n2) болгонуна карабастан, көбүкчө сорттоо кыстаруу түрүнөн дээрлик ар дайым ашып турат. Бул эки алгоритм үчүн зарыл болгон своптордун санына байланыштуу (көбүктүн сортторуна көбүрөөк своп керек). Бирок көбүктүү сорттун жөнөкөйлүгүнөн улам, анын кодунун өлчөмү өтө кичинекей. Ошондой эле кыстаруу сортунун кабыкча сорту деп аталган варианты бар, ал убакыттын татаалдыгы O(n3/2) бар, бул аны иш жүзүндө колдонууга мүмкүндүк берет. Андан тышкары, кыстаруу сорту көбүкчө сортторго салыштырмалуу "дээрлик иреттелген" тизмелерди сорттоо үчүн абдан натыйжалуу.
