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

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 8 бет
Таңдаулыға:

Жоспар

І. Кіріспе

ІІ. Негізгі бөлім

1. Алгоритмді сұрыптау.

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

3. Шелла әдісі

4. Хоорда әдісі

5. Берілгендер қоры

6. Сұрыптауға есептер.

ІІІ. Қорытынды

Алгоритм іріктеу

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

Сұрыптау программалаудың барлық облыстарында берілгендер базасында болсын немесе математикалық программалауда болсын шектеусіз қолданылады.

Сұрыптау алгоритімінің әрқайсысын 3 бөлікке бөлуге болады:

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

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

1. Көбік әдісі немесе пузирька әдісі.

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

Біз барлық массивті төменнен жоғарыға деп қарастырамыз және төменгі элемент «жоғарғы» элементтен аз болатындай етіп ауыстырамыз. Енді қалған сұрыпталмаған № - 1 элементтер үшін осыны қайталаймыз, яғни біріншіден төмен жатқандардан бастаймыз. Көріп отырғанымыздай алгоритм өте қарапайым және аса тиімді де емес.

Бұл әдіске қарағанда тиімді және көрнекі әдіс - екінші әдіс.

2. Таңдап сұрыптау әдісі

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

3. Шелла әдісі

Бұл әдіс 1959 жылы Donald Lewis Shall автрорларының ұсынуымен енгізілді.

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

4. Хоора әдісі

Бұл әдістің авторы Charles Antony Richard Hoare. Бұл әдіс 1962 жылы талданып тез сұрыптау әдісі деген атқа ие болды. Бұл әдістің негізі мынада: сұрыптауға жататын жиынның ішінен осы жиынды екі жиынға бөліп жіберетін элементті табу керек. Бұл идеяны түрлі әдістермен көрсетуге болады.

Сұрыптау - элементтердің тұрақтылығын кемімейтін (не өспейтін) тұрақтылыққа түрлендіру. Элементтердің тұрақтылығы {Аі} кемімейтін деп аталады, егер кез келген i және j үшін, i<j болғанда Аі< = Aj теңсіздігі орындалса.

Қатаң өспелі тізбектер үшін теңсіздік Аі < Aj түрге келеді.

Олимпиадалық есептерді шешуде берілгендерді сұрыптау өте қажет. Негізінен берілгендер N элементтен тұратын массив түрінде беріледі. Мұнда элементтер сандар мен қатарлардан тұрады. Берілген массивті элементтерді ауыстырып алгоритмнің бірнеше түрін қолдану керек екенін білу керек.

Есептің күрделілігі логарифмдік сызықтың, квадраттың, экспонициальный т. б. болуы мүмкін, оларды шешу үшін қажетті O (ln(N) ) ’, O(N), O (N ₂ ) және O (eN) операцияларын тиісінше орындау керек.

Ең жақсы қолдануға тиімді универсальды сұрыптау алгоритмі - O (n* ln (n) ), бұл алгоритм олимпиада есептерінде N = 300 000 массивті сұрыптауға мүмкіндік береді. Осындай алгоритмдердің қатарына мынадай сұрыптауларды жатқызуға болады: тез, пирамидалық, бинарлық ағаш. Сұрыптаудың қарапайым алгоритмі - O (N ₂ ), бұл N < = 5000 сұрыптау үшін есептер шешуге мүмкіндік береді.

Кейбір жағдайларда сызықтың тәртіптің күрделілігімен сұрыптауға болады, егер берілгендерде кейбір шектеулер бар болса (мысалы массив ішінара сортталған немесе элементтің диапозоны шектелген болса) . Осындай тәртіппен 107 элементтен тұратын массивті сұрыптауға болады. Мысалы: келесі алгоритмдер мынадай шешім береді: цифрлық және разрядтық.

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

Енді біз программистердің жиі қолданатын сұрыптау алгоритмдерін қарастырамыз.

a [i] - сандық массив, n элементтен тұратын, 1 -ден n - ге дейінгі индекспен белгіленген массивті сұрыптау алгоритімінің барлық мысалдарда қарастырамыз.

