Thread by @swapnakpanda

10 Sorting Algorithms

⇩

⬒ Have you just started studying Data Structures and Algorithms?

⬓ Are you finding difficulties in understanding the sorting algorithms?

I will introduce you here to 10 different sorting algorithms by explaining each using simple terms.

📋 Table of Contents

➊ Bubble Sort
➋ Selection Sort
➌ Insertion Sort
➍ Merge Sort
➎ Quick Sort
➏ Counting Sort
➐ Radix Sort
➑ Bucket Sort
➒ Heap Sort
➓ Shell Sort
➒➑ Time Complexity
➒➒ Space Complexity

➊ 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.

➋ 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.

➌ 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.

➍ 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 have 2 sorted sub lists at the end of recursion

➂ Merge 2 sorted sub lists for a full sorted list

➎ 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

➏ 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.

➐ 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.

➑ 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

➒ 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.

➓ 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.

➒➑ Time Complexity

The figures are arranged as 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)

➒➒ 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)

💭 Final Words

⬒ This is an introductory to all sorting algorithms.

⬔ I am going to share details in coming days about each of these algorithms in my Blog.

⬓ You can find my blog posts 👇 Subscribe me there to receive notifications.

swapnakpanda.hashnode.dev

End of 🧵

Do you find this one useful? Share your thoughts.

I am regularly sharing tutorial type threads on Web Development (HTML, CSS, JavaScript, React, Node.js), Data Structures and, SQL/NoSQL.

If you are interested in these, Follow me ✅