 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Шайқау әдісімен сұрыптау алгоритмі
|
|
Сұрыптау (Сортировка; sorting) - массив элементтерін белгілі бір заңдылықпен орындарын ауыстырып реттеупроцессін айтамыз. Мысалы, сандар массивін өсуі, кемуі бойынша сұрыптау, жолдар массивін алфавит бойынша сұрыптау және тағы басқа. Сұрыптау мақсаты - көптеген сұрыпталған обьектінің ішінен белгілі бір элементті іздеуді оңайлату. Ақпараттық жүйелерде мәліметтерді сұрыптаудың маңызы өте зор.
Сұрыптаудың шейкерлі әдісі - ретсіздіктен құтылу арқылы сұрыптау. Шайқау әдісімен сұрыптау кезінде массивтегі жүрістер саны минимальды немесе максимальды элемент қай жерде орналасқанына байланысты. Мұнда бірінен кейін бірі келетін жүрістердің бағытын ауыстыру арқылы жылдамдатуға болады.
Массив реттелген болған жағдайда бүкіл тізім бойынша 1 ғана жүріс өтеді. Мұнда тиімділігі О(n)-ға тең. Ал ең тиімсіз жағдайда i-1 жүріс орындалады және i-ші жүрісте n-i-1 салыстыру жүргізіледі. Ең тиімсіз жағдайда тиімділігі О(n2) тең. Жалпы жағдайда таңдау арқылы сұрыптау көбікше арқылы сұрыптауға қарағанда ауыстырылатын сан аздығымен тиімді болады. Шейкер сұрыптау алгоритмі элементтердің барлығы немесе көпшілігі сұрыпталған жағдайда пайдаланған тиімді.
Бұл алгоритмнің негізгі мәні мынада:
· Массивтегі ретсіздіктен құтыламыз;
· Бір-бірінен алшақ орналасқан элементтерді салыстырамыз;
· Салыстырып отырған интервалдар бірте-бірте кемиді;
· Соңғы қадамдарды элементтер жай ғана орые алмастырумен шектеледі.
| void ShakerSort(int *a, int n) { int left, right, i; left = 0; right= n - 1; while (left <= right) { for (i = right; i >= left; i--) { if (a[i-1] > a[i]) { int temp = a[i-1]; a[i-1] = a[i]; a[i] = temp; } } left++; for (i = left; i <= right; i++) { if (a[i-1] > a[i]) { int temp = a[i-1]; a[i-1] = a[i]; a[i] = temp; } } right--; } } |
Дата публикования: 2015-07-22; Прочитано: 1508 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
