Sorting Techniques

   What is Sorting?

A.      Sorting

Sorting means arranging the objects or anything in some specified manner, when concerned with the data structures, sorting is arranging data in a specified manner i.e., data placed in order with some condition or it may also be w.r.t a category like,

1.            Sorting data or objects in ascending or descending order based on some parameter like height, etc.

2.            Sorting objects on category and so on.

Sorting w.r.t data structures as mentioned earlier refers to arranging of data in some pattern. Now we will see, everything about sorting w.r.t data structures only,

 Sorting Techniques

Sorting techniques refers to the different ways of sorting the data in the specified manner. In data structures there are many ways of sorting data, each of them has their own advantages and disadvantages. So, let us understand about the different sorting techniques in data structures and algorithms.

  Different Sorting Techniques.

As per various sources and Wikipedia there are almost close to 43 sorting techniques, but this number may vary from source to source however, we will be analysing only the frequently used 10 sorting techniques.

 So, lets start,

1.       Bubble Sort:

B. Bubble Sort                                    

Bubble sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. It is called "bubble sort" because smaller elements "bubble" to the top of the list while larger elements "sink" to the bottom.

Algorithm:

1. Start with the first element (i.e., index 0) in the list.
2. Compare this element with the next element (i.e., index 1). If the first element is greater than the second element, swap them.
3. Move to the next pair of elements (index 1 and index 2) and compare them. Again, if the first element is greater, swap them.
4. Continue this process, comparing and swapping adjacent elements, until you reach the end of the list. At this point, the largest element in the unsorted portion of the list will have "bubbled up" to the last position.
5. Repeat steps 1-4 but exclude the last element (which is already in its correct sorted position) and continue from the beginning of the list up to the second-to-last unsorted element.
6. Continue this process until no more swaps are made during a pass through the list. This indicates that the list is fully sorted.
7. The algorithm is complete, and the list is now sorted in ascending order.

Pseudo Code:

Time & Space Complexity: 

-Worst-case time complexity is O(n2). 

-The bubble sort has a space complexity of O(1).

2.       Merge Sort:

C.      Merge Sort

Merge sort is a widely used comparison-based sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer paradigm, breaking down the sorting task into smaller, more manageable subproblems. The primary idea behind merge sort is to repeatedly divide the unsorted list into two halves, sort each half independently, and then merge the two sorted halves back together to create a single sorted list.

Algorithm:           

1. If the length of the array is 1 or 0, it is already sorted, so return the array.
2.  Divide the unsorted array into two equal halves by finding the middle point. You can calculate the middle point by (start + end) / 2, where start is the beginning index, and end is the ending index of the array.
3. Recursively apply merge sort to the left and right halves of the array.
4.  Call mergeSort(arr, start, middle) for the left half.
5. Call mergeSort(arr, middle + 1, end) for the right half.
6.  Merge the two sorted halves back together to create a single sorted array. This is done by comparing elements from the left and right subarrays and placing them in ascending order in a temporary array.
7.  Copy the merged elements from the temporary array back into the original array, ensuring it's sorted.

Pseudo Code:   

Time & Space Complexity: 

-Worst-case time complexity is O(n*log(n)). 

-The space complexity is O (1).

3.       Quick Sort.

D.         Quick Sort

Quicksort is another popular and efficient comparison-based sorting algorithm. It follows the divide-and-conquer paradigm, like merge sort, but it has a different approach. Quicksort selects a "pivot" element and partitions the array into two subarrays: elements less than the pivot and elements greater than the pivot. It then recursively sorts both subarrays. The pivot selection and partitioning process are key to its performance. 

Algorithm:           

1. Choose a pivot element from the array.
2. Partition the array into two subarrays: elements less than the pivot and elements greater than the pivot.
3. Recursively apply quicksort to both subarrays.
4. Combine the sorted subarrays with the pivot to form the final sorted array.

Pseudo Code:   

Time & Space Complexity: 

-Worst-case time complexity: O(n^2)

-Quicksort has a space complexity of O (log n)

4.       Selection Sort:

E.      Selection Sort

Selection sort is a straightforward comparison-based sorting algorithm known for its simplicity but is less efficient compared to other sorting algorithms like merge sort. It operates by dividing the array into two subarrays: the sorted subarray and the unsorted subarray. The primary idea behind selection sort is to repeatedly select the minimum (or maximum) element from the unsorted subarray and move it to the end (or beginning) of the sorted subarray, gradually expanding the sorted subarray until the entire array is sorted.

Algorithm:           

1. If the length of the array is 1 or 0, it is already sorted, so return the array.

2. Initialize a variable min_index to keep track of the minimum element's index.

3. For each iteration from 0 to n-1, where n is the length of the array:

   I. Set min_index to the current iteration index.

   II. Iterate through the remaining unsorted subarray and find the index of the minimum element.

   III. Swap the element at the current iteration index with the element at min_index.

Pseudo Code:   

Time & Space Complexity: 

- Worst-case time complexity is O(n^2).

- Selection sort has a space complexity of O(1) since it performs in-place sorting.

5.       Insertion Sort:

F.      Insertion Sort

Insertion sort is a simple and efficient comparison-based sorting algorithm. It builds the final sorted array one item at a time by repeatedly taking an element from the unsorted part and inserting it into its correct position in the sorted part of the array. The primary idea behind insertion sort is to divide the array into two subarrays: the sorted subarray and the unsorted subarray. It then iteratively selects elements from the unsorted subarray and inserts them into their correct position within the sorted subarray.

