SORTING ALGORITHMS

 

Sorting Algorithms Beyond the Classroom

Introduction

In class, we studied several important sorting algorithms such as Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort, and Radix Sort. These algorithms form the foundation of sorting techniques.

However, there are many other sorting algorithms that are equally interesting and useful in different scenarios. In this blog, I explored a few additional sorting methods to understand how they work and where they are used.

Why Explore Other Sorting Algorithms?

While the algorithms taught in class are widely used, exploring additional methods helps in:

  • Understanding different problem-solving approaches

  • Learning optimization techniques

  • Knowing which algorithm works best in specific situations

1. Merge Sort

Idea

Merge Sort follows the Divide and Conquer approach:

  • Divide the array into halves

  • Sort each half recursively

  • Merge the sorted halves

Example

[5, 3, 8, 2] = [5,3] & [8,2] = [3,5] & [2,8] = [2,3,5,8]

Time Complexity

  • O(n log n)

Why I Chose This

Merge Sort is very efficient and stable. It works well for large datasets and linked lists.

2. Counting Sort

Idea

Instead of comparing elements, Counting Sort:

  • Counts how many times each value appears

  • Places them in correct positions

Example

Input: [4,2,2,1]
Count = [1:1, 2:2, 4:1]
Output = [1,2,2,4]

Time Complexity

  • O(n + k)

Why I Chose This

It is very fast when the range of numbers is small and avoids comparisons completely.

3. Bucket Sort

Idea

  • Divide elements into buckets

  • Sort each bucket individually

  • Merge all buckets

Example

[0.42, 0.32, 0.23] => Buckets => Sort => Merge

Time Complexity

  • O(n + k) (average case)

Why I Chose This

Works well for uniformly distributed data like decimals.

4. Shell Sort

Idea

An improved version of Insertion Sort:

  • Compare elements at a gap

  • Reduce the gap gradually

Example

Instead of comparing adjacent elements, it compares distant elements first.

Time Complexity

  • Depends on gap sequence ( O(n log n))

Why I Chose This

It improves the performance of insertion sort for larger arrays.

5. Tim Sort

Idea

  • Hybrid of Merge Sort and Insertion Sort

  • Used in real-world systems

Features

  • Used in Python and Java

  • Optimized for real-world data

Time Complexity

  • O(n log n)

Why I Chose This

It is used in practical applications, making it highly relevant.

Comparison with Classroom Algorithms

AlgorithmTypeTime ComplexityStable
Merge SortDivide & ConquerO(n log n)Yes
Counting SortNon-comparisonO(n + k)Yes
Bucket SortDistributionO(n + k)Yes
Shell SortGap-basedO(n log n)No
Tim SortHybridO(n log n)     Yes

CONCLUSION

Exploring sorting algorithms beyond the syllabus helped me understand that no single algorithm is best for all cases. Each algorithm has its own strengths depending on the type of data and constraints.

While the algorithms taught in class are fundamental, these additional methods provide deeper insight into how sorting can be optimized in real-world scenarios.

Comments

Post a Comment

Popular posts from this blog

THE DELIVERY MAN

  The Delivery Man – Python List Operations  Introduction Lists in Python are used to store multiple items in a single variable. They are flexible, allowing us to add, remove, update, and manipulate elements easily. In this task, different list operations are performed to simulate a delivery man's workflow. 1. Creating a list and accessing an item items = ["Notebook", "Pencil", "Eraser", "Ruler", "Marker"] print(items[2]) Approach: Indexing Why: Lists use zero-based indexing, so the third item is accessed using index 2. 2. Adding a new item items.append("Glue Stick") print(items) Approach: append() method Why: It adds an item at the end of the list, which is ideal for adding new deliveries. 3. Inserting an item items.insert(2, "Highlighter") print(items) Approach: insert() method Why: Used when we need to add an item at a specific position instead of the end. 4. Removing an item items.remove("Ruler...
Read more

EC2 LAUNCHING

  EC2 Step 1: Launch EC2 Instance Go to: AWS Console --> EC2 --> Launch Instance Configure: Name : my-web-server AMI : Amazon Linux 2 (easy for beginners) Instance Type : t2.micro (free tier) Step 2: Key Pair Create or select a key pair. Step 3: Network Settings  Allow these: SSH (port 22) --> for login  HTTP (port 80) --> for web access Step 4: Launch Instance Click Launch Instance Step 5: Connect to Instance Use: EC2 --> Connect --> EC2 Instance Connect (easiest) OR via terminal: with this command. for this you have to download the pem files while selecting the key pair.  ssh -i your-key.pem ec2-user@<public-ip> Step 6: Install Web Server For Amazon Linux: sudo yum update -y sudo yum install httpd -y Step 7: Start Web Server sudo systemctl start httpd sudo systemctl enable httpd Step 8: Add a Web Page echo "Hello from EC2" | sudo tee /var/www/html/index.html Step 9: Get Public IP Go to EC2 d...
Read more

SORT A LINKED LIST USING MERGE SORT

  Sort a Linked List using Merge Sort Introduction Sorting a linked list efficiently is a common problem in data structures. Unlike arrays, linked lists do not allow direct access to elements, so algorithms like quicksort are not ideal. Merge Sort is the best choice for linked lists because: It does not require random access It works efficiently with node-based structures Problem Statement Given the head of a linked list: Sort the list in ascending order Return the sorted linked list Example Input: 10 -> 30 -> 20 -> 40 -> 60 -> 50 Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60 Solution Code class Solution: def mergeSort(self, head): if not head or not head.next: return head mid = self.getMiddle(head) next_to_mid = mid.next mid.next = None left = self.mergeSort(head) right = self.mergeSort(next_to_mid) return self.merge(left, right) def getMiddle(self,...
Read more