🇺🇿 Selection tartiblash usuli.

Salom! Bugun tartiblash algoritmlar mavzusini davom etaman. Selection sort-ni ko'rib chiqaman.

😇 Github: Selection sort
⏰ Time complexity: O(N ^ 2)
🔎 Space complexity: O(1)

🧑‍💻 Izoh 🧑‍💻
1. Massivda eng kichik elementni topasiz 🧐 va uni 1-pozitsiya ostida turgan element bilan joylarini almashtirasiz.

2. Endi massivni keyingi elementdan [2, n] boshlab aylanib, eng kichik elementni topib 🧐, uni 2-pozitsiyada turgan element bilan joylarini almashtirasiz. Bundan so'ng bizda ikkita o'sish tartibda joylashgan element bo'ladi.

3. ✅ Massivni oxirgacha tartiblash uchun bu harakatlarni n-1 marta takrorlaysiz.

Manbalar:
1. Selection sort in C

Omad! ✌️😎

@leetcodin

😄😄😄

🇬🇧 Guess which sorting algorithm is next?
🇺🇿 Keyingi tartiblash algoritmini topa olasizmi?

🇬🇧 Insertion Sort.

Hi! Today is the day of insertion sort.

😇 Link to Github: Insertion sort
⏰ Time complexity: O(N ^ 2)
🔎 Space complexity: O(1)

🧑‍💻 Approach🧑‍💻

1. 🧐 Start from the 1-indexed element. Save it into a temporary variable.

2. 🧐 Move all elements, greater than temp, from left to right.

3. 🧐 Put temp element to the start of moved elements.

3. ✅ Repeat this until current position reaches the array length to sort the array.

Sources:
1. Insertion Sort

Good luck! ✌️😎

@leetcodin

🇺🇿 Insertion Sort
[Kiritish orqali tartiblash usuli]

Salom! Bugun kiritish orqali tartiblash usulini ko'rib chiqaman.

😇 Github: Insertion sort
⏰ Time complexity: O(N ^ 2)
🔎 Space complexity: O(1)

🧑‍💻 Izoh 🧑‍💻

1. 🧐 Indeksi 1ga teng bo'lgan elementdan boshlaysiz. Bu elementning qiymatini temp [vaqtincha] o'zgaruvchisiga saqlaysiz.

2. 🧐 Temp-dan chapda turgan va undan katta bo'lgan elementlarni o'ngga surasiz.

3. 🧐 temp-ni surilgan elementlarning boshiga kiritasiz.

3. ✅ Shu harakatlarni indeks berilgan massivning uzunligiga teng bo'lmagunicha takrorlaysiz.

Manbalar:
1. Insertion Sort

Omad! ✌️😎

@leetcodin

😄😄😄

🇬🇧 Empty array is shocked...
🇺🇿 Bo'sh massiv Kusto hayratda...

P.S. Aytgancha, kecha 200dan ko'p yangi obunachilar kelibdi. Kim kanalga havola berganligini aytsangizlar.
Kanal shuncha odamga qiziq bo'lganidan xursandman.🏥

P.S.S.
Huge posts are coming...
Katta postlar kelmoqda...

🇬🇧 Merge Sort.

Hi! A big topic is here - Merge Sort. Let's try to sort things out. 😁😄😁

😇 Link to Github: MergeSort
⏰ Time complexity: O(N * logN)
🔎 Space complexity: O(N)

🧑‍💻 Idea 🧑‍💻

Merge sort is a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

In simple terms, we can say that the process of merge sort is to divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted.

Why merge sort is cool? Because its time complexity is more efficient than quadratic complexity algorithms such as Bubble sort, Selection sort, and Insertion sort.

🧑‍💻 Algorithm 🧑‍💻

If you look at code we have 3 methods: mergeSort(), recursiveMergeSort(), and merge().

NB: We don't use new subarrays for each recursive call. Only one extra array of the same length is used as a work space instead. This is achieved because we will work with indices of elements.

👩‍💻 mergeSort():
- Create an array with the same size to use as a work space.
- Call recursiveMergeSort() and pass work space array, lower bound (0) and upper bound (last index of the array).

