1️⃣0️⃣ List Sorting Techniques
Let's explore 10 famous sorting techniques through this introductory of Data Structures and Algorithms (DSA) series.
🧵 👇
Let's explore 10 famous sorting techniques through this introductory of Data Structures and Algorithms (DSA) series.
🧵 👇
We will discuss about
1️⃣ Bubble Sort
2️⃣ Selection Sort
3️⃣ Insertion Sort
4️⃣ Merge Sort
5️⃣ Quick Sort
6️⃣ Counting Sort
7️⃣ Radix Sort
8️⃣ Bucket Sort
9️⃣ Heap Sort
1️⃣0️⃣ Shell Sort
↓
1️⃣ Bubble Sort
2️⃣ Selection Sort
3️⃣ Insertion Sort
4️⃣ Merge Sort
5️⃣ Quick Sort
6️⃣ Counting Sort
7️⃣ Radix Sort
8️⃣ Bucket Sort
9️⃣ Heap Sort
1️⃣0️⃣ Shell Sort
↓
1️⃣ Bubble Sort
✪ Compare 2 consecutive elements. Swap if 1st one is larger than 2nd one.
✪ At the end of each iteration, largest element in the list bubbles up to the top of the list.
✪ Compare 2 consecutive elements. Swap if 1st one is larger than 2nd one.
✪ At the end of each iteration, largest element in the list bubbles up to the top of the list.
2️⃣ Selection Sort
✪ The list is scanned for the smallest element.
✪ At the end of each iteration, this smallest element is swapped with the first element in the list.
✪ The list is scanned for the smallest element.
✪ At the end of each iteration, this smallest element is swapped with the first element in the list.
3️⃣ Insertion Sort
✪ An element in the list is picked and compared with all other elements prior to it in a reverse order.
✪ If the element is smaller than the compared element, later is shifted to right. Or else the element is inserted next to the compared element.
✪ An element in the list is picked and compared with all other elements prior to it in a reverse order.
✪ If the element is smaller than the compared element, later is shifted to right. Or else the element is inserted next to the compared element.
4️⃣ Merge Sort
It uses Divide-and-Conquer and Recursions.
✪ A list is divided in 2 equal halves. Each half goes for a recursion (calling same function).
✪ It is expected to receive 2 sorted sub lists at the end of recursion
✪ Merge 2 sorted sub lists for a full sorted list
It uses Divide-and-Conquer and Recursions.
✪ A list is divided in 2 equal halves. Each half goes for a recursion (calling same function).
✪ It is expected to receive 2 sorted sub lists at the end of recursion
✪ Merge 2 sorted sub lists for a full sorted list
5️⃣ Quick Sort
It uses Divide-and-Conquer and Recursions
✪ A pivot element is chosen and checked for an appropriate position in the list so that smaller elements are left to it and larger elements are right to it
✪ The left and right sub lists do the same through recursion
It uses Divide-and-Conquer and Recursions
✪ A pivot element is chosen and checked for an appropriate position in the list so that smaller elements are left to it and larger elements are right to it
✪ The left and right sub lists do the same through recursion
6️⃣ Counting Sort
✪ The list is scanned for the maximum element
✪ Another list (count list) is created of size (max element + 1) with all 0s.
✪ The list is traversed and count list is updated accordingly with appropriate count.
✪ Based on counts, list is sorted.
✪ The list is scanned for the maximum element
✪ Another list (count list) is created of size (max element + 1) with all 0s.
✪ The list is traversed and count list is updated accordingly with appropriate count.
✪ Based on counts, list is sorted.
7️⃣ Radix Sort
✪ Find the max value in the list. Find out how many digits it has.
✪ Starting from units, then to tens and hundreds etc arrange the elements based on sorted numbers in that digit place.
✪ Find the max value in the list. Find out how many digits it has.
✪ Starting from units, then to tens and hundreds etc arrange the elements based on sorted numbers in that digit place.
8️⃣ Bucket Sort
It uses Scatter-Gather approach
✪ First a bucket list is created. Each bucket in the list can contain elements of certain range.
✪ Elements are scattered to buckets
✪ Each bucket is sorted (other sorting technique)
✪ Elements from all buckets are gathered
It uses Scatter-Gather approach
✪ First a bucket list is created. Each bucket in the list can contain elements of certain range.
✪ Elements are scattered to buckets
✪ Each bucket is sorted (other sorting technique)
✪ Elements from all buckets are gathered
9️⃣ Heap Sort
It uses heap data structure.
✪ Elements are kept in heap either in Min-Heap or, Max-Heap.
✪ The root is swapped with the right most child node and, then removed from the heap.
✪ Then the heap is heapified and this process continues till the heap is empty.
It uses heap data structure.
✪ Elements are kept in heap either in Min-Heap or, Max-Heap.
✪ The root is swapped with the right most child node and, then removed from the heap.
✪ Then the heap is heapified and this process continues till the heap is empty.
1️⃣0️⃣ Shell Sort
✪ It uses insertion sort mechanism. But instead of scanning elements one-by-one, it uses a sequence.
Example of a sequence: N/2, N/4, N/8 where N is size of list.
✪ So after each iteration, elements at particular intervals (based on sequence) are sorted.
✪ It uses insertion sort mechanism. But instead of scanning elements one-by-one, it uses a sequence.
Example of a sequence: N/2, N/4, N/8 where N is size of list.
✪ So after each iteration, elements at particular intervals (based on sequence) are sorted.
That's it guys.
All these sorting techniques will individually be described in a 🧵 as part of DSA series. It will be explained both in written and visual format.
Stay tuned for the upcoming threads in this series.
See you soon 👋
All these sorting techniques will individually be described in a 🧵 as part of DSA series. It will be explained both in written and visual format.
Stay tuned for the upcoming threads in this series.
See you soon 👋
• • •
Missing some Tweet in this thread? You can try to
force a refresh
