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

Презентация қосу

АЛГОРИТМІ

Ор
Те ын
кс д
ер ағ
ге ан:
н: __
__ __ _
__ __
__ __
ЖЫЛДАМ СҰРЫПТАУ

__ __
__ __
__ __
__
_
Массивтерді сұрыптау
Сұрыптау – қазіргі заманда мәліметтерді өңдеу
процесінің ең кең тараған түрлерінің бірі. Сұрыптау деп –
массив элементтерін белгіленген ережелер бойынша
орналастыру болып табылады.
Мысалы, массивті өсуі немесе кемуі бойынша сұрыптау .
Массивтерді сұрыптау – алгоритмдеріне қойылатын
басты талап – жадтың экономды пайдаланылуы.
Элементтерді 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-ты көрсететін, рұқсат етілген элемент пен элементтің
орналасуы орындалады.

Шешім элементі дұрыс жерде орналасқан: оның сол
жағындағы элементтер кіші мәндерге ие; оң жақта - үлкен.
Алгоритм солардың сол жағына және сол жаққа
субархивтерді сұрыптауға
Си тілінде жылдам арналған
сұрыптау .
алгоритмін іске асыру
1 include
2 #include
3 // Функция быстрой сортировки
4 void quickSort(int *numbers, int left, int right)
5 {
6 int pivot; // разрешающий элемент
7 int l_hold = left; //левая граница
8 int r_hold = right; // правая граница
9 pivot = numbers[left];
10 while (left < right) // пока границы не сомкнутся
11 {
12 while ((numbers[right] >= pivot) && (left < right))
13 right--; // сдвигаем правую границу пока элемент
[right] больше [pivot]
14 if (left != right) // если границы не сомкнулись
15 {
16 numbers[left] = numbers[right]; // перемещаем элемент
[right] на место разрешающего
17 left++; // сдвигаем левую границу вправо
18 }
19 while ((numbers[left] <= pivot) && (left < right))
20 left++; // сдвигаем левую границу пока элемент [left]
меньше [pivot]
21 if (left != right) // если границы не сомкнулись
22 {
23 numbers[right] = numbers[left]; // перемещаем элемент
[left] на место [right]
24 right--; // сдвигаем правую границу вправо
25 }
26 }
27 numbers[left] = pivot; // ставим разрешающий элемент на
место
28 pivot = left;
29 left = l_hold;
30 right = r_hold;
31 if (left < pivot) // Рекурсивно вызываем сортировку для
левой и правой части массива
32 quickSort(numbers, left, pivot - 1);
33 }
34 int main()
35 {
36 int a[10];
37 // Заполнение массива случайными числами
38 for (int i = 0; i<10; i++)
39 a[i] = rand() % 20 - 10;
40 // Вывод элементов массива до сортировки
41 for (int i = 0; i<10; i++)
42 printf("%d ", a[i]);
43 printf("\n");
44 quickSort(a, 0, 9); // вызов функции сортировки
45 // Вывод элементов массива после сортировки
46 for (int i = 0; i<10; i++)
47 printf("%d ", a[i]);
48 printf("\n");
49 getchar();
50 return 0;
51 } Орындалу нәтижесі
Жылдам сұрыптау
1960 жылы МСУ-да жұмыс істеген кезде ағылшын тілінің
компьютерлік зерттеушісі Чарльз Хоар әзірлеген танымал
сұрыптау алгоритмі, әдетте qsort (әдеттегі C
кітапханасында аты бойынша) деп аталатын жылдам
сұрыптау, хоор сұрыптауы.
Массивтерді сұрыптауға арналған ең танымал әмбебап
алгоритмдердің бірі: {\ displaystyle O (n \ log n)} O (n \ log n)
элементтеріне тапсырыс беру кезінде алмасу; Іс жүзінде
бірқатар кемшіліктердің болуына байланысты ол әдетте
кейбір өзгерістермен қолданылады.
Сипаттамасы
QuickSort - тікелей айырбастау әдісімен (оның нұсқалары
«Bubble sorting» және «Shaker sorting» ретінде белгілі)
сұрыптау алгоритмінің айтарлықтай жақсартылған
нұсқасы, сонымен қатар оның тиімділігі төмен екендігімен
белгілі.
Басты айырмашылығы, ең алдымен, ауыстыру ең үлкен
қашықтықта жүргізіледі және кейін элементтер екі
тәуелсіз топқа бөлінеді. Қызықты факт: ең тиімсіз тікелей
сұрыптау әдісін жетілдіру ең тиімді әдістердің біріне
әкелді.
Алгоритмнің жалпы идеясы келесідей:
Сілтеме деп аталатын жиымнан элементті таңдаңыз. Ол
массивтің кез келген элементтері болуы мүмкін.
Алгоритмнің дұрыстығы элементті таңдауға байланысты
емес, бірақ кейбір жағдайларда оның тиімділігі қатты
төмендеуі мүмкін.
Массив бір-бірінің артынан кейін үш үздіксіз бөлікке «кіші
сілтеме», «тең» және «үлкен» бөлу үшін барлық қалған
элементтерді салыстырыңыз және оларды массивте
қайта реттеңіз.
«Кішігірім» және «үлкен» мәндерді бөлу үшін, рекурсивті
түрде қайталану операциялар тізбегін орындаймыз, егер
бөліктің ұзындығы бірліктен үлкен болса,.
Іс жүзінде, массив әдетте үш емес, екі бөлікке бөлінеді:
мысалы, «кішірек қолдау» және «тең және үлкен»; Мұндай
тәсіл әдетте жалпы жағдайда тиімдірек болады, өйткені
бөлу алгоритмін жеңілдетеді
Хоар бұл әдісті машиналық аудару үшін әзірледі; сөздік
магниттік таспада сақталды және өңделген мәтіннің
сөздерін сұрыптау таспаның бір айналымында
аудармаларын кері қайтарусыз алуға мүмкіндік берді.
Алгоритм Хоардың Кеңес Одағында болған кезінде ойлап
тапты, онда Мәскеу университетінің компьютерлік
аудармасында оқыды және орысша-ағылшынша сөзбе-сөз
дамытты.
algorithm partition(A, lo, hi) is
pivot := get_pivot(A, lo, hi)
i := lo
j := hi
while i <= j do
while A[i] < pivot do
i := i + 1
while A[j] > pivot do
j := j - 1
if i <= j then
swap A[i] with A[j]
i := i + 1
j := j - 1
return I
Мұнда A массасы сілтеме бойынша берілсе, яғни сұрыптау
«бір орында» орын алады және танылмаған функция
get_pivot сілтеме элементінің мәнін қайтарады.
Артықшылықтары:
Жалпы мақсаттағы ішкі сұрыптау алгоритмдерінің ең
жылдамы (іс жүзінде).
Іске асыру оңай.
Оның жұмысы үшін {\ displaystyle O (\ log n)} O (\ log n)
қосымша жады қажет. (Жадтың ең жаман жағдайында
{\ displaystyle O (n \ log n)} O (n \ log n) жетілдірілмеген
рекурсивті алгоритм)
Кэштеу және виртуалды жад механизмдерімен жақсы
бірігеді.
Табиғи параллелдеуге мүмкіндік береді (бөлінген
субаррядтарды бір мезгілде жұмыс істейтін
субпроцесстерде сұрыптау).
Бірнеше кілтпен сұрыптау үшін тиімді модификацияға
мүмкіндік береді(атап айтқанда, Sedgewick алгоритмі
жолдарды сұрыптау үшін) себебі, бөліну процесінде
автоматты түрде тірекке тең элемент бөлігі таңдалады,
бұл бөлікті дереу келесі кілтпен сұрыптауға болады .
Байланыстырылған тізімдер және кез-келген жүйеге
қол жеткізе отырып, басынан бастап аяғына дейін және
соңынан басталуына мүмкіндік беретін басқа
Кемшіліктері:
o Кіріс деректері сәтсіз болғанда, жылдамдық бойынша
ең нашар немесе соган жақын жағдайда тез төмендейді
(\ displaystyle O (n ^ {2}) дейін} O (n ^ {2}).
o Екі рекурсивті қоңыраумен функция ретінде тікелей
іске асыру стека толып кету қателігіне алып келуі
мүмкін, себебі ең нашар жағдайда, {\ displaystyle O (n)} O
(n) кірістірілген рекурсивті қоңыраулар жасау қажет
болуы мүмкін.
o Тұрақсыз.
Тірек элементін таңдау
Ертерек іске асыру кезінде, әдетте, бірінші элемент
сортталған массивтерде өнімділікті төмендететін сілтеме
ретінде таңдалған. Орташа, кездейсоқ элемент немесе
(үлкен массивтер үшін) тиімділікті арттыру үшін бірінші,
орта және соңғы элементтердің медианы таңдауға
болады. Барлық тізбектің ортасы оңтайлы тірек элементі
болып табылады, бірақ оның есептеуі сұрыптауда
пайдалану үшін тым ауыр.

Ұқсас жұмыстар

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

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

Ауыстыру арқылы сұрыптау

Көпіршікті сұрыптау

Мәліметтерді шейкер әдісімен сұрыптау

Алгоритмдер туралы түсінік. Алгоритм күрделілігі

Таңдау арқылы сұрыптау

Алгоритм туралы мәлімет

Бір өлшемді массивтерді сұрыптау

Пирамидалық сұрыптау

Пәндер