What is Sorting in DSA?
- Sorting is a fundamental function in data structures and computer science.
- It is the process of organizing the contents of an array or list in a specific order in data structures and algorithms.
- There are various sorting algorithms that are regularly used in computer science, and the choice of method is determined by the problem’s unique needs.
Types of Sorting in DSA:
There are a number of sorting algorithms, we shall see some of the most commonly used sorting algorithms:
- Bubble Sort: This is a basic sorting algorithm that passes over the list periodically, compares nearby entries, and swaps them if they are out of order. The process is repeated until no further swaps are required.
- Selection Sort: This algorithm sorts an array by continuously selecting the first member from the unsorted portion of the array that is the smallest value.
- Insertion Sort: Another straightforward sorting technique, this one involves iterating through an array and placing each element in the appropriate location inside a new sorted array.
- Quick Sort: This divide-and-conquer method divides the remaining items into two sub-arrays based on whether they are less than or greater than the pivot element that is chosen from the array as its “pivot” element. The sub-arrays are then sorted recursively using the algorithm.
- Merge Sort: Another divide-and-conquer method, this one involves splitting the array in half, sorting each half again, and then joining the two sorted halves once more.
- Heap Sort: The Binary Heap data structure is used in this sorting technique to do comparison-based sorting. Each entry in the list is first removed from the heap portion of the list before being added to the sorted portion of the list.
- Radix Sort: Radix sorting is an integer sorting technique that uses integer keys as keys to order data by significant location and value (place value). An array of integers is sorted using a Radix sort using a counting sort function.
- Bucket Sort: Elements are sorted into several categories, commonly referred to as buckets, in bucket sorting. A bucket sort separates elements into regular groupings called buckets with a certain numerical order. Each bucket is sorted separately after being classified, either using a recursive sorting technique or a distinct sorting algorithm. The components are collected into groupings after sorting them.
Time complexity of the above-mentioned algorithms:
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Quick Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) |
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) |
| Merge Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) |
| Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) |
| Heap Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) |
Note: also read about DSA: Modular Arithmetic
Follow Me
Please follow me to read my latest post on programming and technology if you like my post.
https://www.instagram.com/coderz.py/
https://www.facebook.com/coderz.py
Staying up to the mark is what defines me. Hi all! I’m Rabecca Fatima a keen learner, great enthusiast, ready to take new challenges as stepping stones towards flying colors.