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

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 13 бет
Таңдаулыға:

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТІРЛІГІ
Л.Н. Гумилев атындағы Еуразия ұлттық университеті
Ақпараттық технологиялар факультеті
Компьютерлік және программалық инженерия кафедрасы

Алгоритмдер және деректер құрылымы пәні

К У Р С Т Ы Қ ЖҰ М Ы С

6B06104 - Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығының
В057-6104-20-07 тобының студенті

Ермағамбетов Ержан Жандосұлы
тегі А.Ә.

Нұр - Сұлтан 2022

Мазмұны

Кіріспе
2
1. Жылдам сұрыптау әдісп
3
2. AVL-ағашты баланстау. Солға үлкен бұру
6
3. Практикалық тапсырма
10
4. Қорытынды
12
5. Қолданылған әдебиеттер тізімі
13

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

1. Жылдам сұрыптау әдісі
Сұрыптау - күнделікті жұмыс және көп уақытты қажет етеді. Сұрыптау термині әдетте тізімдегі заттарды алдын-ала белгіленген тапсырыс қатынасы негізінде өсу немесе кему ретімен орналастыруды білдіреді. Сұрыптау көбінесе деректерді өңдеудегі тағы бір негізгі қызмет болып табылатын іздеуге арналған. Егер сөздіктерде сөздер ұйымдастырылмаған немесе сұрыпталмаған болса, сөздікті іздеу қаншалықты қиын болғанын елестетіп көріңіз. Бұл сөздіктегі жазбалардың стандартты алфавиттік тәртіпте сақталуының себебі. Көптеген тапсырмалар мен есептеулер жай сұрыптау арқылы оңай болмайды. Сұрыптау алгоритмдері суретке түсетін жерде.

Сұрыптау алгоритмі - тізімнің элементтерін белгілі бір тәртіпке, мысалы, ең төменнен жоғарыға, ең төменнен төменге, өсіп келе жатқан тәртіпке, азайту тәртібіне, алфавиттік т.с.с. ұйымдастыруға арналған әдіс. сандық және лексикографиялық тәртіпті құрайды. Алгоритмдер негізгі сұрыптау ретінде сұрыптауды жиі қолданады. Сұрыптау алгоритмдерінің алуан түрлері бар, олардың әрқайсысында көптеген әдістер қолданылады. Осындай танымал, бірақ қуатты алгоритмнің бірі - көп тармақты рекурсияға негізделген алгоритм болып табылатын Divide және Conquer алгоритмі. Жылдам сұрыптау және біріктіру сұрыптау - бөлу және жеңу алгоритміне негізделген екі жиі қолданылатын алгоритмдер.

Жылдам сұрыптау - бөлу және жеңу тәсіліне негізделген жоғары тиімді, бірақ тиімді сұрыптау алгоритмі, ол екі немесе одан да көп ішкі мәселелерге бөлініп, содан кейін рекурсивті түрде шешілетін динамикалық тәсілге өте ұқсас. Егер қосалқы есептердің мөлшері аз болса, онда олар еш қиындықсыз қарапайым түрде шешіледі. Жылдам сұрыптау алгоритмі бөлімді айырбастау сұрауы деп аталады, тізімді үш негізгі бөлікке бөледі: 1) жиынтық элемент (орталық элементтер), 2) айналмалы элементтерден аз элементтер және 3) айналмалыдан үлкен элементтер. Біліктің өзі екі топтың арасына өзінің соңғы орнына ауысады, содан кейін САҚТАНДЫҚ СОРТ рекурсивті қолданылады.

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

Ғарыштық күрделілік
Жылдам сұрыптау алгоритмінде сұрыптау рекурсивті түрде жасалады және әр рекурсивті қоңырау үшін стек орын қажет. Ол біріктіруге арналған қосымша орынды қажет етпейді, біріктіруге арналған бір жадтан басқа. Бұл орнында сұрыптау алгоритмі болғандықтан, сұрыптау үшін қосымша орын қажет емес. Шындығында, ол массивті бөлу және біріктіру кезінде бірдей жиымды қолданады. Merge Sort, екінші жағынан, деректерді файлда немесе массив түрінде ұсынудың бірнеше жолдары бар, сондықтан оған қосымша орын қажет ететін ішкі файлдар немесе масштабтағы өлшемдер сияқты жұмыс аумақтары қажет.

