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

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

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ

СЕМЕЙ ҚАЛАСЫНДАҒЫ ШӘКӘРІМ АТЫНДАҒЫ УНИВЕРСИТЕТІ

Информатика және ақпаратттық технологичлар кафедрасы

СӨЖ

Тақырыбы: Сұрыптау есептері. Сұрыптау алгоритмдері.

Пәні:Мәліметтерді өңдеу құрылымы мен алгоритмі

Орындаған: Серікғалиева Е. .

Т-341(б)

Тексерген : Болсынбекова Ш. Ж.

Семей, 2015жыл

Жоспар:

1. Алгоритм және сұрыптау ұғымдарына түсініктеме.

2. Сұрыптау түрлері.

3. Сұрыптау есептері.

Алгоритм - қазіргі математикада, оның ішінде электронды есептеуіш машинада қолданылатын негізгі ұғымдардың бірі. Белгілі бір теңдеу түбірінің жуық мәнін кез келген дәлдікпен табу оған арналған Алгоритммен есептеледі. Компьютердің кең қолданылуына байланысты Алгоритм жаңа мағынаға ие болды. Берілген есепті шешу барысында орындаушыға біртіндеп қандай әрекеттер жасау керектігін түсінікті әрі дәл көрсететін нұсқау да Алгоритм деп аталады. Алогритмді орындаушы - адам, ЭЕМ немесе робот. Әрбір нұсқау - бұйрық. Ал орындаушының жүзеге асыра алатын бұйрықтар жиыны бұйрықтар жүйесі деп аталады. «Алгоритм» ұғымы информатикада ақпарат сияқты іргелі ұғымдар қатарына жатады. Алгоритм атауы атақты араб математигі Әбу Жафар Мұхаммед ибн Мұса әл-Хорезми ( 763-850 ж. ж) есімінің латынша Algorithmi (Алгоритми) болып жазылуына шыққан. Ол санаудың ондық жүйесінде көп орынды сандар мен арифметикалық амалдардың орындалу ережесін ұсынған. Бұл ережелер қосынды мен көбейтіндіні табуға арналған амалдарды орындауға қажетті тізбектен құрылған. Сол ереже осы күнге дейін қолданылып келеді. Әл-Хорезмидің ұсынған тәсілін жатқаушыларды алгоритмдіктер деп, ал «алгоритм» ұғымын бірқатар қасиеттері бар ережелер жүйесі деп атаған. Қазіргі кезде «алгоритм» ұғымы тек математикалық есеп шешу әдісімен ғана шектелмейді. Оның мағынасы әлдеқайда кең. Әрбір компьютер алдын-ала берілген алгоритммен, яғни жоспарлы жұмыс істейді.

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

Мысалы, у = (ax + b) (cx - d) функциясын есептеу ЭЕМ-да мынадай әрекеттерден құралады:

а-ны x-ке көбейту R1 деп,
оған b-ны қосу нәтижесі R2 деп,
с-ны х-ке көбейту R3 деп,
сх-тан d-ны алу R4 деп,
R2-ні R4-ке көбейту у деп белгіленеді.

Алгоритмнің бұйрықтары бірінен кейін бірі кезекпен орындалады. Бағдарлама Алгоритм тілінде жазу, бейнелеу мағынасын береді. Компьютерде Алгоритмнің сызықты, тармақты, циклді, логикалық, модельдік, параллельдік, тізбекті т. б. түрлері қолданылады.

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

Мәліметтерді сұрыптау (сортировка данных; sort) - белгіленген ережелерге сәйкес, мысалы мәтіндерді алфавит бойынша, сандар жиынын көлемі (өсуі, кемуі) бойынша, жиын элементтерін индекстеріне қарай қайта іріктеп орналастыру. Жұмыс істеу принципі мен алгоритмдері әр түрлі көптеген сұрыптау программалары бар.

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