👩‍💻 recursiveMergeSort():
This method is used to divide the array and then merge parts.
- If lower bound and upper bound are equal, then finish current execution of the method.
- Else we calculate middle index, which will find the middle for given boundaries. Then we recursively call this method for left half and then for right half. After that, we merge two halves.

👩‍💻 merge():
This method is used to merge two halves.

- We declare lower bound and have low pointer. Low pointer is the index from which we start adding numbers from left half (from lower bound to middle). We also have high pointer and upper bound (start and end of the second half respectively.

- In the first while loop we you add elements to workspace array from two halves from least to highest.

- In the second while loop you add the rest elements (if we have) to workspace array from the left half.

- In the third while loop you add the rest elements (if we have) to workspace array from the right half.

- Inside for loop we add sorted part of the initial array to it.

☝️Sources:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. Wikipedia

So, this is it.
If you need detailed explanation of some parts then let me know.

Good luck! ✌️😎

@leetcodin

🇺🇿 Merge sort. Birlashtirish orqali massivni tartiblash.

Salom! Bugun ancha qiyinroq mavzu - Birlashtirish orqali massivni tartiblash. Keling birgalashib, massivni tartibga solib qo'yamiz. 😁😄😁

😇 Github: MergeSort
⏰ Time complexity: O(N * logN)
🔎 Space complexity: O(N)

🧑‍💻 G'oya 🧑‍💻

Birlashtirish orqali massivni tartiblash algoritmi berilgan massivni kichikroq massivlarga bo'lish va har bir kichik massivni tartiblash, keyin shu tartiblangan kichik massivlardan katta massivni birlashtirish orqali ishlaydi.

Boshqa so'z bilan aytganda, siz berilgan massivni ikkita teng massivga bo'lasiz, har birini tartiblaysiz va keyin ularni bir qayta birlashtirasiz. Bu jarayonni to'la massiv tartibga solingani qadar bajarasiz.

Nimaga bu algoritm zo'r? Chunki uning tezligi boshqa o'tilgan algoritmlardan [Bubble tartiblash, Selection tartiblash va Kiritish orqali tartiblash] ancha tezroq. Chiziqli funksiya logarifmlik funksiyaga ko'paytirilgan funksiyani kvadrat funksiya bilan taqqoslashtiring.

🧑‍💻 Algorithm 🧑‍💻

Agar code-ga qarasangiz, siz 3ta metodni ko'rasiz. Bular mergeSort(), recursiveMergeSort() va merge().

Ahamiyat bering: Men ishlatgan usulda yangi kichik massivlarni yaratilmaydi. Buning o'rniga bitta uzunligi teng massiv yaratiladi va u elementlarni vaqtincha saqlab turish uchun ishlatiladi. Bunga elementlarning indekslarini chegaralar sifatida ishlatilish orqali erishiladi.

👩‍💻 mergeSort():
- workSpace massivini elementlarni vaqtincha saqlash uchun ishlatasiz.
- recursiveMergeSort() metodini chaqirasiz va unga parametrlar sifatida workSpace, chap chegara va o'ng chegaralarni berib yuborasiz.

👩‍💻 recursiveMergeSort():
Bu metod berilgan massivni teng qismlarga bo'lib chiqish va keyin ularni ulash uchun ishlatiladi.
- Agar chap va o'ng chegaralar teng bo'lsa, metod hozirgi bajarilishini to'xtatasiz.
- Aksincha massivning o'rta indeksini topasiz. Bundan so'ng rekursiv tarzda shu metodni chap qism va o'ng qism uchun bajarasiz. Keyin esa ikkita qism birlashtiriladi.

👩‍💻 merge():
Bu metod ikkita (yarim) qismni birlashtirish uchun ishlatiladi.

- Sizda chap chegara va chap chegara yana alohida ko'rsatgich bo'ladi. Chap chegara ko'rsatgichi bu vaqtincha massivga chap tarafdan qo'shiladigan elementning ko'rsatgichidir. Sizda yana o'ng chegara va o'ng qismning boshini ko'rsatuvchi o'zgaruvchi bo'ladi. Bular o'ng tarafda qo'shiladigan elementlarning chegaralarni ko'rsatuvchi sonlar.

- Birinchi while loop ichida siz ikkita qismdan eng kichik elementdan boshlab, eng katta elementgacha workSpace massiviga kiritib chiqasiz.

- Ikkinchi while loop ichida chap qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.

- Uchinchi while loop ichida esa o'ng qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.

- for loop ichida biz merge() metodining hozirgi bajarilishida tartiblangan elementlarni berilgan massivga yozib qo'yamiz.

☝️ Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. Wikipedia

Bugunga shu.
Agar qaysidir qism bo'yicha savollaringiz bo'lsa, comments-da yozing.

Omad! ✌️😎

@leetcodin

😄😄😄

That's what I use

🇬🇧 Quick Sort.

Hi! Another big topic - Quick sort.
😇 Link to Github: QuickSort
⏰ Time complexity: Best case O(N * logN), worst case O(N ^ 2)
🔎 Space complexity: O(1)

🧑‍💻 Idea 🧑‍💻

Quick sort is a sort of sorting algorithms which is faster than simple sorting algorithms such as as Bubble sort, Selection sort, and Insertion sort.

There are three basic steps:
- Partition the array or subarray into left (smaller keys) and right (larger keys) groups.
- Call ourselves to sort the left group (recursively).
- Call ourselves again to sort the right group (recursively).

To partition data means to separate it into two groups against chosen number (pivot), so that all numbers with lower value go to the one (left) group and numbers with higher value go to the second (right) group.

🧑‍💻 Algorithm 🧑‍💻

If you check the solution you can see that I have QuickSort class with a field array to store given array which I need to sort.
Then you can see four methods: quickSort(), recursiveQuickSort(), partitionIt(), and swap().

👩‍💻 quickSort()
This method assign given array to the array field and calls recursiveQuickSort() with array's zero and last index.

👩‍💻 recursiveQuickSort()
- We have base case for recursive method.
- Inside else statement we do 4 things:
1. Select pivot. We select the rightmost element from the current range.
2. We find the index of first element of the right group for current range by calling partitionIt(). This method moves all lower numbers to the left and greater numbers to the right. Then it returns start index of the right group.
3. Then we recursively call current method for left (partitioned) group.
4. Then we recursively call current method for right (partitioned) group.

👩‍💻 partitionIt()
Here we begin with indices of leftmost and rightmost elements for a given range.
We have outer while loop and two inner while loops.
- The first inner while loop finds the index of the first element which is greater than pivot starting from left.
- The second inner while loop finds the index of the first element which is lower than pivot starting from right.
- If these two pointing indices are equal or the left one is greater than the right index it means that numbers in given range are partitioned into two groups. So, we stop the outer while loop.
- If left index pointer is lower than the right pointer index, then we swap these two number. This operation helps us to move elements lower than pivot to the left and the elements greater than pivot to the right parts.

When we stop the outer while loop we swap elements with leftPointer and right indices. By this action we put the pivot to the place, where the elements on the left side are lower and the elements on the right side are greater.

In the end we just return pivot's index.

👩‍💻 swap()
This is a regular swap action, where you change the positions of two elements using their indices.

Sources:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Quick Sort in 4 minutes
3. Quick Sort gif

This is it.
If you need detailed explanation of some parts then let me know.

Good luck! ✌️😎

@leetcodin

🇺🇿 Tez Tartiblash. Tartiblash algoritmlari.

Salom! Bugun ham katta mavzu - Tez tartiblash [Quick sort].

😇 Github: QuickSort
⏰ Time complexity:
Eng yaxshi holat: O(N * logN),
Eng yomon holat: O(N ^ 2).
🔎 Space complexity: O(1).

🧑‍💻 G'oya 🧑‍💻

Quick sort bu tezligi kvadrat funksiyaga ega bo'lgan tartiblash algoritmlardan [Bubble sort, Selection sort, and Insertion sort] ancha tezroq ishlaydigan algoritm (o'rta holatda).

