Algoritmlar va berilganlar strukturasi

Saralash algoritmi
Saralash nima ekanligini va uni amalga oshirish usullarini tushunganimiz uchun endi saralashni amalga oshiruvchi algoritmlarga o'tamiz. Ro'yxat yoki to'plamni saralash uchun ro'yxat homolog bo'lishi kerak, ya'ni ro'yxatdagi barcha elementlar bir xil bo'lishi kerak. Ko'pincha biz butun sonlar ro'yxatidan foydalanamiz va odatda qiymatlarni ko'paytirish yoki kamaytirish tartibida butun sonlarni ro'yxatlashimiz mumkin. Masalan, quyidagi sonlarning ro'yxati berilgan: 1, 3, 8, 4, 7, biz ushbu ro'yxatni ba'zi xususiyatlarga ko'ra saralashimiz mumkin:
Kirish: 1, 3, 8, 4, 7
A. Chiqish: 1, 3, 4, 7, 8 =>
B. qiymatning ortib boruvchi tartibiga ko'ra tartiblangan . Chiqish natijasi: 8,7, 4, 3,1 => qiymatning pasayishi tartibiga ko'ra tartiblangan
C. Chiqish: 1, 3, 8, 4, 7 => omillar sonining ortib borishi tartibida saralanadi
Yuqoridagi birinchi holatda, biz ro'yxatdagi narsalarning tobora ortib borayotgan tartibiga qarab tartiblashtirdik.
Ikkinchi holda, biz ro'yxatdagi narsalarning kamayish tartibiga qarab tartibni tartiblashtirdik.
Uchinchi holatda, biz har bir butun son mavjud bo'lgan omillar sonining ortib borayotgan tartibiga qarab ro'yxatni tartibladik. Shuningdek, biz satrlar yoki so'zlarning ro'yxatini leksikografik tartibda saralashimiz mumkin va juda murakkab ma'lumot turlarini saralashimiz kerak bo'lishi mumkin.
Tartiblash algoritmi bu qatorni kirish sifatida qabul qiladigan, ketma-ketlikda belgilangan operatsiyalarni bajaradigan, ba'zan ro'yxat deb nomlanadigan va tartiblangan massivni chiqaradigan bir qator ko'rsatmalardan iborat algoritm. - brilliant.org
Nima uchun ma'lumotlarni saralashdan tashvishlanishimiz kerak va nima uchun tez va samarali saralash algoritmlarini topishga ko'p yillik tadqiqotlar va tadqiqotlar sarflandi? Saralash algoritmlarini o'qitish va tushunish Big-O notation, bo'linish va yutish usullari va ikkilik daraxtlar va uyumlar kabi ma'lumotlar tuzilmalari kabi boshqa kompyuter fanlari tushunchalarini joriy etishga yordam beradi. Saralangan ma'lumotlar mashinalarning hisoblash kuchi uchun juda foydali.
Agar biz ro'yxatni kompyuter xotirasida saralanmagan deb saqlasak va biz ushbu ro'yxatdagi elementni qidirishni xohlasak, biz qidirayotgan narsani topgunimizcha chiziqli qidirishni amalga oshirishimiz kerak va biz qidirayotgan narsani topgunimizcha skanerlashni davom ettirishimiz kerak. uchun. Agar biz ro'yxatdagi elementni topa olmagan bo'lsak (eng yomon stsenariyimiz), biz qidirayotgan element bilan taqqoslagan holda, butun ro'yxatni ko'rib chiqdik. Shunday qilib, agar ro'yxatda n ta element bo'lsa, eng yomon holatda, biz n ta taqqoslashni amalga oshiramiz. Zamonaviy kompyuter tomonidan ishlov beriladigan ma'lumotlarning hajmini tasavvur qiling, agar n = 2⁶⁴ ni olsak va bitta taqqoslashni hisoblash uchun 1 millisekund kerak bo'lsa, yomonroq stsenariyda taqqoslash uchun hisoblash vaqti 2⁶⁴ ga teng bo'ladi.millisekundlarda. Men buni soatlab, kunlar va hatto yillarga aylantirmoqchi emasman, ammo barchamizning fikrimizcha, bu hisoblash to'liq bo'lishi uchun bir necha yil kerak bo'ladi. Hech kim biron bir hisoblash tugashini kutib o'tirishni xohlamaydi, chunki biz bilamiz, vaqt qimmatlidir. Ammo, agar biz ro'yxatimizni saralangan ro'yxat sifatida kompyuter xotirasida saqlasak, biz elementimizni topish uchun ikkilik qidiruvdan foydalanishimiz mumkin. Bunday holda, n o'lchovli ro'yxatimiz uchun, hisoblashni yakunlash uchun kirish millisekundlarga to'g'ri keladi.
If we take n = 2⁶⁴;
log₂n => log₂2⁶⁴
=> 64log₂2
=> 64 * 1 => 64
(Izoh: log₂2 1 ga teng).
Shuning uchun taqqoslashni hisoblashni yakunlash uchun 64 millisekund davom etadi. Qoyil! Qanday farq, to'g'rimi ?! Tartiblangan ro'yxat bilan biz ko'p vaqtni tejashga va boshqa muhim narsalarga o'tishga muvaffaq bo'ldik.
Tartiblashning muammo sifatida muhimligi bugungi kunda bizda mavjud bo'lgan turli xil algoritmlarni loyihalashga olib keldi. Ushbu saralash algoritmlarining ba'zilari quyidagilarni o'z ichiga oladi;