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

КІРІСПЕ
1. Сұрыптау тәсілдері
1.1 Хоар тәсілі
1.2 Пузырёк тәсілі
2 Іздеу
Қорытынды
Пайдаланылған әдебиеттер

Жаңа реттеулер енгізуден қиын, сәттілігі жағынан күдікті, жүзеге
асыруы жағынан қауіпті жұмыс жоқ .
Никколо Макьявелли (1513)

«Біз барлық автомобильдердің нөмірін қарастырып үлгермейміз»,- деді Дрейк. «Ал бізге оны істеп қажеті жоқ, Пол. Біз тек ғана оларды реті бойынша қойып,олардың бірдейлерін іздейміз».
“The Case of Angry Mourner” (1951)

Бұл айтылған пікірлердің барлығы программалаудың ең бір қажетті мүмкіндіктері сұрыптау мен іздеуге арналған. Сұрыптау мен іздеуді кез-келген программада қолдануға болады.олардың мүмкіндіктері шексіз. Осы мүмкіндіктерді пайдалана отырып, программа алгоритімін қарапайым жолмен жеңілдетуге болады. Негізінен сұрыптау мен іздеудің түрлері өте көп.
Кез-келген күнделікті жағдайда біз сұрыптау және іздеу үрдістерімен жұмыс жасаймыз. Әр адамда неліктен деген сұрақ туады. Жауап өте қарапайым. Себебі бұл үрдістермен жұмыс жасау өте ыңғайлы. Тіпті өзіміздің күнделікті қолданып жүрген персоналды компьютерімізде сол принциппен жұмыс істейді. Олар сіз енгізген мәліметтерді сұрыптап қояды да сіз оларды іздегенде лезде тауып бере қояды. Сұрыптау мен іздеу тәсілдерін кеңінен қолданады. Бұл тәсілдерді қарапайым студентте кәсіпқой программистте қолдана алады. Жалпы алғанда кез-келген программа сұрыптаудан басталады. Ал тез сұрыптап қажет элементті табу үшін сұрыптау және іздеу тәсілдерін жетік білген жөн. Сондықтан сұрыптау мен іздеу тәсілдерін қарастырып көрейік.

1. Уэит, Мартин Д. “Язык Си” М.:1988ж.
2. Мұртазина Ә.Ө., Сатпаева А.К. “Си тілінде программалаудың негіздері” Алматы: ҚазҰТУ, 2002ж.
3. Уиннер Р. “Язык Turbo C” М.:1991ж.
4. Культин Н. “C/C++” М:2001ж.
5. Вирт Н. Алгоритмы + структуры данных = программы: Пер. С англ.- М.: Мир, 1985. – 406б.

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

КІРІСПЕ

Жаңа реттеулер енгізуден қиын, сәттілігі жағынан күдікті,
жүзеге
асыруы жағынан қауіпті жұмыс жоқ .
Никколо
Макьявелли (1513)

Біз барлық автомобильдердің нөмірін қарастырып
үлгермейміз,- деді Дрейк. Ал бізге оны істеп қажеті жоқ, Пол. Біз тек
ғана оларды реті бойынша қойып,олардың бірдейлерін іздейміз.
“The Case
of Angry Mourner” (1951)

Бұл айтылған пікірлердің барлығы программалаудың ең бір
қажетті мүмкіндіктері сұрыптау мен іздеуге арналған. Сұрыптау мен іздеуді
кез-келген программада қолдануға болады.олардың мүмкіндіктері шексіз.
Осы мүмкіндіктерді пайдалана отырып, программа алгоритімін қарапайым
жолмен жеңілдетуге болады. Негізінен сұрыптау мен іздеудің түрлері
өте көп.
Кез-келген күнделікті жағдайда біз сұрыптау және іздеу
үрдістерімен жұмыс жасаймыз. Әр адамда неліктен деген сұрақ туады. Жауап
өте қарапайым. Себебі бұл үрдістермен жұмыс жасау өте ыңғайлы. Тіпті
өзіміздің күнделікті қолданып жүрген персоналды компьютерімізде сол
принциппен жұмыс істейді. Олар сіз енгізген мәліметтерді сұрыптап қояды да
сіз оларды іздегенде лезде тауып бере қояды. Сұрыптау мен іздеу тәсілдерін
кеңінен қолданады. Бұл тәсілдерді қарапайым студентте кәсіпқой
программистте қолдана алады. Жалпы алғанда кез-келген программа сұрыптаудан
басталады. Ал тез сұрыптап қажет элементті табу үшін сұрыптау және іздеу
тәсілдерін жетік білген жөн. Сондықтан сұрыптау мен іздеу тәсілдерін
қарастырып көрейік.

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

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

1.1 Хоар тәсілі

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