Bu algoritm uchta qismdan iborat:
- Massivni yoki uning qismini ikki qismga bo'lish. Chap qismida asos qilib olingan sondan kichikroq va o'ng qismida shu sondan kattaroq elementlar joylashtiriladi.
- Huddi shu metodni rekursiv chaqiruv orqali chap qism uchun ishlatish.
- Shu metodni rekursiv chaqiruv orqali bu safar o'ng qism uchun ishlatish.

Massivni kichikroq qismlarga bo'lish deganda massivni ikkita guruhga asos (tayanch) qilib oningan songa qarshi bo'lishni tushunish kerak. Shunda chap guruhdagi sonlar tayanch sondan kichikroq va o'ng guruhdagi sonlar esa shu tayanch sonidan kattaroq bo'lishi lozim.

🧑‍💻 Algoritm 🧑‍💻

Tepada Github-dagi yechimga havola qoldirganman.
Shu yechimda hamma logic QuickSort klassining ichida. Bu klassda array massivi bor. U tartiblash uchun berilgan massivga ko'rsatgichni saqlaydi.
QuickSort klassida yana 4 metod bor. Bular quickSort(), recursiveQuickSort(), partitionIt() va swap().

👩‍💻 quickSort()
Klassga tegishli massiv o'zgaruvchisiga berilgan massivni yozib qo'yadi. Keyin esa recursiveQuickSort() rekursiv metodini 0 va oxirgi indekslar uchun chaqiradi.

