Лекция · 3.8

Сұрыптау әдістері

Телефон кітапшасы неге әрдайым А-дан Я-ға қарай реттелген, ал спорттық жарыс кестесі — ұпай бойынша? Реттелген тізімнен керек нәрсені табу әлдеқайда ЖЕҢІЛ. Осы «реттеу» операциясының өзін компьютерге қалай үйретеміз? Бүгін массив элементтерін сұрыптаудың бірнеше классикалық алгоритмін үйренеміз — олардың әрқайсысының өз артықшылығы мен жылдамдығы бар.

Таңдау әдісімен сұрыптау

Анықтама
Сұрыптау — массив элементтерін белгілі бір заңдылықпен (өсу немесе кему тәртібімен) орналастыру процесі. Мақсаты — сұрыпталған массивтен керек элементті іздеуді жеңілдету.

Таңдау әдісі: сұрыпталмаған бөліктен ЕҢ КІШІ элемент табылып, ол сол бөліктің БІРІНШІ элементімен орын ауыстырады. Осылайша массивтің бірінші элементі сұрыпталады, содан кейін қалған (қысқарған) бөлікпен де солай істеледі.

Есеп (орта): таңдау әдісімен сұрыптау

Берілді: [49, 13, 92, 7, 71, 65, 83] массиві.

def sel_sort(array):
    for i in range(len(array) - 1):
        m = i
        j = i + 1
        while j < len(array):
            if array[j] < array[m]:
                m = j
            j = j + 1
        array[i], array[m] = array[m], array[i]

A = [49, 13, 92, 7, 71, 65, 83]
sel_sort(A)
print(A)

Жауабы: [7, 13, 49, 65, 71, 83, 92]

Көпіршікті әдіс

Массивті тік құрылым ретінде елестетсек, көпіршікті әдісте әрбір «өтуде» ЕҢ ЖЕҢІЛ көпіршік (ең кіші элемент) жоғары көтеріледі — сол себепті атауы осылай қойылған.

Анықтама
Көпіршікті сұрыптау (алмасу арқылы сұрыптау) — көршілес элементтер жұбы дәйекті түрде салыстырылып, ретсіз тұрса орындары ауыстырылады.

Есеп (орта): көпіршікті әдіспен сұрыптау

N = 7
A = [49, 13, 92, 7, 71, 65, 83]
for i in range(N - 1):
    for j in range(N - 2, i - 1, -1):
        if A[j] > A[j + 1]:
            A[j], A[j + 1] = A[j + 1], A[j]
print(A)  # [7, 13, 49, 65, 71, 83, 92]

Бұл әдісті ОҢТАЙЛАНДЫРУҒА болады: егер бір толық өту барысында ешбір алмасу болмаса, массив ТОЛЫҚ сұрыпталған дегенді білдіреді — циклды содан тоқтатуға болады.

def bubble(array, N):
    for i in range(N - 2):
        swapped = False
        for j in range(N - 2, i - 1, -1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                swapped = True
        if not swapped:
            break

💡

Тарихи атауы: толық сұрыптау үшін (n−1) рет өту қажет, ал жалпы салыстырулар саны n(n−1)/2-ге тең — сол себепті бұл әдіс кейде «алмастыру арқылы сұрыптау» деп те аталады.

Кірістіру мен жылдам сұрыптау

Кірістіру әдісінде массив шартты түрде реттелген және реттелмеген екі бөлікке бөлінеді; реттелмеген бөліктің әр элементі реттелген бөлікке КЕРЕК ОРНЫНА кірістіру арқылы қосылады.

def fast_insertion_sort(l):
    for i in range(1, len(l)):
        j = i - 1
        value = l.pop(i)
        while (j >= 0) and (l[j] > value):
            j -= 1
        l.insert(j + 1, value)
    return l

a = [16, 25, 24, 12, 11]
fast_insertion_sort(a)
print(a)  # [11, 12, 16, 24, 25]

Соңғы, ЕҢ ТИІМДІ алгоритм — жылдам сұрыптау (Quick Sort): массив ортасынан тірек элемент таңдалады, одан кіші элементтер сол жаққа, үлкені оң жаққа топтастырылады, содан кейін әр жарты бөлік РЕКУРСИВТІ түрде қайта сұрыпталады.

def qSort(A, p, q):
    if p >= q:
        return
    L, R = p, q
    X = A[(L + R) // 2]
    while L <= R:
        while A[L] > X:
            L += 1
        while A[R] < X:
            R -= 1
        if L <= R:
            A[L], A[R] = A[R], A[L]
            L += 1
            R -= 1
    qSort(A, p, R)
    qSort(A, L, q)

Алгоритм	N=100 үшін тексеру саны (шамамен)
Көпіршік / Кірістіру / Таңдау	~10 000 рет
Жылдам сұрыптау (Quick Sort)	~700 рет

⚡

Неге жылдам сұрыптау тезірек? Қарапайым әдістер (таңдау, көпіршік, кірістіру) БҮКІЛ массивті қайта-қайта аралайды (~N² амал). Ал жылдам сұрыптау есепті ЕКІГЕ бөліп, әр бөлікті ЖЕКЕ-ЖЕКЕ (кішірек көлемде) шешеді — бұл рекурсияның нақты пайдасы.

Дайын функциялар және іздеу

Өз алгоритміңді жазбай-ақ, Python-да ДАЙЫН сұрыптау функциялары бар:

Код	Түсініктеме
`B = sorted(A)`	A-ны сұрыптап, ЖАҢА B массивіне жүктейді
`A.sort()`	A-ның ӨЗІН реттейді (орнында)
`A.sort(reverse=True)`	Кему ретімен, орнында
`A.reverse()`	Ретті КЕРІ АЙНАЛДЫРАДЫ (сұрыптамайды!)

⚠️

Жиі шатастырылады: reverse() тек массивтің ретін теріске бұрады (соңын басына), ол сұрыптау ЕМЕС — мәндер бойынша реттемейді.

Ал элементті ІЗДЕУ үшін — сызықтық іздеу: массив элементтерін бірінен соң бірін берілген мәнмен салыстыру.

nomer = -1
for i in range(n):
    if mas[i] == x:
        print("mas[", i, "] = ", x, sep="")
        break
else:
    print("Tabylmady!")

💡

Python ерекшелігі: for циклінің де else бөлігі бола алады — ол ТЕК break қолданылмаған жағдайда орындалады. Бұл іздеу нәтижесін ықшам жазуға мүмкіндік береді.

🎯 ҰБТ байланысы

Сұрыптау алгоритмдерін қадам-қадаммен қолмен орындай білу — ЕНТ-те жиі кездесетін тапсырма.

Таңдау әдісі — ЕҢ КІШІНІ іздеп алдыға қояды; көпіршік — КӨРШІЛЕС жұптарды салыстырады.

sort() массивті ӨЗГЕРТЕДІ, sorted() ЖАҢА массив қайтарады.

reverse() — сұрыптау емес, тек ретті теріске бұру.

Сабақ қорытындысы

Сұрыптау — массивті белгілі тәртіппен реттеу, іздеуді жеңілдету үшін қажет.
Таңдау, көпіршікті, кірістіру әдістері қарапайым, бірақ баяу (~N²); жылдам сұрыптау (Quick Sort) рекурсиямен әлдеқайда тиімді жұмыс істейді.
Python-да sorted()/sort() дайын функциялары бар; reverse() сұрыптамайды, тек ретті бұрады.
Сызықтық іздеу — элементтерді бірінен соң бірін тексеру арқылы табу.