Талдау сұрыптау. Алдымен барлық элементтер арасындағы ең кішісін анықтап, 1 мен алмастырамыз, ары қарай қалғандарының ішінен тағы да ең кішісін тауып, екіншімен алмастырамыз Осылайша (n - 1) - ші элементке дейін алмастырамыз.

Шешу алгоритмі төмендегіше болады:

for I = 1…n - 1{

for j = I + 1… n{

if (a [i] > a [j] ) a [i] < > a [j] ;

}

Көбік сұрыптау. Бұл сұрыптау алгоритмін де алдыңғыға ұқсас, мұнда да керекті элементті біріншіден бастап соңғысына дейін позицировать етеміз. Керекті элементті өз позициясына қою көбікті еске түсіреді. Бірінші (ең кіші) элемент өз орнына тұру үшін массивпен оңға және солға жылжуы керек, қос - қостан көрші элементтерді солдан оңға қарай орын ауыстыратындай етіп салыстырамыз. Екінші элементті өз орнына қою үшін тағы да массив бойынша жүру керек, бірақ бірінші элементке емес, екінші элементке шейін т. с. сс

Берілген алгоритмді келесі түрде жазуға болады:

for i = 1… n - 1{

for j = n - 1 …i {

if (a [j] > a [j + 1] ) a [j] <> a [j +1]

}

Тез сұрыптау. Бұл алгоритм көбіне жиі қолданылатын алгоритмге жатады.

O (n* ln (n) ) күрделі тәртіппен жазылады.

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

Алгоритм мына түрде жазылады:

Sub Quick Sort (1, r) {

X= (1 + r ) div 2;

i = j; j = r;

do {

while (a[i] <p) i = i + 1

while (a[j] <p) j = j + 1

if (i < = j) {

a [i] < > a [j]

i = i + 1; j = j + 1;

}

} while (i < = j)

if (j > 1) Quick Sort (1, j) ;

if (r>i) Quick Sort (i, r) ;

}

Массивті сұрыптау үшін Quick Sort (1, n) (Время: 1 сек. Память: 16 Мб. Сложность:13%) . Сұрыптауды орындау үшін берілген уақытында, сағатында, минуты және секундында орындау керек.

Берілгендерге кіру

Input. TXT кіру файылында бірінші қатарда, N (1 < = N < = 100) саны жазылған, ал келесілерінде N қатардан N уақытына дейін жазылған. Әрбір уақыт аралығы 3 бүтін санмен есептеледі - сағаттар (0 - ден 23 - ке дейін), минуттар (0 - ден 59 - ға дейін), секундтар (0 - ден 59 - ға дейін) .

Берілгендерден шығу.

OUTPUT. TXT шығу файылында уақыт аралығын көрсету керек.

Мысалы:

№1

Input. TXT

102030

73000

235959

133030

OUTPUT. TXT

73000

102030

133030

235959

і) Сұрыптау реті сұрыптау группасының тізбегі болып саналады. Сұрыптау группасы - бұл қатарлар тізбегі. Сұрыптау группасы сұрыптау группасының тізбегі болуы мүмкін.

іі) Әрбір сұрыптау группасының тізбектер тығыздығы мен позиция реттілігі сұрыптау қатарларының мағынасымен анықталады.

ііі) Егер сұрыптау реті қосымша сұрыптау қатарларымен толықтырылса, онда бірліктен артық сандық қатармен берілген әрбір сұрыптау группасы сұрыптау группасының тізбегі болып табылады. Әрбір тізбектің тығыздығы мен әрбір сұрыптау группасының реттік позициясы келесі сұрыптау қатарларының мәні болады.

Айталық, кадрларға бөлінген лента бөлігі бар. Кадрлар екі жағынанда көмірленген. Лента Мекбус қағазына жапсырылған. Көрші кадрлар ретімен тұруы үшін алгоритм құру керек. Кадрларды қайта орналастырғанда сандар кадрдың екі жағынан да қойылатынын ескеру керек.

Екі кадр бар:

А1, В1 - кадрдың бір жағы

А2, В2 - екінші жағы

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.