👩‍💻 recursiveQuickSort()
- Boshida rekursiya uchun asosiy holat tekshiriladi.
- else blokining ichida quyidagi 4ta harakat bajariladi:
1. Tayanch sonini tanlaysiz. Buning uchun berilgan diapazondan oxirgi elementni tanlaysiz.
2. partitionIt() metodini chaqirish orqali shu tayanch sonining indeksi aniqlanadi. Bu metod tayanchdan kichik sonlarni chapga va kattaroq sonlarni o'nga joylashtiradi.
3. Keyin rekursiv chaqiruv orqali recursiveQuickSort() metodini chap guruh uchun chaqirasiz.
4. Bundan keyin rekursiv chaqiruv orqali recursiveQuickSort() metodini o'ng guruh uchun chaqirasiz.

👩‍💻 partitionIt()
Metodning boshlanishida berilgan diapazon [left - right] ichida bosh va oxirgi indekslar uchun alohida int o'zgaruvchilarini yaratasiz.
Bulardan keyin bitta tashqi va ikkita ichki while loop-lar joylashgan.
- Birinchi ichki while loop tayanch sondan katta bo'lgan birinchi sonning indeksini topib beradi.
- Ikkinchi ichki while loop esa tayanch sondan kichik bo'lgan oxirgi sonning indeksini topadi.
- Agar shu ikkita indeks teng bo'lsa yoki leftPointer rightPointer-dan kattaroq bo'lsa, unda berilgan diapazondagi sonlar tayanch songa nisbatan to'g'ri taqsimlangan. Bu holatda tashqi loop-dan chiqib ketiladi.
- Agar chap ko'rsatgich indeks o'ng ko'rsatgich indeksdan kichik bo'lsa, biz shu indeks ostida joylashgan elementlarning swap() orqali joylarini almashtiramiz.
Bu harakatlar orqali siz tayanch sondan kichik sonlarni chapga va undan katta sonlarni unga nisbatan o'nga joylashtirasiz.

Tashqi while loop-dan chiqqaningizda swap() orqali tayanch sonini o'z o'rniga qo'yasiz.
Oxirida esa shu sonning indeksini qaytarasiz.

👩‍💻 swap()
Bu oddiy ikkita elementni indekslari bo'yicha joylarini almashtiruvchi metod.

Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Quick Sort in 4 minutes
3. Quick Sort gif

Bugunga shu.
Agar xatolar topsangiz yoki qaysidir qism bo'yicha savollaringiz bo'lsa, comments-da yozing.

Omad! ✌️😎

@leetcodin