1. Таңдау арқылы сұрыптау - бұл сұрыптаудың ең қолайлы түрі. Әдетте бұл әдіс кестені реттеуді қажет еткен адам ойына ең бірінші келеді. Бұның мәні мынада, мысалы n элементтен тұратын А сандар массиві берілген. Оны таңдау әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет. a1, a2, a3, …, an бүтін немес нақты сандар массивын қарастырып көрейік. Элементтердің орнын ауыстырғанда осы массив элементтерінің ауысуы кему реті бойынша емес (өсу реті бойынша емес) реттелуі керек. Массивтегі бірінші орында - ең кіші элемент, екінші орында - қалған элементтердің арасындағы ең кіші элемент және т. б. орналасуы қажет. Алгоритм келесідей болады: массивтің ең кіші мәнді элементті табу, бірінші элементпен орнын ауыстыру. Осы қадамды екінші элементтен бастап қайта қайталау. Алгоритмі:

Өлшемі n болатын А массивін толтыру және экранға шығару;
i:=1;
Индекс i-ден басталатын массив элементтерінің ішінен ең кішісін (индексі j) таңдап алу;
A[i] және A[j] элементтерінің орындарын ауыстыру;
i:=i+1 мәні үшін i:=n болғанға дейін 3 және 4 қадамдарды қайталау;
Сұрыпталған А массивін экранға шығару.

2. . Алмастыру арқылы сұрыптау - алгоритмдік сұрыптаудың ең жеңіл түрі болып табылады. Бұл алгоритмдік сұрыптау өте жеңіл, әрі оңай, себебі бұл сұрыптау улкен емес массивтерге қолданылады. Алгоритмнің қиындығы: O( n ²) . Қайтсе де сұрыптаудың кез-келген әдісі алмастырумен, яғни жадыда екі элементтін орын ауыстырумен байланысты. Бірақ басқа әдістер үшін бұл әрекет көмекші болса, алмастыру сұрыптауы үшін бұл - процесстің басты сипаты болып табылады. Алмастыру арқылы сұрыптаудың мәні кестенің қатар тұрған элементтерін қос-қостан көптеп салыстырып және осы элементтерді берілген ретпен орын ауыстыруда. Бұның мәні мынада, Мысалы n элементтен тұратын А сандар массиві берілген. Оны алмастыру әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет. Мысалы,

a1, a2, a3, …, an сандарын тізбектеп қарастырып, a[i] > a[ i+1] болатындай ең кіші i-ды табу. a[i] және a[ i+1] орындарын ауыстыру, a[ i+1] және т. б. элементтерін қарастыруды қайта бастау. Осылай ең үлкен сан соңғы орынға орналасады. Қарастырылып отырылған элементтердің санын бірге азайту арқылы келесі қарастыруларды қайтадан басынан бастау. Масив тек қана бірінші және екінші элемент қатысқан қарастырудан кейін реттеледі. Алгоритмі:

Өлшемі n болатын А массивін толтыру және экранға шығару;
i:=1;
A[i] >A[i+1] элементтерінің орындарын ауыстыру;
i:=i+1 мәні үшін i:=n болғанға дейін 3 қадамды қайталау;
Сұрыпталған А массивін экранға шығару.

3. Енгізу арқылы сұрыптау- бұл массивтің сұрыпталмаған бөлігінен сұрыпталған бөлігіне элементтерді енгізу болып табылады. Енгізілген элемент массив бөлігінің сұрыпталуын бұзбау қажет. Ол үшін енгізілген элемент өз орнын тапқанша, сұрыпталған бөлігінің элементтерімен орын ауыстырып отыруы тиіс. Өлшемі n болатын А массивін толтыру және экранға шығару. Мысалы, a2, a3, …, an реттін қарастырып, a[i] әр жаңа әлементтін a1, a2, a3, …, a[i-1] реттелген жиынының қолайлы орнына орналастыру. Бұл орын a[i] -мен a1, a3, …, a[i-1] реттелген элементтерін тізбектік салытыруымен анықталады. Алгоритмі:

1. i:=2;

2. j:=i-1;

3. Егер A[j+1] =A[j] болса, онда олардың орындарын ауыстырамыз және j:=j-1, әйтпесе j:=0;

4. j:=0 болғанға дейін 3 және 4 қадамдарды қайталау;

5. i:=i+1;

6. i:=n болғанға дейін 3, 4, 5, 6 қадамдарды қайталау;

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

Program sortmass;

Const n= ;

Var

a: array [1. . n] of integer;

i, j, c: integer;

begin

{ массивті толтыру }

randomize;

for i:=1 to n do

a[i] :=random (n) ;

{ массивті баспаға шығару}