Algorithm:           

1. If the length of the array is 1 or 0, it is already sorted, so return the array.

2. Iterate through the unsorted subarray, starting from the second element (index 1).

3. For each element in the unsorted subarray:

   I. Compare the element with the elements in the sorted subarray from right to left.

   II. Shift the elements in the sorted subarray to the right until the correct position for the current element is found.

   III. Insert the current element into the sorted subarray at the correct position.

Pseudo Code:   

Time & Space Complexity: 

- Worst-case time complexity is O(n^2).

- Insertion sort has a space complexity of O(1) since it performs in-place sorting.

6.       Heap Sort:

G.      Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements.

Algorithm:           

1. Build a max heap from the input array.
2. The max heap property ensures that the largest element is at the root.
3. Swap the root element (the largest) with the last element in the heap.
4. Reduce the size of the heap by one.
5. Re-heapify the root node to maintain the max heap property.
6. Repeat steps 3-5 until the heap is empty.
7. The elements are now sorted in ascending order.

Pseudo Code:   

  

Time & Space Complexity: 

 -Worst-case time complexity is O(n*log(n)).

- The space complexity is O(1).

7.       Bucket Sort:

H.     Bucket Sort

Bucket Sort is a sorting algorithm that distributes elements into a finite number of buckets and then sorts each bucket individually, tyapically using another sorting algorithm like insertion sort.

Algorithm:           

1. Create an array of buckets.
2. Divide the range of input values into these buckets, and distribute each element into its corresponding bucket.
3. Sort each bucket, either recursively using the bucket sort itself or by using another sorting algorithm like insertion sort.
4. Concatenate the sorted buckets to get the final sorted array.

Pseudo Code:   

Time & Space Complexity: 

Worst-case time complexity is O(n^2). 

The space complexity is O (n+k).

8.       Radix Sort:

 I.      Radix Sort

Radix Sort is a non-comparative integer sorting algorithm that sorts elements by processing individual digits of the numbers from the least significant digit (LSD) to the most significant digit (MSD). 

Algorithm:           

1. Determine the maximum number of digits (d) in the input array.
2. Start from the least significant digit (rightmost) and go to the most significant digit (leftmost).
3. For each digit position (from LSD to MSD), use a stable sorting algorithm (typically counting sort) to sort the elements based on that digit.
4. Repeat the process for all digit positions.
5. The array is now sorted.

Pseudo Code:   

Time & Space Complexity: 

Worst-case time complexity is O(d*(n+k)). 

The space complexity is O (n).

9.       Comb Sort:

 J.      Comb Sort

Comb Sort is a comparison-based sorting algorithm and an improvement over the bubble sort algorithm. It works by repeatedly swapping and comparing adjacent elements with varying gap sizes, making it a more efficient alternative to bubble sort.

Algorithm:           

1. Start with a gap value (typically initialized to the length of the array).
2. Compare elements that are "gap" positions apart and swap them if they're out of order.
3. Reduce the gap by a shrink factor (usually around 1.3) until it becomes 1.
4. Repeat steps 2 and 3 until the gap becomes 1.
5. Continue swapping and comparing adjacent elements until the array is sorted.

Pseudo Code:   

 

Time & Space Complexity: 

Worst-case time complexity is O(n^2). 

The space complexity is O (1).

10.   Exchange Sort:

K.      Exchange Sort

Exchange Sort, also known as Bubble Sort, is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Algorithm:           

1. Start at the beginning of the list.
2. Compare the first two elements. If they are out of order, swap them.
3. Move one position to the right and repeat the comparison and swap until you reach the end of the list. This "bubbles" the largest element to the end.
4. Repeat steps 1-3 for the remaining elements (excluding the already sorted ones).
5. Continue these passes until no more swaps are needed, indicating that the list is sorted.

Pseudo Code:   

   

Time & Space Complexity: 

Worst-case time complexity is O(n^2). 

The space complexity is O (1).

Conclusion

The blog thus gives the information about the various types of sorting techniques in Data Structures, still as is it said that "Sky is the Limit.", yet hope you have liked the provided small information and hopefully again it benefits you in all possible manner that it should. 

With this information it would be easy for you to take a decision as to which algorithm to choose by looking at the various complexities provided and as per the need of your project.

THANK  YOU ALL 😇!!

Refences:

[A].     https://149695847.v2.pressablecdn.com/wp-content/uploads/2022/07/Sorting-Image.jpg

[B].    https://upload.wikimedia.org/wikipedia/commons/e/ef/Sorting_shaker_sort_anim.gif

[C].     https://cdn.emre.me/sorting/merge_sort.gif        

[D].    https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif

[E].     https://upload.wikimedia.org/wikipedia/commons/3/3e/Sorting_selection_sort_anim.gif

[F].     https://upload.wikimedia.org/wikipedia/commons/2/24/Sorting_insertion_sort_anim.gif

[G].  https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif

[H].    https://media.geeksforgeeks.org/wp-content/uploads/20210224162956/ezgifcomgifmaker14.gif

[I].        https://i.makeagif.com/media/7-17-2016/hlfsiC.gif

[J].       https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQZYk056OyTCAyBHk9f1YYtM_rSFK9LhwJKgF3u179R&s

[K].    https://upload.wikimedia.org/wikipedia/commons/e/ef/Sorting_shaker_sort_anim.gif