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