ЖЫЛДАМ СҰРЫПТАУ АЛГОРИТМІ

Жылдам сұрыптау алгоритмі

Орындаған: Тексерген:

Массивтерді сұрыптау

Сұрыптау - қазіргі заманда мәліметтерді өңдеу процесінің ең кең тараған түрлерінің бірі. Сұрыптау деп - массив элементтерін белгіленген ережелер бойынша орналастыру болып табылады.

Мысалы, массивті өсуі немесе кемуі бойынша сұрыптау.

Массивтерді сұрыптау - алгоритмдеріне қойылатын басты талап - жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі) . Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау) .

Жиымдарды сұрыптау жылдамдығы әр түрлі болады.

Қарапайым сұрыптау тәсілдері n*n рет салыстыруды керек етеді, мұндағы n - жиым элементтері саны; ал жылдам сұрыптау тәсілі n*ln(n) рет салыстыруды қажет етеді.

Жылдам сұрыптау алгоритмі

Сұрыптау түрі сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдетеді.

Жылдам сұрыптау - ең тезі және ең жақсысы болып табылады.

Жылдам сұрыпталу - бөліктеу арқылы есептеледі.

Мәліметтерді тез сұрыптауға мүмкіндік беретін алгоритм, сандық мәліметтерді өсу реті бойынша немесе мәтіндік мәліметтерді алфавит ретімен орналастыру.

Алгоритм тізіммен берілген әрекетті орындайды және тізімнің әр жерінде орналасқан мәліметтерді салыстырады.

Бірнеше жүз элементтен тұратын айтарлыктай үлкен тізімдер үшін қолданылады.

Жылдам сұрыптау

Жылдам сұрыптау - алмасу принципіне негізделген жетілдірілген сұрыптау әдісі. Көпіршікті сұрыптау барлық тікелей сұрыптау алгоритмдерінің ең тиімсіздігі болып табылады. Дегенмен жақсартылған алгоритм - массивтерді сұрыптаудың ең жақсы белгілі әдісі. Оның керемет қасиеттері бар, оның өнертапқышы Х. Хоаре оны жылдам сұрыптау деп атады.

Ең үлкен тиімділікке қол жеткізу үшін үлкен қашықтыққа элементтерді айырбастау қажет. Жиымда шешімді шешетін элемент таңдалады. Содан кейін массивтің орнына орналастырылады, онда барлық элементтердің реттелуінен кейін болуы керек. Шешім элементіне қолайлы орын табу үдерісінде элементтің перестанциялары сол жақтан шешілетін элементтерден аз, ал оң жақта үлкен (бұл массив өсу тәртібімен реттеледі деп болжанады) етіп жасалады.

Массив екі бөлікке бөлінеді:

Рұқсат етілмейтін элементтің сол жағына сұрыпталмаған элементтер;

Рұқсат етілмейтін элементтің оң жағында сұрыпталмаған элементтер.

Осы екі кішігірім подмассивті сұрыптау үшін алгоритм рекурсивті түрде өзін шақырады.

Егер бірнеше элементті сұрыптағыңыз келсе, сізге қажет

массивтің рұқсат етілетін элементін таңдаңыз;

Массивті оның элементтін соңғы орынға орналастыру арқылы қайта реттейді;

Рұқсат етілгеннің сол жағындағы элементтерді рекурсивті түрде қайта сұрыптау;

Рұқсат етілгеннің оң жағындағы элементтерді рекурсивті түрде қайта сұрыптау.

Жылдам сұрыптаудың негізгі элементі - қайта жоспарлау алгоритмі.

Массив үлгісінде сұрыптауды қарастырайық:

10, 4, 2, 14, 67, 2, 11, 33, 1, 15.

Ретін өзгерту алгоритмін қолдану үшін left көрсеткішін массивтің шеткі сол элементіне қолданамыз. Көрсеткіш оңға қарай жылжиды, ол көрсеткен элементтер рұқсат берушіден аз қалмайынша. Right көрсеткішін массивтің шщеткі оң элементіне қойып, ол солға жылжытады, ал көрсететін элементтер рұқсат берушіден жоғары болады.

Шеткі сол элемент - рұқсат етуші pivot болсын. Left көрсеткішін келесі элементке орнатыңыз; right - соңғы.

Алгоритм 10 элементінің дұрыс орналасуын анықтайды және дұрыс емес орналасу элементтерін ауыстырады.

Көрсеткіштің қозғалысы шешуші элементке қатысты орналасу тәртібі дұрыс емес элементтері болған кезде тоқтайды.

Көрсеткіш left 10-нан жоғары элемент көрсетпейінше жылжиды; right 10-нан кіші элемент көрсетпейінше жылжиды.

Бұл элементтер орын ауыстырады және көрсеткішінің қозғалысы қайта басталады.

Процесс right left-тің сол жағында болмайынша жалғасады.

Осы арқылы рұқсат етуші элементінің дұрыс орналасуын анықтайды.

