Программалау және программа, программалау тілдері. Программалау тілдерінің түрлері. Программаны түзету (отладка), тестілеу

Енді көпіршікті сұрыптауға өтейік. Оның негізгі принципі кіші мәндерді тізім басына ығыстыру, ал үлкен мәндерді төмен түсіреді. Көпіршікті сұрыптаудың көптеген әртүрлі нұсқалар бар. Көпіршікті әдіс алгоритмі тізім бойынша бірнеше рет өтеді. Әрбір өткенде көрші элементтерді салыстырады. Егер көрші элементтердің тізімі дұрыс емес болса, онда олар орын ауыстырады. Әрбір тәсіл тізім басынан басталады. Алдымен бірінші мен екінші элементтер, сосын екінші мен үшінші, содан кейін үшінші мен төртінші және т.с.с.; жұпта ретсіз тұрған элементтердің орны ауыстырылады. Тізімнің ең үлкен элементін бірінші өткенде тапқан кезде ол тізімнің соңына жеткенге дейін барлық кезекті элементтермен орын ауыстыра береді. Сондықтан екінші рет өткенде соңғы элементпен салыстыру қажет емес. Екінші рет өткенде тізімнің екінші элементі соңғы позициядан бастап екіншіге түседі. Процесті жалғастыра берсек әрбір өткен сайын ең болмағанда кезекті бір элемент өзінің орнында қалады. Бұл кезде ең кіші мәндер жоғары қарай жиналады. Егер қандай да бір өткен кезде ешқандай элементтердің орны ауыспаса, онда олардың барлығы қажетті ретпен тұр, және алгоритмнің орындалуын тоқтатуға болады. Әрбір өткенде бірден бірнеше элемент өзінің орнына жақындай түседі, тек біреуі ғана нақты орнында келеді

Біз қысқаша түрде ең жақсы жағдайды қарастырамыз, swappedElements туының дұрыс емес интерпретациясын ескерту үшін, орындалатын жұмыс көлемі қандай жағдайда минималды. for циклі бірінші өткенде толығымен орындалу керек, және сондықтан алгоритмге ең болмағанда N — 1 салыстыру талап етіледі. Екі мүмкіндікті қарастыру керек: бір өткенде ең болмағанда бір орын ауыстыру болды және ауыстырулар болған жоқ. Бірінші жағдайда орын ауыстыру swappedElements жалауының мәнін true-ға ауыстырады, ендеше while циклі қайтадан орындалады және N — 2 салыстыруды талап етеді. Екінші жағдайда swappedElements жалауы false мәнін сақтайды және алгоритмнің орындалуы тоқтайды.Сондықтан жақсы жағдайда N — 1 салыстыру орындалады, және бірінші өткенде орын ауыстыру болмаған кезде орындалады. Бұл деректердің жақсы жиыны талап етліген реттегі элементтер тізімін береді.

Ең жақсы мүмкін болатын тізімдегі элементтер талап теліген ретпен жүргендіктен элементтердің кері реті ең жаман жағдайды бере ме, соны қарау керек. Егер ең үлкен сан бірінші тұрса, онда ол тізімнің соңына дейін барлық элементтермен орын ауыстырады. Бірінші рет өтер алдында шамасы бойынша екінші элемент екінші позициядан орын алса, бірақ бірінші салыстыру және бірінші орын ауыстыру нәтижесінде ол бірінші орынға қойылады. Алдымен екінші рет өткенде бірінші позицияда шамасы бойынша екінші элемент орналасады, және ол тізімнің соңының алдына дейін барлық элементтермен орын ауыстырады. Бұл процесс қалған барлық элементтер үшін қайталанады, сондықтан for циклі N—1 рет қайталанады. Сондықтан кіріс деректерінің кері реті ең жаман жағдайға әкеледі.