Reja: kirish I. Bob. Saralash algoritimi haqida tushuncha

Pufakcha orqali saralsh (buble sort).Bunda quiyidagilarni yozdim.
Pufakcha usulida saralash algoritmi massivining dastlabki ikkita elementini taqqoslash bilan boshlanadi, agar kerak bo'lsa almashtirladi. Masalan, agar siz massiv elementlarini qoiymati bo'yicha saralamoqchi bo'lsangiz va birinchi element ikkinchisidan kattaroq bo'lsa, elementlarni joyida almashtirishingiz kerak. Agar birinchi element ikkinchisidan kam bo'lsa, uni almashtirishingiz kerak emas. Keyin ikkinchi va uchinchi elementlar yana taqqoslanadi va agar kerak bo'lsa almashtiriladi va bu jarayon oxirgi va oldingi elementlar taqqoslanib almashtirilguncha matngacha davom etadi. Bu qabariq tartibining birinchi bosqichini yakunlaydi.
Birlashtirish orqali saralsh.Bunda quiyidagilar yozildi.
Bu algoritm Jon fon Neyman tamonidan 1946 yilda taklif qilingan.
Jon Fon Neyman Vengriyalik matematika, kvant fizikasi, funksional
analiz, to’plamlar nazariyasi, ekonomika, informatika kabi fanlarga
munosib hissa qo’shgan. Ajratish va g'alaba qozonish strategiyasi
Divide and Conquer texnikasi yordamida biz muammoni subtasksga ajratamiz. Bizda har bir kichik topshiriq uchun echim bo'lsa, biz asosiy vazifani hal qilish uchun pastki vazifalardan olingan natijalarni "birlashtiramiz".

Aytaylik, biz A massivini saralashni xohladik. Sub-vazifa bu qatorning kichik qismini, p indeksidan boshlanib, r indeksiga qadar A [p..r] deb belgilangan tartiblashtirishdan iborat bo'ladi.

Bo'lmoq
Agar q p va r orasidagi oraliq nuqta bo'lsa, unda biz A [p..r] kichik qatorni ikkita A [p..q] va A [q + 1, r] qatorlarga bo'lishimiz mumkin.

Hukmronlik qiling

Fath bosqichida biz ikkala A [p..q] va A [q + 1, r] kichik dasturlarni saralashga harakat qilamiz. Agar biz hali ham boshlang'ich darajaga etib bormagan bo'lsak, biz yana ikkala quyi qismni ajratib, ularni saralashga harakat qilamiz.

Biz birlashtiramiz

Fath etuvchi pog'ona tayanch pog'onasiga etganida va biz A [p..r] massivi uchun ikkita tartiblangan A [p..q] va A [q + 1, r] kichik majmualarni olsak, natijalarni birlashtiramiz, tartiblangan massiv hosil qilamiz. A [p .r] ikkita saralangan A [p..q] va A [q + 1, r]