Массивди сорттоо маселесин чечүү үчүн бир нече негизги алгоритмдер бар. Алардын ичинен эң атактууларынын бири – кыстаруу сорту. Айкындыгы жана жөнөкөйлүгү, бирок эффективдүүлүгү төмөн болгондуктан бул метод негизинен программалоону үйрөтүүдө колдонулат. Бул негизги сорттоо механизмдерин түшүнүүгө мүмкүндүк берет.
Алгоритмдин сүрөттөлүшү
Киргизүүнү сорттоо алгоритминин маңызы – баштапкы массивдин ичинде туура иреттелген сегмент түзүлөт. Ар бир элемент бирден текшерилген бөлүк менен салыштырылат жана керектүү жерге киргизилет. Ошентип, бардык элементтерди кайталагандан кийин, алар туура тартипте тизилет.
Элементтерди тандоо тартиби каалаган болушу мүмкүн, алар каалагандай же кандайдыр бир алгоритм боюнча тандалышы мүмкүн. Көбүнчө ырааттуу саноо массивдин башынан баштап колдонулат, мында иреттелген сегмент түзүлөт.
Сорттоонун башталышы мындай болушу мүмкүн:
- Массивдин биринчи элементин ал.
- Салыштыра турган эч нерсе болбогондуктан, элементтин өзүн буйрутма катары кабыл алыңызырааттуулугу.
- Экинчи нерсеге өтүңүз.
- Сорттоо эрежесинин негизинде аны биринчиси менен салыштырыңыз.
- Эгер зарыл болсо, элементтерди орду менен алмаштырыңыз.
- Биринчи эки элементти иреттелген ырааттуулук катары алыңыз.
- Үчүнчү нерсеге өтүңүз.
- Экинчиси менен салыштырыңыз, керек болсо алмаштырыңыз.
- Эгер алмаштыруу жасалган болсо, аны биринчиси менен салыштырыңыз.
- Үч элементти иреттелген ырааттуулук катары алыңыз.
Жана ушул сыяктуу баштапкы массивдин аягына чейин.
Чыныгы кыстаруу сорту
Түшүнүктүү болуу үчүн бул сорттоо механизми күнүмдүк жашоодо кандайча колдонулаарын мисал келтиргенибиз оң.
Мисалы, капчыкты алалы. Банкнот бөлүмүндө жүз, беш жүз жана миң долларлык купюралар баш аламан болуп жатат. Бул баш аламандык, мындай ходжеподждо дароо туура кагазды табуу кыйын. Банкноттордун массиви иреттелиши керек.
Эң биринчиси - 1000 рублдик банкнот, андан кийин дароо - 100. Биз жүздү алып, алдына коёбуз. Үчүнчүсү катары менен 500 рубль, ал үчүн татыктуу орун жүздөн миңге чейин.
Ошондой эле биз "Акмак" ойноп жатканда алынган карталарды иреттеп, аларды башкарууну жеңилдетүү үчүн.
Операторлор жана жардамчы функциялары
Киргизүүнүн сорттоо ыкмасы иреттөө үчүн баштапкы массивди, салыштыруу функциясын жана керек болсо, элементтерди санап чыгуу эрежесин аныктоочу функцияны киргизет. Анын ордуна көбүнчө колдонулаткадимки цикл билдирүүсү.
Биринчи элементтин өзү иреттелген топтом, андыктан салыштыруу экинчиден башталат.
Алгоритм көбүнчө эки маанини алмаштыруу үчүн жардамчы функцияны колдонот (алмаштыруу). Ал эстутумду талап кылган жана кодду бир аз жайлатуучу кошумча убактылуу өзгөрмө колдонот.
Альтернатива катары элементтердин тобун массалык түрдө жылдырып, андан соң учурдагыны бош мейкиндикке киргизүү саналат. Бул учурда, кийинки элементке өтүү салыштыруу оң натыйжа бергенде ишке ашат, бул туура тартипти көрсөтөт.
Ишке ашыруу мисалдары
Конкреттүү ишке ашыруу көбүнчө колдонулган программалоо тилине, анын синтаксисине жана структураларына көз каранды.
Классикалык C маанисин алмаштыруу үчүн убактылуу өзгөрмө аркылуу ишке ашыруу:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; массив[j + 1]=массив[j]; массив[j]=temp; } }
PHP ишке ашыруу:
function insertion_sort(&$a) { үчүн ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Бул жерде, биринчиден, сорттоо шартына дал келбеген бардык элементтер оңго жылдырылат, андан кийин учурдагы элемент бош мейкиндикке киргизилет.
while циклин колдонгон Java коду:
жалпыга ачык статикалык жараксыз insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Коддун жалпы мааниси өзгөрүүсүз калат: массивдин ар бир элементи ырааттуу түрдө мурункулар менен салыштырылат жана керек болсо алар менен алмаштырылат.
Болжолдуу иштөө убактысы
Албетте, эң жакшы учурда, алгоритмдин киргизилиши мурунтан эле туура иреттелген массив болот. Бул жагдайда, алгоритм жөн гана алмашуу жасабастан, анын туура жерде экенине ынануу үчүн ар бир элементти текшерүү керек болот. Ошентип, иштөө убактысы O(n) баштапкы массивинин узундугуна түздөн-түз көз каранды болот.
Эң начар киргизүү - тескери тартипте иреттелген массив. Бул көп сандагы алмаштырууну талап кылат, аткаруу убактысынын функциясы элементтердин квадраттык санына жараша болот.
Толугу менен иретсиз массив үчүн алмаштыруулардын так санын формула менен эсептесе болот:
n(n-1)/2
мында n - баштапкы массивдин узундугу. Ошентип, 100 элементти туура тартипте жайгаштыруу үчүн 4950 алмаштыруу керек болот.
Киргизүү ыкмасы кичинекей же жарым-жартылай иреттелген массивдерди сорттоо үчүн абдан натыйжалуу. Бирок, эсептөөлөрдүн татаалдыгына байланыштуу аны бардык жерде колдонуу сунушталбайт.
Алгоритм башка көптөгөн татаал сорттоо ыкмаларында жардамчы катары колдонулат.
Бирдей маанилерди иреттөө
Киргизүү алгоритми туруктуу деп аталган түрлөргө кирет. Бул билдирет,ал окшош элементтерди алмаштырбайт, бирок алардын баштапкы тартибин сактайт. Туруктуулук индекси көп учурларда туура иреттөө үчүн маанилүү.
Жогорудагылар бийге киргизүүнүн сонун визуалдык мисалы.
