Сұрыптау

►Бірөлшемді массив элементтерін сұрыптау алгоритмдерін қолданып, өсу немесе кему ретімен қалай сұрыптауға болады?

Программалауда сұрыптау

1-сурет. Алмаларды салмақтары бойынша сұрыптау

Ойлан 

♦ Сұрыптау деген не?

♦ Массив элементтерін сұрыптау дегенді қалай түсінесің?

♦ Осы тақырыпқа байланысты күнделікті тұрмыстан қандай мысалдар келтіре аласың?

Өткен тақырыптарда біртипті деректердің арасынан бізге қажетті қасиеті бар элементті сызықтық алгоритмдер арқылы іздеумен таныстық. Мысалы, салмақтары әртүрлі 4 алма берілген (1-сурет). Неше рет ауыстыру арқылы осы алмаларды салмақтарының өсу ретімен орналастыруға болады?

Қарастырылған мысалда 4 рет ауыстыру арқылы алмалар өсу ретімен сұрыпталды. Бірақ төрт рет ауыстыру орындалғанмен, әрбір 2 жұп элемент барлығы 6 рет тексерілді. Ұзындығы n-ге тең массив элементтерін сұрыптау үшін көп жағдайларда n * n тексеруді қажет етеді. Бұл сұрыптау көбікті сұрыптау әдісіне жатады.

Есіңізде сақтаңыз

Программалауда сұрыптау – бұл қандай да бір массив эле-менттерін кему немесе өсу ретімен ауыстыру процесі.

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

Программалау процесінде бірөлшемді массивтерді сұрыптаудың бірнеше жалпыға танымал алгоритмдері бар. Бұл сұрыптау алгоритмдері жұмыс істеу тиімділігіне қарай бөлінеді (1-кесте).

-1-

Жылдам сұрыптау (Быстрая сортировка; Quick Sort) сұрыптау әдістерінің арасындағы ең жылдам сұрыптаушы алгоритмдердің бірі саналады. Quick Sort – көмегімен сандық элементтерді өсу немесе кему ретімен, мәтіндік массив элементтерін алфавит ретімен сұрыптайды. Quick Sort-ты 1960 жылы Мәскеу мемлекеттік университетінің студенті ағылшын Чарль Хоармен әзірлеген. Хоармен бұл сұрыптауды көпіршік әдісінің жетілген түрі ретінде ұсынған болатын.

-2-

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

-3-

Төменде берілген кестедегі сұрыптау командалары арқылы сандарды ғана емес, сөздерді де сұрыптауға болады. Мысалы, Раушан, Асхат, Мағжан, Асыл деген есімдерді Асыл, Асхат, Мағжан, Раушан деп алфавит ретімен сұрыптауға болады. Ол үшін массив элементін жүктеу A[i] = int(input()) қатарын A[i] = input() түрінде жазу керек.

Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жылдам сұрыптау және компьютер жадын үнемді пайдалану болып табылады.

Мысалдар

1-мысал

А[N] бірөлшемді массиві берілген. Осы массивтің элементтерін өсу және кему ретімен экранға шығар. Программа коды (1-код) мен 2-суретте программаның сұрыптау нәтижесі берілген.

2-мысал:

B[N] бірөлшемді, бірдей екі элементі жоқ массив берілген (0<N<100). Осы массивтегі K-ші үлкен элементті тап. Мысалы, N=10 және К=2 болса, онда 10 элементі бар массивте (8 14 52 14 25 35 67 41 25 30) 2-ші үлкен элемент 52-ге тең.

-1-

Есепті шешудің бірнеше жолы бар. Ең қарапайым тәсілі бірінші үлкен элементті тауып, оның мәнін басқа кіші мәнге ауыстыру керек. Одан соң массивте 2-ші рет іздеу жүргізіп, 2-ші үлкенін табуға болады.
​Әрине массивтегі элементтер аз болғанда программаның жұмыс жылдамдығы бізді қанағаттандыратыны анық. Ал массивтің 100 емес 1 000 000 элементі және реті бойынша 2-ші емес 99-шы тұрған үлкен элементті табу керек болса, қалай болады?

-2-

Мұндай жағдайда массивті кему бойынша сұрыптап, 99-шы тұрған элементті нәтиже ретінде беруге болады (А. Шень: Программирование: теоремы и задачи. 2004 г.). Егер жұмыс жылдамдығы орташа компьютерлер 1 секундта жуық шамамен 1000000 амал орындайтынын ескерсек, онда жоғарыда қарастырылған жағдайда 99-шы үлкенін табуға 1 се-кунд уақыт кетеді. Есептің программа коды мен 3-суретте нәтижесі берілген.

3-сурет. Программаның орындалуы

Практикалық жұмыс

Python-да сұрыптау көмегімен күнделікті кездесетін есептердің жобаларын орындауды қарастырайық.

«Алма сыйлау» жобасы

Әселдің N алмасы бар (0<N<10000). Алмаларының салмағы bi массивін құрайды (bi<1000). Әсел сіңлісі Гауһарға сол алмалардың арасынан ең үлкен К алманы сыйлағысы келеді (0<К<N). Әселге ең үлкен алманы таңдауға көмектесетін жоба дайында.

Түсініктеме: Жобаның программасын дайындау кезеңін-де алмалар салмағына арналған массивті кездейсоқ сандармен құраймыз. Алмалардың саны-ның шегі үлкен болғандықтан, жылдам сұрыптау үшін Qsort әдісін қолданамыз. Жобаның программалық кодында (3-код) алмаларды салмағының кему ретімен орналастырамыз. Сыйлауға алғашқы К алманы нәтиже ретінде баспаға береміз (4-сурет).

4-сурет.«Алма сыйлау» жобасының орындалу кезеңі

Ойыңды тұжырымда

Жұптық жұмыс

Сыныптастарыңды көркем әдебиет оқуға шақыру мақсатында «100 кітап жобасы» аясында өздерің оқыған 10 кітаптың атауы мен шыққан жылы бойынша екі массив құрастырыңдар. Төмендегі әрекеттерді орындайтын жобаның жоспарын ұсыныңдар.

1. Кітаптардың атауларын алфавит ретімен реттейтін.

2. Кітаптарды шыққан жылы бойынша жаңасынан ескісіне қарай сұрыптайтын.

Топтық жұмыс

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

Жеке жұмыс

1. Массивті сұрыптау деген не?
​2. Массивтерді сұрыптайтын негізгі әдістер туралы не айтуға болады?
​3. Сұрыптау алгортимдеріне қандай талаптар қойылады?
​4. Сұрыптауды қолданып, массивтің минималды элементін қалай табуға болады?
​5. Ең жылдам сұрыптау әдіс жайлы не айта аласың?
​6. Көпіршік әдісте сұрыптау қалай жүзеге асады?

Өтінемін күте тұрыңыз