ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ
ТҰРАР РЫСҚҰЛОВ атындағы ҚАЗАҚ ЭКОНОМИКАЛЫҚ УНИВЕРСИТЕТІ
Кафедра «Қолданбалы информатика»
Реферат
Тақырыбы: Іздеу және сұрыптау алгоритімдері
Орындаған: Қожахметов Ш
Мамандығы: ИЭФ 104 — топ
Тексерген: Жұмажанов Б.Ж.
АЛМАТЫ 2008
Іздеу алгоритмі
Барлық әдістерді статикалық және динамикалық деп қарастыруға болады. Массивтен статикалық әдіспен іздеу кезінде оның мәндері өзгермейді. Массивтен динамикалық әдіспен іздеу кезінде оның өлшемі өзгеруі мүмкін, себебі ол қайтадан сұрыпталады. Біз көбінде статикалық әдісті қолданамыз, үйткені мәтіндік редактордағы сөздерді өзгерте алмаймыз, ал динамикалық тәсіл ойын құрғанда пайдаланылады.
Іздеу әдістерін сондай-ақ нақты кілттерді пайдаланатын және туындаушы кілттерді пайдаланатын деп екіге бөледі. Бұл жағдайда кілт деп өзіміз іздеп отырған сөзді айтады. Мәтіндік редакторға қолданылатын кілт – туындаушы болып табылады, себебі ізделінетін массив алдын-ала алфавит бойынша сұрыпталған. Бұл рет іздеуді жеңілдету үшін пайдаланылады.
Кейбір кітаптарда бұл әдіс «экстраполяция әдісі» деп аталады. Экстарполяция – берілген интервалдан тыс бірнәрсені анықтау әдісі, ал интерпояция – сол интервал аралығына анықтау әдісі. Сондықтан да «экстраполяция әдісі» деп атау қате, үйткені ізделінетін сөзді шекарадан тыс аумақта іздеу мүмкін емес.бұл әдісті сипаттамас бұрын сізге ағылшын тіліндегі «treasure» сөзінің аудармасы қажет болды дейік. Яғни сіздің алдыңызда тапсырма – осы сөзді сөздіктен іздеу. Біздің келесі іс-әркеттеріміз қандай да бір іздеу алгоритмін құрумен жалғасады. Ізделінетін сөзді алфавит бойынша сұрыпталған массивтен іздейміз, ал керекті сөз бізге белгілі. Оны тез арада тауып алуға болады. Енді осы іздеуге толығымен тоқталайық. Бізге керекті сөз «т» әрпінен басталады, яғни алфавиттің екінші бөлігінде, немесе біз ол қандай орында тұрғанында шамамен есептеп ала аламыз. Яғни қанша дым жасауға болатынын анықтап аламыз. Егер ізделінетін массив үлкен болса осы әдіс арқылы оның шекрасын көрсетіп, тек осы аралықты ғана іздеуге болады. Ол үшін келесідей ек теңдік аламыз:
T1=M*N;
T2=2M*Log(2)N+N*Log(2)N;
N – массивтегі элементтердің саны.
M – рет іздеуге болады.
Тура ауытырудың алгоритмі жасайтын операция саны M*N-ге тең. Ал сұрыптауға кететін уақыт N*Log(2)N-ге тең, оған тағы 2M*Log(2)N дихотомия әдісін қосамыз. T1=T2 кезінде екі алгоритм де тиімді шекарада боламыз.
Алдымен linearsearch (сызықты іздеу) деген шағын порграмма құрастырайық. Оның үш параметрі болады: Strings – жолдың өрнектер қптпры, newstring – жолдың өрнек, осыны іздеу қажет және size – қаралатын қатардың элемпенттер саны.
Біздің басты программамызда екі тип анықталған және оларды біз linearsearch-ң
формальді параметрін баяндауда қолданамыз:
Type StrType=String[20]
ArrayStrType=Array[1..100] Of StrType;
Енді біз шағын прогарамманың басын жаза аламыз:
Function linearsearch(Strings:ArrayStrType; NewString:String;
Size:Integer):Integer;
String қатарынынң әр элементі NewString – пен салыстырылады. Егер де мәндері сәйкес келсе, онда табылған элементтің позийиясы (индексі) қайтарылады. Ал егер NewString – ті барлық элементтермен салыстырып болған соң, керекті жолдың өрнек табылмаса, онда 0 мәні қайтарылады, бұл – іздеуден түк шықпады деген сөз. Сипатталған процессте барлық элементтер кезекпен салыстырылады. Сондықтан бұл әдісті сызықты немесе тізбектелген іздеу әдісі деп атайды.
әр элемент Strings жодың өрнегінде бір-бірден кездеседі деп ойлайық(егер бұлай болмаса, онда олардың бірінші рет кездескендерін белгілеп отырамыз). Егер элемент табылса, әрі қарай процесс тоқтатылады, сондықтан логикалық Found айнымалысын енгізейік:
Var position:Integer;
Found:Boolean;
Begin
Position:=1;
Found:=False;
While (not Found) And (position=size) Do
Begin
If Strings [position]=NewString Then
Begin
Linearsearch:=position;
Found:=True;
End; {If…Then}
Position:=position+1;
End; {While циклінің соңы}
If not Found Then linearsearch:=0;
End; {linearsearch}
Егер сіз көңіл аударсаңыз, While циклі мына екеуінің біреуі орындалмағанша жүре береді: not Found өрнегі жалған болмағанша не position мәні size-дан асып кетпегенше.
LinearSearch функциясының қолданылуы.
Біздің linearsearch функциямызда басты программада қалай қолдануға болады? Мысалы, n соңды аттардан тұратын қатарда іздеу жүргізу керек болсын, осы мақсатпен басты программада names қатары баяндалған, сонымен қатар ізделінді есімді сақтайтын NewName айнымалысы да баяндалған. Онда LinearSearch функциясын шақыратын программа үзіндісі былай болады:
Type StrType=String[20];
ArrayStrType=Array[1..100] Of StrType;
Var Names:ArrayStrType;
NewName:StrType;
N,location:Integer;
…….
Location:=linearsearch(names,n);
If location>0
Then WriteLn(NewName,’орны’,location)
Else WriteLn(newName,’табылған жоқ’)
Сұрыптау алгоритмі
Сұрыптаудың Шелл әдісі бойынша сұрыптау, Хоар әдісі бойынша сұрыптау, таңдап сұрыптау сияқты түрлері бар.
Сұрыптау дегеніміз—берілген жиынның элементтерін белгілі бір ережелерге сәйкес орналастыру. Оның негізгі көздеген мақсаты – сұрыпталған жиыннан керек элементтерді іздеуді жеңілдету. Сұрыптауды көбіне массивтерді және файлдарды сұрыптағанда көп қолданады. Бұл екеуін әдетте ішкі және сыртқы сұрыптаулар деп атайды. Массивтер “ішкі” (жедел) жадыда орналасатындықтан, ішкі сұрыптау болады. Бұл жадыға тез қатынаймыз, ал файлдар бұдан бәсеңдеу, бірақ сыйымдылығы үлкендеу “сыртқы” жадыда, яғни есте сақтау құрылғыларында (диск, лента т.б.) сақталатындықтан, оны сыртқы сұрыптау деп атаймыз.
Іздеу әдістерінің де әдістері бір-бірімен қатты байланысқан. Әсіресе, біз бинарлы әдісті, егер қатарымыз сұрыпталған болса, тинтен қолдана алмаймыз. Мысалы, біз бинарлы іздеу әдісін миллиондаған фамилияларды іздеген кезде қолданамыз. Ал ол кітапшадағы фамилиялар алфавит әріптері бойынша сұрыпталған. Яғни, іздеу бар жерде сұрыптау міндетті түрде болу керек.
Тағы сұрыптаудың орналастыру арқылы сұрыптау түрі бар. Бұл әдістің негізгі мәні алдыңғы реттелген элементтерге соңғы элементтерді бір-бірлеп қосып отыруда. Әрине, бұл сұрыптаумен танысқан адам, көп уақытқа созылатын процесс деп ойлауы мүмкін. Бірақ олай емес, өйткені алдыңғы элементтер сұрыпталған күйде болады да, келесі элементті сәйкес кез-келген жерге қоямыз.
Орналастыру әдісі арқылы сұрыптау.
Бұл әдістің негізгі мәні алдыңғы реттелген элементтерге соңғы элементтерді бір-бірімен қосып отыруда. Бірінші қадамға алғашқы екі элемент сұрыпталады. Содан кейін осы екі элементпен салыстырылып, сәйкес орынға үшінші элемент орналастырылады. Үш сұрыпталған элементтерге төртінші элементті қосамыз. Ол жаңа төрттіктегі өз орнына жайғасады. Сөйтіп, сұрыпталған n-1 элементтерге соңғы n-ші элемент қосылғанша жалғаса береді. Осы әдіске мысал ретінде мына процедураны қарастырайық:
Procedure ins(var x:Array Of Integer; n:Integer);
Var i,j,t:Integer;
Begin
For i:=1 To n-1 Do
Begin
T:=x[i];
J:=i-1;
While (j>=0) And (t<x[j]) Do
Begin
X[j+1]:=x[j];
j:=j-1;
end;
x[j+1]:=t;
End;
End;
Сыртқы сұрыптау
Тура бірігу
Кезекті а1,а2,…,аn жазбалардан тұратын А файлы бар дейміз. Әрбір жазба тура бір элементтен тұрады деп алайық. Сұрыптау үшін екі қосалқы В және С файлы (оның әрқайсысының көлемі n/2 –ге тең болады) пайдаланылады. Сұрыптау қадамдардың жүйелілігінен құралады, оның әрқайсысында А файлынан В және С файлдарына үлестіру орындалады, ал одан кейні В және С файлдардың А файлына бірігуі орындалады. Бірінші қадамда үлестіруге А файлы оқылады да, а1,а3,…а(n-1) жазбалары В файлына жазылады, ал а2,а4,…,аn жазбалары С файлына жазылады (бастапқы үлестіру). Бастапқы бірігу (a1, a2), (a3, a4), …, (a(n-1), an) парлары бойынша істелінеді, нәтижесі А файлына жазылады. Екінші қадамда А файлы жүйелі түрде қайтадан оқылады да, В файлына тақ нөмірлі жүйелі парлар жазылады, ал С файлына жұптар жазылады. Бірігу кезінде А файлына жазбалардың реттелген төрттіктер құрылады және жазылды. Тағы сол сияқты. Ең соңы қадамды орындағаннан бұрын, А файлының ішінде әрбір n/2 өлшемдіекі реттелген қосалқы жүйелері болады. Үлестіру кезінде оның біріншісі В файлына, ал екіншісі С файлына келеді. Бірігуден кейін А файлында жазбаның түгелімен реттелген жүйесі болады.
Кәдімгі бірігу
Тура бірігу тәсілін пайдаланған кезде, бастапқы файлдың сұрыпталуы мүмкін екені саналмаған. Серия – бұл ai, a(i+1), …, aj жазбаларының қосалқы жүйелігі деп аталады, мұндағы ak <= a(k+1) бәрі үшін i <= k < j, ai < a(i-1) және aj > a(j+1).Тура бірігу жағдайында, сұрыптау бірнеше қадамдарға дейін орындалады да, әрбіреуінің біріншіден А файлының В және С файлдары бойынша үлестірілуі орындалады да, содан соң А файлына В және С файлдарына бірігуі. Үлестіру кезінде жазбаның бірінші сериясы оқылады да, В файлына көшіріледі, ал екінші — С файлына т.с.с. Бірігу кезінде В файлындағы жазбалардың бірінші сериясы С файлының бірінші сериясымен бірігеді де, В –ның екінші сериясы С ның екінші сериясымен бірігеді және т.с.с. Егер де бір файлының қарауы басқа бір файлының қарауынан бұрын аяқталса, онда қаралмаған файлдың қалдығы түгелімен А файлының соңына көшіріледі. А файлында бір ғана серия қалғанда процесс аяқталады. Файлдарды сұрыптау 3.1 және 3.2 суреттерінде көрсетілген
Бөлу сұрыптауы
(Quicksort)
Бұл тәсіл ауыстыру тәсілінің дамуы болып табылады. Ол эффектілі болғаннан кейін, оны «тез сұрыптау тәсілі» (Quicksort) деп атаған. Оның негізгі идеясы Х массивінің кез-келген элементі таңданады да, осы массив a[i] (a[i]>X) элементі кездескенге дейін сол жағынан қарастырылады, одан кейін массив a[j] (a[j]<X) элементін кездескенге дейін оң жағынан қарастырылады. Осы екі элементтер орындарымен ауыстырылады да, қарау, салыстыру және ауыстыру процесстері Х элементке жеткенге дейін жалғастырылады. Нәтижесінде массив екі бөлікке бөлінеді: оң, оның кілттердің мәндері Х-тан кіші болады және сол, оның кілттерінің мәндері Х-тан үлкен болады. Осыдан кейін процесс рекурсивті түрде әрбір бөлікте бір ғана элемент болғанға дейін жалғастырылады.
