Mundarija[Yashirish][Show]
Kompyuter fanlari algoritmlar va ma'lumotlar tuzilmalarining murakkabligini tushunishga qaratilgan.
Sizda saralanishi kerak bo'lgan narsalar ro'yxati bor, lekin sizda murakkabroq tartiblash algoritmidan foydalanish uchun vaqt va resurslaringiz yo'q.
Qo'shishni saralash eng oddiy tartiblash algoritmlaridan biridir, lekin katta ro'yxatlar uchun u sekin bo'lishi mumkin.
Oson amalga oshirish va tushunish bu usulni dasturchilar orasida sevimliga aylantirdi. Bu kichik ro'yxatlar uchun yoki sizga tezkor yechim kerak bo'lganda juda mos keladi.
Ushbu blog postida biz kiritish vaqtini saralashning murakkabligini ko'rib chiqamiz. Bu algoritm massivlarni saralash uchun ishlatiladi va uning ish vaqti O(n2). Bu shuni anglatadiki, vaqt murakkabligi massiv hajmi bilan ortadi.
Biroq, bu algoritm tez-tez tez saralash kabi boshqa tartiblash algoritmlariga qaraganda tezroq bo'lishi mumkin.
Keling, qo'shishni saralash qanday ishlashini batafsil ko'rib chiqaylik!
Qo'shishni tartiblash algoritmi nima?
Bir vaqtning o'zida bitta element, qo'shish tartiblash ko'pincha ro'yxat deb ataladigan tartiblanadigan massivni hosil qiladi.
Masalan, saralash kompilyatorlar kabi murakkab kompyuter dasturlarida qo'llaniladi, bu erda tokenlar tartibi dasturni talqin qilish uchun muhimdir.
Qo'shishni saralash qanday ishlaydi?
Massivni saralash uchun kiritish tartibidan foydalansak, algoritm ro‘yxatdagi eng kichik elementni topib, uni to‘g‘ri joyga qo‘yishdan boshlanadi.
Keyin u keyingi eng kichik elementni topadi va uni to'g'ri joyga qo'yadi va hokazo.
Algoritm roʻyxatni aylanib chiqish, har bir elementni oʻzidan oldingi element bilan solishtirish orqali ishlaydi.
Agar elementlar noto'g'ri tartibda bo'lsa, algoritm ularni almashtiradi. Keyin ro'yxat tartiblanganligini tekshiradi va agar shunday bo'lsa, algoritm tugaydi.
Amalda, kiritish tartibi ko'pincha bir necha qator kodlar yordamida amalga oshiriladi, bu uni kichik massivlarni saralash uchun mashhur tanlovga aylantiradi. Biroq, ushbu algoritmdan foydalanganda vaqt murakkabligini hisobga olish kerak.
misol:
Qo'shishni saralash qanday ishlashiga misol. Biz quyidagi massivdan foydalanamiz:
1, 2, 3, 4, 5, 6
Algoritm ro'yxatdagi eng kichik elementni topishdan boshlanadi, bu 1. Keyin uni to'g'ri pozitsiyaga, birinchi pozitsiyaga kiritadi. Keyin u keyingi eng kichik elementni topadi, bu 2. Uni to'g'ri pozitsiyaga, ya'ni ikkinchi pozitsiyaga kiritadi.
Keyin u keyingi eng kichik elementni topadi, ya'ni 3. Uni to'g'ri pozitsiyaga, ya'ni uchinchi pozitsiyaga kiritadi.
Keyin u keyingi eng kichik elementni topadi, ya'ni 4. Uni to'g'ri pozitsiyaga, ya'ni to'rtinchi pozitsiyaga kiritadi va hokazo. Ro'yxat endi tartiblangan!
Biz misoldan ko'rishimiz mumkinki, algoritm oltita taqqoslash va ro'yxatni saralash uchun almashtirishni oladi. Buning sababi n ni oladi2 n ta element ro'yxatini saralash uchun taqqoslash va almashtirish. Bu holda, n=6.
Qo'shishni saralash vaqtining murakkabligini qanday yaxshilash mumkin?
Qo'shish tartibida ish vaqti O(n2), uni tezroq saralash kabi yaxshiroq tartiblash algoritmidan foydalanish orqali yaxshilash mumkin.
Quicksort O(n log n) ish vaqtiga ega, bu O(n) dan ancha tezroq2).
Biroq, ba'zi hollarda qo'shishni saralash tezkor saralashdan tezroq bo'lishi mumkin.
Misol uchun, agar ro'yxat allaqachon tartibda bo'lsa, qo'shishni saralash tezkor saralashdan kamroq vaqt oladi.
Amalda, kiritish tartibi ko'pincha bir necha qator kodlar yordamida amalga oshiriladi, bu uni kichik massivlarni saralash uchun mashhur tanlovga aylantiradi.
Biroq, ushbu algoritmdan foydalanganda vaqt murakkabligini hisobga olish kerak.
Vaqt murakkabliklari
Eng yomon holat murakkabligi O(n2):
Vaqtning murakkabligi massiv hajmi bilan ortadi. n ni oladi2 n ta element ro'yxatini saralash uchun taqqoslash va almashtirish.
Misol uchun, agar bizda 1000 o'lchamli massiv bo'lsa, algoritm massivni saralash uchun 1,000,000 XNUMX XNUMX taqqoslash va almashtirishni oladi.
Eng yaxshi holatlar murakkabligi O(n):
Vaqt murakkabligi kirish massivining o'lchami bilan bir xil. I
t n ta ob'ekt ro'yxatini saralash uchun n ta taqqoslash va almashtirishni oladi. Misol uchun, 5 o'lchamli massivni ko'rib chiqing. Algoritm massivni saralash uchun beshta taqqoslash va almashtirishni oladi.
Oʻrtacha harflar murakkabligi O(n2):
Vaqt murakkabligi bu holatda eng yomon va eng yaxshi holatlar o'rtasida.
n ni oladi2 n ta element ro'yxatini saralash uchun taqqoslash va almashtirish.
Shunday qilib, qo'shishni saralash barqaror tartiblash algoritmidir.
Nima uchun qo'shish tartibi barqaror?
Qo'shish tartibi barqaror, chunki u kirish massividagi teng elementlarning tartibini saqlaydi.
Bu ma'lumotlarni olish yoki moliyaviy tahlil kabi ko'plab ilovalar uchun muhimdir. Misol uchun, agar bizda ikkita raqamlar ro'yxati mavjud bo'lsa va ularni solishtirmoqchi bo'lsak, elementlarning tartibi saqlanishiga ishonch hosil qilishimiz kerak.
Agar ro'yxatlar tartiblanmagan bo'lsa, biz ularni aniq taqqoslamaymiz.
Leave a Reply