👈 қаріп өлшемі 👉

Технология | Массив элементтерін сұрыптау

Технология | Массив элементтерін сұрыптау

[quote] Массив элементтерін сұрыптауда қойылатын негізгі шарт: массив элементтерін сұрыптаудың таңдалған әдісі жадыны тиімді пайдалануда болып табылады. Бұл элементтерджі ретке келтіретін орын ауыстырулар сол орындаа орындалуы керек екенін көрсетеді. Жадыны үнемдеу критерийімен шектеле отырып, мүмкін болатын әдістердің арасынан қажеттісін таңдау қажет, ол үшін алдымен әдістерді олардың үнемділігі тұрғысынан, яғни олардың жұмыс істеу уақыты бойынша топтау қажет. Тиімділіктің өлшемі ретінде: С-қажетті салыстырулар кілтінің санын және М- элементтерді алмастырулар санын аламыз. Бұл сандар сұрыпталатын n – элементтер санының негізгі мәні болып табылады. Сұрыптаудың тиімді алгоритмдері n*log n салыстыру ретін талап етеді. Алдымен, ең қарапайым әдісті қарастырайық, тура әдіс деп атайды, мұнда салыстырулар кілті n2 ретпен орындалады. Тура әдісті талдаудан бастауға мынадай себептер бар:
1. Тура әдіс көптеген сұрыптааулардың негізгі принциптерін түсіндіруге ерекше қолайлы.
2. Бұл әдістің программаларын түсіну әлдеқайда жеңіл, әрі программасы қысқа. Программаның өзі де жадыдан орын алатынын білеміз.
3. Күрделіленген әдістер көптеген операцияларды орындауды талап етеді, бұл операциялардың өздері де күрделі. Сондықтан тура әдіс кіші n үшін айтарлықтай жылдам болып табылады.
«Сол орында» сұрыптау әдістерін оларды анықтайтын принциптеріне сәйкес үш категорияға бөлуге болады:
1. Жалғау көмегімен сұрыптау.
2. Ерекшелеу көмегімен сұрыптау.
3. Алмастыру көмегімен сұрыптау.


Тікелей қосу көмегімен сұрыптау
Бұл әдіс карта ойынында кеңінен пайдаланылады. Элементтер ойша a1,…,aі-1 «дайын» тізбек және aі,…,an алғашқы тізбек болып бөлінеді. Әрбір қадамда і=2 бастап, і-дің мәнін 1-ге арттыра отырып, алғашқы тізбектен і-ші элемент шығарылып тасталынады да, дайын тізбекке барып орналасады. Сөйтіп, ол жаңа орынға қойылады.
Сегіз кездейсоқ таңдалынған сандарды тікелей жалғау көмегімен сұрыптаудың мысалы төмендегідей:

Алғашқы кілттер 44 55 12 42 94 18 06 67
і=2 44 55 12 42 94 18 06 67
і=3 12 44 55 42 94 18 06 67
і=4 12 42 44 55 94 18 06 67
і=5 12 42 44 55 94 18 06 67
і=6 12 18 42 44 55 94 06 67
і=7 06 12 18 42 44 55 94 67
і=8 06 12 18 42 44 55 67 94

Бұл сұрыптаудың алгоритмі төмендегідей:
For і:=2 To n Do
X:=a[і]; {x-ті a[1],…,a[і] арасындағы сәйкес орынға қою}
End;
Шынайы іздеу процесінде тізбектегі салыстырулар мен жылжуды алмастыра отырып, електен өткізу болып табылады. Х кезекті aj элементімен салыстырылады, одан кейін х не бос орынға қойылады, не aj оңға қарай жылжиды, ал процесс солға қарай жүреді. Електен өткізу процесі төмендегі шарттардың бірі орындалғанда аяқталады:
1. х-тің кілтінен кіші кілтті aj элементі табылған жағдайда;
2. тізбектің сол жақ шетіне жеткен жағдайда.
Сонымен, бұл алгоритм фрагменті төмендегідей:

For і:=2 to n do
begіn
X:=a[і];a[0]:=x; j:=І;
Whіle x
Құрметті оқырман! Файлдарды күтпестен жүктеу үшін біздің сайтта тіркелуге кеңес береміз! Тіркелгеннен кейін сіз біздің сайттан файлдарды жүктеп қана қоймай, сайтқа ақпарат қоса аласыз! Сайтқа қосылыңыз, өкінбейсіз! Тіркелу
Толық нұсқасын 30 секундтан кейін жүктей аласыз!!!


Кейінірек оқу үшін сақтап қойыңыз:


Қарап көріңіз 👇



Жаңалықтар:
» Айлакер-алаяқтар интернетте делдалдарды қалай және қандай мақсатпен іздейді 26.11.2022
» Түркия: Ыстанбұлда тағы жарылыс 17.11.2022
» Қазақстандықтар тісін тегін емдете алады: Шарттары қандай? 08.11.2022

Келесі мақала, жүктелуде...
Біз cookie файлдарын пайдаланамыз!
Біздің сайтты пайдалануды жалғастыра отырып, сіз сайттың дұрыс жұмыс істеуін қамтамасыз ететін cookie файлдарын өңдеуге келісім бересіз. Cookie файл деген не?
Жақсы