Жалпы алғанда сұрыптаудың түрлері өте көп. Оларды түгел
қарастырып шығу мүмкін емес. Сонда да мен осы курстық жобамда маңызды
деген бірнеше түрлерін қарастырып өтуді жөн көрдім. Яғни, жоғарыда аталып
өткен сұрыптау тәсілдерін толығырақ қарастырып өтейік.
Лездік сұрыптау немесе Хоар тәсілі. Сұрыптау алгоритімінің ең
тамаша бірі болып лездік сұрыптау (quicksort) болып табылады. Оның
құрастырушысы Чарльз Хоар, осы сұрыптау тәсілін 1962 жылы жарыққа
шығарды. Лездік сұрыптау арқылы қажет емес немесе артық есептеулерден
арылуға болады.сұрыптаудың осы түрімен жұмыс істегенде массивті екіге
бөлуге болады. Яғни, үлкен элементтерін бөлек, кіші элементтерін
бөлек. Содан кейін екі топты рекурсивті түрде сұрыптайды. Ал осы
үрдіс аяқталған кезде массив сұрыпталып бітеді. Хоар тәсілінің
алгоритімі өте қарапайым және өте тиімді. Оның бірнеше түрлері бар.
Төменде қарастырылатын түрі қолдануы жағынан өте жеңіл.
Біздің quicksort функциясы бүтін санды массивті сұрыптайды:

* quicksort : сұрыптайды v[ ]..v[n-1]
өсу бойынша * void quicksortClrrt
v[ ], int n)
➢ {
int i, last;
if (n=1) * ешнәрсе жасамау *
return;
swap (v, 0,rand() % n);
last=0;
for (i=1; in; i++) * бөліктегіш *
if (v[i] v[0])
swap (v, ++last, i);
swap ( v, 0, last ); * бөліктегішті сақтау *
quicksort ( v, last ) ; * рекурсивті
түрде сұрыптау*quicksort (v+last+ 1, n-last-1);
* барлық бөлігін * }

swap операциясы quicksort функциясында үш рет кездеседі, сондықтан оны
бөлек функция ретінде жазамыз.
* swap:
v[i] and v[j] * орындарын алмастырамыз *
void swap(int v[ ], int i , int j)
{ int temp;
temp =v[i]; v[i]=v[j]; v[j]=temp;
Массивті екіге бөлгенде біріншіден, оны бөлетін элемент таңдалады.
Ол уақытша массивтің басына қойылады да, массивтің қалған элементтері
қарастырылады. Массивті бөлетін элементтен кіші элементтер (яғни,
кішкентай элементтер ) массив басына қарай жылжытылады (last
позициясына). Ал үлкен элементтер массив соңына қарай жылжытылады (і
позицияға). Үрдістің басында бөлетін элемент орнын ауыстырғанан кейін
last=0 және i=1 ден n-1 ге дейінгі элементтер әлі қарастырылмаған
болады. Басында 1 ден last қа дейінгі элементтер бөлетін элементтер
қатаң түрде кіші, ал last+1 ден i-1 ге дейінгі элементтер оған тең
немесе үлкен. Ал і ден n-1 ге дейінгілер әлі қарастырылмаған. V[i] ='
V[0] шарты бірінші рет орындалғанша, алгоритм [i] элементін өз-өзіне
ауыстыра береді.
Барлық элементтер қарастырылып болған соң бөлетін элемент өзінің
соңғы позициясына жету үшін, о элемент last позиясына қойылады. ЕНді
массив мына түрде болады: Осы үрдіс массивтің оң жағына да сол
жағына да қолданылады. Үрдіс аяқталғанда массив толық сұрыпталған
болады.Бұл лездік сұрыптау қаншалықты тез жұмыс атқарады десек,оған
келесі түрде жауап беруге болады.Әдетте n элементтен тұратын массив
n2 элементтен тұратындай етіп 2 ге бөлінеді, одан әрі n2 элементтен
тұратын 2 топ әрқайсысы n4 элемент болатындай етіліп 4 топқа
бөледі,содан соң әр біреуінде n8 элемент болатындай етіп 8 топқа
бөлінеді, т.с.с.Үрдіс шамамен log2 n рет қайталанады.
1.2 Пузырёк тәсілі

Бұл тәсілдің басты мақсаты оның атауында. Яғни, массивтің ең “жеңіл”
элементтері көтеріледі, ал ең “ауыр” элементтері төмен түседі.
Алгоритмдік түрде оны келесі жағдайда көрсетуге болады:
Ол үшін массивті астынан үстіне қарай түгел қарастырамыз. Егер қарастыру
барысында “астынғы” элемент “үстінгі” элементке қарағанда кіші болса,
онда оларды ауыстырамыз. Осындай әдіспен массивтің ең ”кіші” элементін
жоғарыға шығарамыз. Содан кейін барлық үрдісті массивтің қалған
сұрыпталмаған N-1 элементтері үшін қайталаймыз (яғни, бірінші
элементтен төменгі элементтер үшін). Бұл сұрыптау тәсілінің алгоритімі
өте қарапайым болғандықтан өте тиімді..
Пузырек тәсілі. Сұрыптаудың ... жалғасы

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