Ең нашар істің күрделілігі
Жылдам сұрыптау үшін ең нашар жағдай бөлу теңестірілмеген кезде пайда болады, ол бөлу үшін қандай элементтер қолданылатынына байланысты болады, алгоритм кірістіру сұрыпталуы сияқты асимптотикалық түрде баяу жұмыс істейді. Жылдам сұрыптаудың ең нашар көрсеткіші - O (n2) және жаттығу ретінде қалады. Дегенмен, дұрыс бұрылысты таңдау арқылы оны болдырмауға болады. Merge Sort-тің ең нашар жағдайы, керісінше, ең көп салыстыруды орындау қажет болған кезде пайда болады. Біріктірудің сызықтық өнімділігін ескерсек, сұрыптаудың ең нашар көрсеткіші O (n log2 n) болып табылады.

Қысқаша мәлімет
Жылдам сұрыптау және біріктіру сұрыптау алгоритмдері де бөлуге және сұрыптауға арналған тәсілге негізделген. Дегенмен, олар бөлу және біріктіру процедураларын орындау үшін қолданылатын әдістермен ерекшеленеді. Олар негізінен бірдей принцип бойынша жұмыс істейді - мәселені екі немесе одан да көп ішкі проблемаларға бөліп, содан кейін оларды рекурсивті түрде шешу. Біріктіру сұрыптау нашар жағдайда жылдам сұрыптауға қарағанда тиімді, бірақ екеуі орташа жағдайда бірдей тиімді. Жылдам сұрыптау - Merge Sort сұрыптауынан гөрі кең орынды. Осылайша, Жылдам сұрыптау, біріктірудің сұрыптауынан гөрі тезірек және жақсырақ, бірақ салыстыруға келгенде кейбір жағдайларда тиімсіз болады.
2. AVL- ағашты байланыстыру. Солға үлкен бұру
AVL ағашы (Aдельсон-Velsky және Landis өнертапқыштардың атымен аталады ) - бұл өзін-өзі теңдестіретін екілік іздеу ағашы. Мұндай бірінші болды мәліметтер құрылымы ойлап табу керек.[2] AVL ағашында биіктіктер екеуінің бала кез-келген түйіннің ішкі ағаштары ең көбімен ерекшеленеді; егер кез-келген уақытта олар бірнешеден ерекшеленетін болса, қайта теңгерімдеу осы қасиетті қалпына келтіру үшін жасалады. Іздеу, енгізу және жою қажет O(журнал n) орташа және нашар жағдайдағы уақыт, қайда - бұл операцияға дейінгі ағаштағы түйіндердің саны. Енгізу және жою ағашты бір немесе бірнеше баланстың теңгерімдеуін талап етуі мүмкін ағаштардың айналуы.AVL ағашы екеуінің атымен аталған Кеңестік өнертапқыштар, Георгий Адельсон-Вельский және Evgenii Landis, оны 1962 ж. Ақпаратты ұйымдастырудың алгоритмі мақаласында жариялады.[3] AVL ағаштарын жиі салыстырады қызыл-қара ағаштар өйткені екеуі де бірдей операциялар жиынтығын қолдайды және қабылдайды негізгі операцияларға арналған уақыт. Іздеуді қажет ететін қосымшалар үшін AVL ағаштары қызыл-қара ағаштарға қарағанда жылдамырақ, өйткені олар қатаң теңдестірілген.[4] Қызыл-қара ағаштарға ұқсас, AVL ағаштары биіктікте теңдестірілген. Екеуі де жалпы емес салмақ теңдестірілген не - кез-келген үшін теңдестірілген ;[5] яғни, бауырластар түйіндерінің ұрпақтарының саны әр түрлі болуы мүмкін. AVL ағашына бірнеше элементтер кірістірілген анимация. Оған солға, оңға, солға-оңға және оңға-солға айналу кіреді.

AVL ағашы - бұл теңдестірілген екілік іздеу ағашының түрі, онда әр ішкі түйіннің екі баласының биіктігі бір-біріне сәйкес келуі керек. Сыртқы түйіннің биіктігі нөлге тең, ал кез-келген ішкі түйіннің биіктігі әрқашан екі баласының биіктігінің максимумы болып табылады. Осылайша, AVL ағашының биіктік функциясы WAVL ағашының шектеулеріне бағынады және біз кез-келген AVL ағашын WAVL ағашына айналдырып, әр түйіннің биіктігін оның дәрежесі ретінде қолдана аламыз.
AVL ағашы мен WAVL ағашының арасындағы негізгі айырмашылық түйінде бірдей дәрежеге немесе бойға ие екі бала болған кезде пайда болады. AVL ағашында, егер түйін болса х бойымен бірдей екі баласы бар сағ ретінде, содан кейін биіктігі х дәл болуы керек сағ + 1. Керісінше, егер WAVL ағашында, егер түйін болса х бір деңгейдегі екі баласы бар р ретінде, содан кейін дәрежесі х болуы ... жалғасы

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