Бұл не?
Сабақтың тақырыбы — «Сұрыптаулар». Талдап көрейік. Сұрыптау — заттарды ретімен орналастыру: сөредегі кітаптарды әліпби бойынша, тауарларды бағасы бойынша, суреттерді күні бойынша. Ортақ суретке түсу үшін достарыңды бойы бойынша тізгенде, сен өзің де сұрыптайсың. Компьютер де дәл осыны істейді, тек миллиондаған жазбамен және қатаң ережелер бойынша.
Бұл не үшін керек?
Айналаңдағы кез келген дерлік сервис сұрыптайды: іздеу ең қолайлы беттерді бірінші шығарады, маркетплейс тауарларды бағасы бойынша орналастырады, әлеуметтік желідегі лента — жаңалығы мен қызықтылығы бойынша. Дерекқорлар жазбаларда жылдам екілік іздеу жұмыс істеуі үшін оларды реттелген күйде ұстайды, ал жасанды интеллектке арналған дата-орталықтар әр секунд сайын орасан зор деректер ағындарын сұрыптайды. Бүгін сұрыптау кодын жасанды интеллект бір секундта жазады, бірақ қандай белгі бойынша реттеу керектігін шешу, нәтиженің шатасқанын байқау және миллиард жазбада тұншығып қалмайтын тәсілді таңдау — адамның ісі. Сұрыптаудың іштей қалай құрылғанын түсінетін адам міндетті де қоя алады, машинаның жауабын да тексере алады.
Бұл қалай жұмыс істейді?
Көпіршікті сұрыптау тізім бойымен жүріп, көршілерді салыстырады: сол жақтағысы оң жақтағысынан үлкен болса, олар орын ауыстырады. Бір өтуде ең үлкен элемент судағы көпіршік сияқты ең соңына қалқып шығады. Таңдау арқылы сұрыптау басқаша әрекет етеді: әлі орналастырылмағандардың ішінен ең кіші элементті іздеп, оны басына қояды. Ал ретсіздікті инверсиялармен — үлкені кішісінен сол жақта тұрған жұптармен өлшеген ыңғайлы: ретсіз тұрған көршілердің әр алмасуы дәл бір инверсияны жояды, сондықтан көпіршік массивте қанша инверсия болса, дәл сонша алмасу жасайды.
Аздап тарих
Машиналар деректерді компьютерлер пайда болмай тұрып-ақ сұрыптай бастаған. Өнертапқыш Герман Холлерит перфокарталарды және оларды санап, жәшіктерге бөліп салатын электр машиналарын ойлап тапты — олардың көмегімен бір мың сегіз жүз тоқсаныншы жылғы Құрама Штаттардағы халық санағы қолмен өңдегеннен әлдеқайда тез өңделді. Холлериттің фирмасы кейін біз Ай-би-эм деп білетін компанияның бөлігіне айналды.
Практикада не істейміз?
Ал енді практикалық тапсырманы орындап көрейік. Алдыңда сегіз саннан тұратын тізім — бес, екі, жеті, бір, сегіз, үш, алты, төрт — бағаналар түрінде тұр, әрқайсысының биіктігі оның мәніне тең. Көрші бағаналардың арасында екі бағыттауышы бар батырмалар бар: бассаң — көршілер орын ауыстырады. Сенің мақсатың — бағаналарды солдан оңға қарай өсу ретімен тізу, оның үстіне бірде-бір артық алмасусыз: тек сол жақ бағанасы оң жақтағысынан биік жұпты ғана ауыстыр. Қазір массивте он үш инверсия бар, әр дұрыс алмасу сайын бұл санауыштың қалай азайып жатқанын бақыла — демек, барлығы дәл он үш алмасу қажет болады. Егер бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, мен жауап беремін. Уайымдама, сенің бәрі де қолыңнан келеді.