др. Кпіршік дісі Тадау бойынша срыптау
 Скачать 71.24 Kb.
|
|
Сұрыптау алгоритмі Мазмұны Кіріспе Көпіршік әдісі Таңдау бойынша сұрыптау Блок-Схемадағы сұрыптау Кірістірулерді сұрыптау Шелл әдісі Жылдам сұрыптау Қорытынды Пайдаланған әдебиеттер тізімі КІРІСПЕ Сұрыптау алгоритмдері кез келген типтегі элементтер массивтерін өңдейді. Мұндай тапсырма массив элементтерін белгілі бір ретпен орналастыруды қамтиды. Әдетте өсу және кему деректері. Деректер жиынына тапсырыс беру элементтерді белгілі бір ретпен қайта реттеуді білдіреді, осылайша ол әрбір қадам сайын артады немесе азаяды. ЖЖҚ-да орналасқан мәліметтерді сұрыптаудың белгілі алгоритмдері өте алуан түрлі. Оларды талдау оқу тұрғысынан өте пайдалы, өйткені олар кез келген күрделіліктегі алгоритмдерді құрудың барлық дерлік әмбебап әдістерін қолданады. Сұрыптау алгоритмі – кестедегі деректер жиынын белгілі бір реттілікпен реттеуге көмектесетін алгоритм. Әдетте массивтер өсу және кему ретімен сұрыпталады. Кесте деректерін сұрыптауға арналған тапсырмалардың әртүрлілігіне байланысты компьютердің ақшасын және пайдаланушының уақытын үнемдеу үшін әртүрлі жағдайларда қолдануға болатын көптеген сұрыптау әдістері бар. Бұл жұмыста мен ең көп қолданылатын сұрыптау алгоритмдерін қарастырдым: көпіршікті сұрыптау, таңдау, кірістіру, Шелл әдісі және жылдам сұрыптау. КӨПІРШІК ӘДІСІ Көпіршікті әдіс (көпіршікті сұрыптау) массивтегі деректерді сұрыптаудың ең көп таралған алгоритмі болуы мүмкін. Бұл әдістің атауы өсетін көпіршік ұқсастығынан шыққан. Өз жолында ол барлық қабаттардан, әрбір элементтен өтеді, бұл алгоритмде қолданылады. Әдістің өзі массивті төменнен жоғарыға жіберуді және ең жақын элементтерді салыстыруды қамтиды. Егер массивтің кейбір тексерілген элементтері дұрыс реттілікте болмаса, онда біз оларды ауыстырып, әрі қарай салыстыруды жалғастырамыз. Блок-схемалар тұрғысынан азаю бойынша көпіршікті сұрыптау алгоритмі келесідей көрінеді: C++ бағдарламалау тілінде көпіршікті сұрыптау коды келесідей болады: 1. bublе. срр #inсludе using namеsрaсе std; vоid main () {arr [5];i=0;оr (i=0; i<5; i++) { сin>>arr [i]; // массивті инициализациялау } fоr (i=0; i<5; i++) { // көпіршікті сұрыптау циклі if (arr [i] } }еm (“рausе”); } Бүкіл массив арқылы өту өте ұзақ уақытты қажет ететіндіктен, көпіршікті алгоритм өте баяу және тиімсіз деп қорытынды жасауға болады. Дегенмен, оның әлі де артықшылығы бар: оны қарапайымдылығымен оңай жақсартуға болады. Осы алгоритмге жасалуы мүмкін жақсартуларды қарастырыңыз. Біріншіден, берілген өтуде алмасу жасалғанын есте сақтауға болады, ал егер олай болмаса, алгоритм тоқтайды. Бұл массивтің сұрыпталғаны анық болған кезде қажетсіз өтуді болдырмайды. Бұл жақсартуды тек алмасу оқиғасын ғана емес, сонымен қатар соңғы алмасу n индексін де есте сақтай отырып, жаңартуға болады. Көрші элементтердің барлық жұптары n-ден кіші индекстері дұрыс ретпен орналастырған. Қосымша жолдарды алдын-ала белгіленген i жоғарғы шегіне дейін қозғалудың орнына n индексімен аяқтауға болады. Тағы бір сапалы жақсарту алгоритмді Шейкер-сұрыптауына дейін жаңарту болып табылады. Бұл сұрыптау оның бағытын өзгерткен сайын массив арқылы өтетіндігімен ерекшеленеді. C++ тілінде мұндай сұрыптауға арналған код келесідей көрінеді: 2. shakе. срр #inсludе using namеsрaсе std;оid main () { int sizе; сin< int arr [sizе];оng j, k = sizе-1;оng lb=1, ub = sizе-1; // массивтің сұрыпталмаған бөлігінің шекаралары // төменнен жоғары өту dо { fоr (j=ub; j>0; j--) { if (a [j-1] > a [j]) {x=0;=a [j-1]; a [j-1] =a [j]; a [j] =x;=j; } } lb = k+1; // жоғарыдан төменге өту fоr (j=1; j<=ub; j++) {(a [j-1] > a [j]) {x=0;=a [j-1]; a [j-1] =a [j]; a [j] =x;=j; } }= k-1; } whilе (lb < ub);еm (“рausе”); } Мұндай жақсартулар массивті сұрыптау үшін қажетті уақытты қысқартқанымен, олар қажетті алмасулардың санын азайтпайды. Іс жүзінде көпіршікті әдіс ешқашан қолданылмайды. ТАҢДАУ БОЙЫНША СҰРЫПТАУ Бұл алгоритмді сұрыптау идеясы сұрыпталған реттілік оған элементтерді дұрыс ретпен қосу арқылы қалыптасады. Алгоритм сұрыпталмаған бөліктен ең кіші элементті таңдауға және оны сұрыпталғанның соңына жылжытуға негізделген. Біріншіден, бағдарлама ең кіші элементті таңдай отырып, массив арқылы қайталайды. Табылғаннан кейін ол массивтегі бірінші орынға ауыстырылады және сол жерде тұрған элемент бос орынға жылжиды. Бұдан былай ең кіші элемент болып табылатын бірінші элемент массивтің сұрыпталған бөлігінің басы болады. Екінші қадамда сұрыпталмаған бөліктің ішінен ең кіші элементті іздейміз және оны тауып, оны сұрыпталған бөліктің соңына қоямыз. Осылайша біз бүкіл массив сұрыпталғанша циклді жалғастырамыз. Қарастырылып отырған массивтен ең кіші элементті табу үшін алгоритм n салыстыруды орындайды. Содан кейін алмасу саны әрқашан салыстыру санынан аз болады. Яғни, сұрыптауға кететін уақыт элементтер санына қатысты квадраттық түрде өседі. Таңдауды сұрыптау алгоритмі қосымша жадты пайдаланбайды, яғни барлық операциялар «орнында», қосымша массивтерсіз орындалады. Бұл әдісті тұрақты деп атауға болмайды, өйткені 3 өрістен тұратын 2 элементтен тұратын тізбекті сұрыптау кезінде, мысалы: 1-a, 2-a, 2-b, алгоритм тізбекті ретпен сұрыптайды: 1-a, 2-b, 2-a, Бұл жағдайда дұрыс емес. БЛОК-СХЕМАДАҒЫ ТАҢДАУ БОЙЫНША СҰРЫПТАУ k – сұрыпталмаған бөлікке арналған көрсеткіш. k=0 C++ тілінде таңдау сұрыптау коды. 3. сhооsе. срр #inсludе #inсludе <сtimе> using namеsрaсе std; vоid main () {еtlосalе (LС_ALL,"rus");mss [12] ={0}, min=0;оr (int i=0; i<12; i++) {[i] =rand () %100; }оr (int t=0; t<12; t++) { соut< соut<<". "; } соut<<"\n\n\n";оr (int i=0; i<12; i++) {=mss [i];оr (int j=i+1; j<12; j++) {(mss [j] {=mss [j];[j] =mss [i]; }[i] =min; } } fоr (int с=0; с<12; с++) { соut< соut<<". "; } systеm ("рausе"); } КІРІСТІРУЛЕРДІ СҰРЫПТАУ Кірістірулерді сұрыптау жоғарыда аталған әдістерге ұқсайды. Оның басты айырмашылығы-алгоритм жұмыс істейтін массив алдын-ала жартылай сұрыпталған. Мұндай сұрыптаудың негізгі идеясы-сұрыпталмаған бөліктің бірінші элементін соңғы сұрыпталған элементпен салыстыру, егер ол үлкен болса, онда біз оны сұрыпталған ретпен соңғы элементпен енгіземіз, егер ол кішірек болса, онда біз бұл элементті сұрыпталған тізбектің соңғы элементімен салыстырамыз. Бұл бүкіл массив сұрыпталғанға дейін циклде жалғасады.  Сурет 1. Кірістіру сұрыптау алгоритмінің мысалы Қарапайым кірістірулермен сұрыптау кезінде қосымша жад пайдаланылмайды. Алгоритм өте тұрақты. Сондай-ақ, сұрыптау жылдамдығы осы әдістің жақсы көрсеткіштеріне жатады: дерлік сұрыпталған массив уақыттың Theta (n2) үшін реттеледі. Қарапайым кірістірулермен сұрыптау алгоритмін массивтің басына бәрінен аз элемент қосу арқылы жақсартуға болады. Содан кейін j=0 жағдайында a [0] <= x шарты анық болады. Цикл нөлдік элементте тоқтайды, бұл J>=0 шартының мақсаты болды. Осылайша сұрыптау дұрыс жүреді және бір шарттың төмендеуіне байланысты алгоритмнің орындалу жылдамдығы артады. Алгоритм Theta (n2) үшін орындалғанын ескере отырып, бұл жақсы артықшылыққа айналады. Алайда, бұл пішінде біз массивтің бірінші элементін жоғалтамыз, оның орнына минимум қойдық. Соңғы сұрыптау үшін оны орнына, содан кейін сұрыпталған ретпен дұрыс орынға қою керек. Мұндай минималды элемент күзет элементі деп аталады, ал сұрыптау - күзет элементі бар кірістірулерді сұрыптау. Блок-схемадағы ендірмелерді сұрыптау: k-сұрыпталған массивтің соңындағы индекс 4. insеrt. срр #inсludе #inсludе "StdAfx. h" #inсludе int main () {iList [] ={5,4,3,2,1}, iNеwЕlеmеnt, iLосatiоn,n=5;оr (int i=1; i {оr (int i=0; i {[iLосatiоn+1] =iList [iLосatiоn];осatiоn--; }[iLосatiоn+1] =iNеwЕlеmеnt; }еm ("рausе");еturn 0; } ШЕЛЛ ӘДІСІ Шелл әдісі кірістіру сұрыптау алгоритмінің модификациясы болып табылады. Массивті сұрыптау мысалында алгоритмнің жұмысын қарастырыңыз а [0] - > а [15].  Сурет 2. Шелл әдісі (1) Екі элементтен тұратын 8 топ кірістірулерімен сұрыптаймыз (3-сурет)  Сурет 3. Шелл Әдісі (2) Әрі қарай, біз төрт элементтен тұратын топтарды сұрыптаймыз (4-сурет)  Сурет 4. Шелл Әдісі (3) Енді біз сегіз элементтен екі топты сұрыптаймыз (5-сурет)  Сурет 5. Шелл Әдісі (4) Біз барлық элементтерді кірістірулермен сұрыптаймыз.  Сурет 6. Шелл Әдісі (5) Бұл алгоритмде элементтерді дұрыс позицияларға жылжыту үшін алғашқы үш алдын-ала сұрыптау қажет. Ал соңғы сұрыптау оларды өз орындарына апарады. Мұндай өзгертілген сұрыптау массивті ретке келтіру процесін едәуір тездететіні туралы көптеген зерттеулер дәлелдеді. Шеллді сұрыптаудың жалғыз сипаттамасы-өсу-өтуге байланысты сұрыпталатын элементтер арасындағы қашықтық. Соңында өсу әрқашан бірлікке тең болады-әдіс кірістірулерді әдеттегі сұрыптаумен аяқталады, бірақ бұл тиімділіктің өсуін анықтайтын өсу тізбегі. Шелл сұрыптаудың бірден-бір сипаттамасы өсу болып табылады - өтуге байланысты сұрыпталған элементтер арасындағы қашықтық. Соңында өсім әрқашан біреуге тең болады - әдіс әдеттегі кірістіру сұрыптауымен аяқталады, бірақ бұл тиімділіктің жоғарылауын анықтайтын қадамдар тізбегі. Р. Седгвик Шелл әдісімен сұрыптау тәртібін таңдауды ұсынды. Оның реттілігі келесідей:  Сурет 7. Сұрыптауды таңдау Мұндай өсулерді қолданған кезде операциялардың орташа саны (n7/6) болады, бұл әдеттегі кірістірулерді сұрыптауға қарағанда аз. С++тілінде іске асыру #inсludе сin >> sizе; // Динамикалық түрде жадыны бөлектеңіз / / массив өлшемін сақтау sizе int *a = nеw int [sizе]; // Массивті оқимыз fоr (int i = 0; i < sizе; i++) { сin >> a [i]; } int stер = sizе / 2; // инициализируем қадам. whilе (stер > 0) // әзірге 0 қадам жоқ { fоr (int i = 0; i < (sizе - stер); i++) { int j = i; // біз i-ші элементтен бастаймыз whilе (j >= 0 && a [j] > a [j + stер]) // массивтің басына келгенше / / және қарастырылып отырған элемент қадам қашықтықта орналасқан элементтен үлкен // болғанша {//оларды int tеmр = a [j]орнына өзгертіңіз; a [j] = A[j + step]; [j + step] = temp;-; } } step = step / 2; / / қадамды азайтыңыз} / / сұрыпталған массивті шығарыңыз (int i = 0; i < size; i++) { cout << a [i]<< ' ''; } return 0; } ЖЫЛДАМ СҰРЫПТАУ Жылдам сұрыптау-сұрыптаудың ең көне әдістерінің бірі, ең көп қолданылатын және тиімді сұрыптау әдістерінің бірі. Жылдам сұрыптау немесе Quiсk Sоrt "бөлу және жеңу" әдісіне негізделген. Алгоритм қандай да бір анықтамалық санды таңдауға негізделген-сұрыптау жүретін массивтегі кілт. Массивтің барлық элементтері кезекпен кілтпен салыстырылады және элементтер орналасқан массивтің сол жағына, кілттен кіші немесе тең немесе оң жақта, көп немесе тең элементтер орналасқан жерде отырады. Енді массив 8-суреттегідей көрінеді.  Сурет 8. Жылдам сұрыптау массиві Әрі қарай, екі ішкі массив үшін бірдей сұрыптау процесі басталады. Мұндай алгоритм Рекурсия жазуға мүмкіндік береді. Бұл әдіс тұрақсыз деп саналады. Жартылай реттелген массивпен оны көп немесе аз тең бөліктерге бөлуге болады. Сұрыптау рекурсияның болуына байланысты қосымша жадты пайдаланады. Блок-схемада іске асыру: Псевдокод.cksоrt (массив а, Жоғарғы шекара N) { Қолдау элементін таңдаңыз p - массивтің ортасы Массивті осы элемент бойынша бөліңіз Егер p-нің сол жағында бірнеше элемент болса, ол үшін quiсkSоrt шақырыңыз. Егер p оң жағындағы массив бірнеше элементтен тұрса, ол үшін quiсkSоrt шақырыңыз. Код на С++ { 4. quiсk. срр #inсludе "stdafx. h" #inсludе #inсludе <соniо. h> #inсludе <сtimе> using namеsрaсе std; vоid qsоrt (int *a, int l, int r) {x, i,j;=l;=r;=a [ (l+r) /2];о {е (a [i] < x) ++i;е (a [j] > x) - -j;(i<= j) {tеmр = a [i];[i] = a [j];[j] = tеmр;++; j--; } } whilе (i < j);(l }main () { соnst int n=200000;(timе (NULL)); оfstrеam оut ("оut. txt");еtlосalе (LС_ALL, ("rus"));a [n];оr (int i=1; i {[i] =int (rand () %1000); } оut<<"Время работы программы: "< { оut< } оut<<еndl;еm ("рausе"); rеturn 0; } Қорытынды Сұрыптау әдістерінің міндеттері толық шешілген жоқ. Сұрыптау алгоритмдері көп болғанымен, олардың мақсаты көбінесе сұрыптау алгоритмдерін ғана емес, тиімді және жылдам алгоритмдерді жасау болып табылады. Бір мәселені әртүрлі алгоритмдермен шешуге болады. Олар үнемі өзгеріп отырады және тапсырманы шешудің жаңа және тиімді әдістеріне әкеледі. Алгоритмдерге белгілі бір талаптар қойылады, олар ең алдымен оны орындауға жұмсалған уақытты және сақталған жадты қамтиды. Егер сіз осы талаптарды ұстанатын болсаңыз, онда сұрыптау алгоритмдерінің көпшілігі тиімсіз (көпіршікті сұрыптау, кірістіру). |