All about Sorting
What is Sorting?
Sorting in general context means that it is the process of arranging the items from a collection in a particular order.
What does it mean in Computer Science?
When dealing with large amounts of data and analyzing for results may take a lot of time for a computer program to execute and print the result. So, the sorting technique can be applied through a method of Sorting algorithms in computer science.
Sorting Algorithms
Sorting algorithms are a set of instructions that take an array or list as an input and arrange the items into a particular order. These algorithms are algorithms that put elements of the array or list in a certain way. This category of algorithms is often come in handy for reducing the complexities of the code.
Complexity
It describes the amount of time and space it takes to run an algorithm.
These algorithms have a direct application in various other algorithms like searching algorithms etc.
These are some popular sorting algorithms:
1) Bubble Sort: This algorithm performs by repeatedly swapping the adjacent elements if they are not in order.
Ex: implementation of bubble sort on an array with elements 5,3,8,4,6
→ initial unsorted array
→ compares the 1st and 2nd elements.
Since 5 is greater than 3 it swaps.
→ after swapping it compares 5 with the next element
Since 5 is less than 8 it does not swap.
→ it compares the next two elements.
Since 8 is greater than 4 it swaps.
→it compares the next two elements.
Since 8 is greater than 6 it swaps.
→final sorted array.
It keeps repeating until there are no more swaps required.
Best Case complexities:
O(n)
Worst-Case complexities:
O(n²)
2) Selection Sort: This algorithm sorts an array by repeatedly finding the min element from an unsorted part and puts it in the beginning.
For every iteration, the min element from the unsorted subarray is moved to the sorted subarray.
Ex: implementation of selection sort on an array with elements 20,12,10,15,2
→checks if it is the min value at index 1.
→checks the next elements for min value at index 2.
→checks the next 2 elements for min value at index 3.
→min value at index 4.
→swaps the min value at index 4.
Best case complexities:
O(n²)
Worst-case complexities:
O(n²)
3) Merge Sort: Merge sort is a comparison-based sorting algorithm. Usually, in merge sort, we Divide the unsorted list or array into n sublists or subarrays, each containing 1 element. Then we repeatedly merge sublists or subarray to produce new sorted sublists or subarrays until there is only 1 sublist or subarray remaining.
The last sublist or subarray will be the sorted list or array.
It is a divide and conquer approach algorithm.
Ex:
Best case complexities
O (n*log n)
Worst-case complexity
O (n*log n)
4) Quick Sort: quick sort also uses divide and conquer like merge sort. But in quicksort, major work is done during the splitting of the array or list into subarrays or sub lists while in the case of merge sort it is done during the merging of subarrays or sub-lists.
This algorithm basically works in this way:
· A pivot element is selected from the array or list, it can be any element from the array or list either the first, last or any random element. Usually, it is the middle element.
· After the pivot is selected it then compares the remaining elements from the array or list.
· After comparison all the elements smaller than the pivot are placed to the left while the elements larger than the pivot are placed to the right of the pivot.
· Now, the elements in the left and right of the pivot are subarrays or sub lists and follow the same procedure as above.
Ex: implementation of quicksort on an array with elements 5,3,7,6,2,9
→selection of pivot element (6)
→selection of left and right pointers.
Comparing the left and right pointers with the pivot
Since 5<6 left shift occurs
→compares left elements with pivot.
Since 3<6 left shift occurs.
→compares left elements with pivot.
Since 7>6 it stops and starts comparing elements in the right.
→since 9>6 it shifts right
But 2<6 and it stops.
→swaps both 2 and 7.
→the pointer moves even further.
Since 6=6 it moves further and stops as left crosses right and vice versa.
Best case complexity:
O(n*log n)
Worst-case complexity:
O(n²)
5) Insertion Sort: insertion sort basically works by sorting one element at a time. It is more efficient than selection sort and bubble sort.
Insertion sort works as:
· We assume that the 1st element is already sorted so we store the second element in a variable known as a key.
· Now we compare the value of the key with the 1st element such that if the value of the key is less than the second element it swaps.
· In the same way it checks the 3rd element, if the 3rd element is the smallest it swaps it with the index 1 element.
· In the same way we repeat this process for the whole array.
Ex: implementation of insertion sort on an array 5,1,6,2,4,3
→initial array
→here 1<5 so it swaps with 5.
→here 5<6 so it remains the same.
And 6>1 so it does not swap with 5 and 1.
→now 2 is compared to all the elements before it.
2<6,2<5, so it is placed before 5.
Then it is compared to the element at index 1.
Since 2>1 it settles before 5.
→here 4 is compared to the elements before it.
4<6,4<5 so it is placed before 5 and now it is compared to the elements before it. 4>2,4>1, so it remains at that position.
→here 3 is compared to all the elements before it.
3 is compared to each element and placed at its position.
→final sorted array.
Best case complexities:
O(n)
Worst case complexities:
O(n²)
6) Heap Sort: Heap sort is more like a modified selection sort. The Heapsort algorithm involves preparing the list or array by first turning it into a max heap.
It works in the following ways:
· Build a function heapify (). This function basically helps in building a heap from a list or array.
· Swap the first element of the array with the final element of the array. Now decrease the range of the array by 1.
· Construct another function downshift () to shift the new first elements to its allocated index in the heap.
· Iterate this process till the size of the array becomes 1.
Ex:
Best Case complexity:
O (n*log n)
Worst-case complexity:
O (n*log n)
