🎢 Sorting Algorithms, explained
❍ 10 algorithms
❍ Time Complexities
❍ Space Complexities
A Beginner's Guide.
⇩
❍ 10 algorithms
❍ Time Complexities
❍ Space Complexities
A Beginner's Guide.
⇩
📖 Read it in an article
Did you like it? Do share your valuable feedback and help me to share more such articles in the future.
doc.clickup.com
Did you like it? Do share your valuable feedback and help me to share more such articles in the future.
doc.clickup.com
➊ Bubble Sort
➋ Insertion Sort
➌ Selection Sort
➍ Merge Sort
➎ Quick Sort
➏ Counting Sort
➐ Radix Sort
➑ Bucket Sort
➒ Heap Sort
➓ Shell Sort
➋ Insertion Sort
➌ Selection Sort
➍ Merge Sort
➎ Quick Sort
➏ Counting Sort
➐ Radix Sort
➑ Bucket Sort
➒ Heap Sort
➓ Shell Sort
➊ 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.
➂ The next iteration excludes the last element (i.e., largest element) in 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.
➂ The next iteration excludes the last element (i.e., largest element) in the list.
➋ Insertion Sort
➀ An element in the list is picked and compared with all other elements prior to it in reverse order.
➁ If the element is smaller than the compared element, later is shifted to the 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 reverse order.
➁ If the element is smaller than the compared element, later is shifted to the right. Or else the element is inserted next to the compared element.
➌ 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 next iteration excludes the first element (i.e., smallest 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.
➂ The next iteration excludes the first element (i.e., smallest element) in the list.
➍ Merge Sort
It uses Divide-and-Conquer & Recursions.
➀ A list is divided into 2 equal halves. Each half goes for a recursion (calling same function).
➁ It is expected to have 2 sorted sublists at the end of recursion
➂ Merge 2 sorted sublists to form a full sorted list
It uses Divide-and-Conquer & Recursions.
➀ A list is divided into 2 equal halves. Each half goes for a recursion (calling same function).
➁ It is expected to have 2 sorted sublists at the end of recursion
➂ Merge 2 sorted sublists to form a full sorted list
➎ Quick Sort
It uses Divide-and-Conquer & Recursions.
➀ A pivot element is chosen and checked for an appropriate position in the list such that smaller elements are left to it and larger elements are right to it
➁ The left and right sublists do the same through recursion
It uses Divide-and-Conquer & Recursions.
➀ A pivot element is chosen and checked for an appropriate position in the list such that smaller elements are left to it and larger elements are right to it
➁ The left and right sublists do the same through recursion
➏ 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 the count list is updated accordingly with an 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 the count list is updated accordingly with an appropriate count.
➃ Based on counts, list is sorted.
➐ 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.
➑ 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 in 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 in buckets
➂ Each bucket is sorted (other sorting technique)
➃ Elements from all buckets are gathered
➒ 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.
➓ 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.
➹ Time Complexity
The figures are arranged for the Best Case, the Worst Case, and the Average Case.
➀ Bubble Sort ➠ O(n), O(n²), O(n²)
➁ Selection Sort ➠ O(n²), O(n²), O(n²)
➂ Insertion Sort ➠ O(n), O(n²), O(n²)
➃ Merge Sort ➠ O(n*logn), O(n*logn), O(n*logn)
The figures are arranged for the Best Case, the Worst Case, and the Average Case.
➀ Bubble Sort ➠ O(n), O(n²), O(n²)
➁ Selection Sort ➠ O(n²), O(n²), O(n²)
➂ Insertion Sort ➠ O(n), O(n²), O(n²)
➃ Merge Sort ➠ O(n*logn), O(n*logn), O(n*logn)
➄ Quick Sort ➠ O(n*logn), O(n²), O(n*logn)
➅ Counting Sort ➠ O(n+k), O(n+k), O(n+k)
➆ Radix Sort ➠ O(n+k), O(n+k), O(n+k)
➇ Bucket Sort ➠ O(n+k), O(n²), O(n)
➈ Heap Sort ➠ O(n*logn), O(n*logn), O(n*logn)
➉ Shell Sort ➠ O(n*logn), O(n²), O(n*logn)
➅ Counting Sort ➠ O(n+k), O(n+k), O(n+k)
➆ Radix Sort ➠ O(n+k), O(n+k), O(n+k)
➇ Bucket Sort ➠ O(n+k), O(n²), O(n)
➈ Heap Sort ➠ O(n*logn), O(n*logn), O(n*logn)
➉ Shell Sort ➠ O(n*logn), O(n²), O(n*logn)
➹ Space Complexity
➀ Bubble Sort ➠ O(1)
➁ Selection Sort ➠ O(1)
➂ Insertion Sort ➠ O(1)
➃ Merge Sort ➠ O(n)
➄ Quick Sort ➠ O(logn)
➅ Counting Sort ➠ O(max)
➆ Radix Sort ➠ O(max)
➇ Bucket Sort ➠ O(n+k)
➈ Heap Sort ➠ O(1)
➉ Shell Sort ➠ O(1)
➀ Bubble Sort ➠ O(1)
➁ Selection Sort ➠ O(1)
➂ Insertion Sort ➠ O(1)
➃ Merge Sort ➠ O(n)
➄ Quick Sort ➠ O(logn)
➅ Counting Sort ➠ O(max)
➆ Radix Sort ➠ O(max)
➇ Bucket Sort ➠ O(n+k)
➈ Heap Sort ➠ O(1)
➉ Shell Sort ➠ O(1)
Hey 👋
I am a Tech Writer, Educator, and Mentor from India 🇮🇳, here sharing
✰ Tutorials
✰ Tricks
✰ Career Tips
✰ Cheat Sheets
✰ Practice Questions
✰ Roadmaps
on
➠ Web Development
➠ Data Structures and Algorithms
➠ Databases
Thanks for reading. 🙏
I am a Tech Writer, Educator, and Mentor from India 🇮🇳, here sharing
✰ Tutorials
✰ Tricks
✰ Career Tips
✰ Cheat Sheets
✰ Practice Questions
✰ Roadmaps
on
➠ Web Development
➠ Data Structures and Algorithms
➠ Databases
Thanks for reading. 🙏
جاري تحميل الاقتراحات...