Си тілінде жылдам сұрыптау алгоритмін іске асыру

right-ты көрсететін, рұқсат етілген элемент пен элементтің орналасуы орындалады.

Шешім элементі дұрыс жерде орналасқан: оның сол жағындағы элементтер кіші мәндерге ие; оң жақта - үлкен. Алгоритм солардың сол жағына және сол жаққа субархивтерді сұрыптауға арналған.

include

#include

// Функция быстрой сортировки

void quickSort(int *numbers, int left, int right)

{

int pivot; // разрешающий элемент

int l_hold = left; //левая граница

int r_hold = right; // правая граница

pivot = numbers[left] ;

while (left < right) // пока границы не сомкнутся

{

while ((numbers[right] >= pivot) && (left < right) )

right--; // сдвигаем правую границу пока элемент [right] больше [pivot]

if (left != right) // если границы не сомкнулись

{

numbers[left] = numbers[right] ; // перемещаем элемент [right] на место разрешающего

left++; // сдвигаем левую границу вправо

}

while ((numbers[left] <= pivot) && (left < right) )

left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]

if (left != right) // если границы не сомкнулись

{

numbers[right] = numbers[left] ; // перемещаем элемент [left] на место [right]

right--; // сдвигаем правую границу вправо

}

numbers[left] = pivot; // ставим разрешающий элемент на место

pivot = left;

left = l_hold;

right = r_hold;

if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива

quickSort(numbers, left, pivot - 1) ;

}

int main()

{

int a[10] ;

// Заполнение массива случайными числами

for (int i = 0; i<10; i++)

a[i] = rand() % 20 - 10;

// Вывод элементов массива до сортировки

for (int i = 0; i<10; i++)

printf("%d ", a[i] ) ;

printf("\n") ;

quickSort(a, 0, 9) ; // вызов функции сортировки

// Вывод элементов массива после сортировки

for (int i = 0; i<10; i++)

printf("%d ", a[i] ) ;

printf("\n") ;

getchar() ;

return 0;

} Орындалу нәтижесі

Жылдам сұрыптау

1960 жылы МСУ-да жұмыс істеген кезде ағылшын тілінің компьютерлік зерттеушісі Чарльз Хоар әзірлеген танымал сұрыптау алгоритмі, әдетте qsort (әдеттегі C кітапханасында аты бойынша) деп аталатын жылдам сұрыптау, хоор сұрыптауы.

Массивтерді сұрыптауға арналған ең танымал әмбебап алгоритмдердің бірі: {\ displaystyle O (n \ log n) } O (n \ log n) элементтеріне тапсырыс беру кезінде алмасу; Іс жүзінде бірқатар кемшіліктердің болуына байланысты ол әдетте кейбір өзгерістермен қолданылады.

Сипаттамасы

QuickSort - тікелей айырбастау әдісімен (оның нұсқалары «Bubble sorting» және «Shaker sorting» ретінде белгілі) сұрыптау алгоритмінің айтарлықтай жақсартылған нұсқасы, сонымен қатар оның тиімділігі төмен екендігімен белгілі.

Басты айырмашылығы, ең алдымен, ауыстыру ең үлкен қашықтықта жүргізіледі және кейін элементтер екі тәуелсіз топқа бөлінеді. Қызықты факт: ең тиімсіз тікелей сұрыптау әдісін жетілдіру ең тиімді әдістердің біріне әкелді.

Алгоритмнің жалпы идеясы келесідей:

Сілтеме деп аталатын жиымнан элементті таңдаңыз. Ол массивтің кез келген элементтері болуы мүмкін. Алгоритмнің дұрыстығы элементті таңдауға байланысты емес, бірақ кейбір жағдайларда оның тиімділігі қатты төмендеуі мүмкін.

Массив бір-бірінің артынан кейін үш үздіксіз бөлікке «кіші сілтеме», «тең» және «үлкен» бөлу үшін барлық қалған элементтерді салыстырыңыз және оларды массивте қайта реттеңіз.

«Кішігірім» және «үлкен» мәндерді бөлу үшін, рекурсивті түрде қайталану операциялар тізбегін орындаймыз, егер бөліктің ұзындығы бірліктен үлкен болса, .

Іс жүзінде, массив әдетте үш емес, екі бөлікке бөлінеді: мысалы, «кішірек қолдау» және «тең және үлкен»; Мұндай тәсіл әдетте жалпы жағдайда тиімдірек болады, өйткені бөлу алгоритмін жеңілдетеді

Хоар бұл әдісті машиналық аудару үшін әзірледі; сөздік магниттік таспада сақталды және өңделген мәтіннің сөздерін сұрыптау таспаның бір айналымында аудармаларын кері қайтарусыз алуға мүмкіндік берді. Алгоритм Хоардың Кеңес Одағында болған кезінде ойлап тапты, онда Мәскеу университетінің компьютерлік аудармасында оқыды және орысша-ағылшынша сөзбе-сөз дамытты.