Brief Explanation of Heap Sort and Bubble Sort
What is meant by sorting?
A sorting algorithm is a method for arranging a large number of items into a specific order. For example alphabetical, highest-to-lowest value, distance from shortest -to-lowest. So the sorting algorithm takes the list of items as an input and do the required operation on the list and deliver the ordered array as output.
Lets Compare selection and Heap Sort?
Heap sort was invented by John Williams. We know that heap sort is a sorting technique in the data structure, which is just opposite to the selection sort. In selection, we find the smallest element among n elements, So the smallest element among the n-1 elements. In heap, sort finds the largest element and keep its end of an array, and finds the second largest element and repeated the same process in all elements in it.
About Heap:-
Heap is a very useful data structure that every programmer should know well. The heap data structure is used in Heap Sort, Priority Queues. Heaps help us to understand memory management. Heap is a data structure that is complete a binary tree. We know that the binary tree means all levels are filled except at the last level.
There are two types of the heap:-
1. Max-heap: — A-Max Heap is basically a complete binary tree in which the Data present at the Root node is greater than or equal to all of its child nodes. In other words, the Root node has the Maximum value. This property must be true for every sub-tree.
2. Min-heap: — A Min Heap is basically a complete binary tree in which the Data present at the Root node is less than or equal to all of its child nodes. In other words, the Root node has the Minimum value. The property must be true for every sub-tree.
So we will discuss the Heap building, Heap Sort and time Complexity.
Discuss Heapify method:-
Heapify is the process of converting a binary tree into a Heap data structure. Heapify method is used to find the max heap in Heap sort. We can also find max heap in a general way but by using the heapify method the time complexity will be better than the normal method of heap sort.
1. We want to construct a max-heap. We start an algorithm with a node that is at the lowest level of the tree and has a children node.
2. So arrange the current node and its children nodes according to the max — heap property.
3. Once we have completed the steps, we continue the same steps to make sure that all subtrees are following the max-heap property.
4. So we call Max-Heapify( ) recursively and iterate back to the root that it has satisfied the max-heap property.
Heap Sort:
Heaps used in sorting an array. In the case of max-heaps, the maximum element is always present at the root of the heap. So we can use this property of the heap to sort an array.
In Heap Sort we need to pop out the max values, it means the root value. We need to repeat the heapify the tree and pop out the second largest value from the tree. Continue until every element is pop out.
Steps for heap sort:-
1. We need to build the max heap from the given array.
2.We got the max value at the root and swap it with the last element in the heap and reduce the size of the heap by one.
3. So repeat the last step until the size of the heap become the or and we got the elements in a corrected order.
Heapsort Time Complexity:-
●. Build max heap takes O(n/2) time
●. We are calling for heapify inside the for loop, which may take the height of the heap in the worst case for all comparison. Therefore time complexity will become O(nlogn)
●. Best Time Complexity: O(nlogn)
●. Average Time Complexity: O(nlogn)
●.Worst Time Complexity: O(nlogn)
Heap sort Space Complexity:
✓. No auxiliary space is required in Heapsort implementation that is we are not using any arrays, linked list, stack, queue, etc to store our elements
✓. Hence space complexity is: O(1)
Efficiency:-
Heap Sort algorithm was very efficient, and another sorting algorithm may slower exponential as the number of items in sort has increased, So the time taken for the heap sort is increases logarithmically. I will suggest that heap sort is suitable for the sorting of huge listed items.
Memory Usage:-
The Heap Sort algorithm can be implemented in place of the sorting algorithm. Its memory usage is minimal because apart from it is necessary to hold the initial list of items to be sorted. Heap sort no need for additional memory space for work. In terms of merge sort, it requires more memory space to work. And also quick requires more stack space for its recursive nature property.
Bubble Sort:
In Bubble sort, each element is compared with the adjacent element. Suppose the first element is smaller than the second element, then the position of each element is interchanged. So the next element is compared with its adjacent element, the same process is repeated for all the elements in the array. Until all the elements get sorted.
If the size of the array is n.
✦ The (n-1) comparisons are required in the first pass. From the above example, 8 comparisons are required to bubble up the 1 at the leftmost position.
✦ The (n-2) comparisons are required in the second pass. So the 2 will be bubbled up and moved to the second position.
✦ So repeat the same process.
Time Complexity:-
●.Time complexity of Bubble Sort is O(n²).
● The best-case time complexity will be O(n), it is when the list is already sorted.
● Worst Case Time Complexity and average time complexity of the bubble sort is O(n²).
●The space complexity for Bubble Sort is O(1) because only a single additional memory space is required. Bubble sort gives stable and in-place sorting.
Bubble Sort Vs Selection Sort :
●In Selection Sort, a maximum of n swap operations are required. In Bubble Sort, up to n swap operations happens for each element, it required the n² swap operations are required.
●These are the swap operations are memory intensive, so selection becomes even more efficient than Bubble Sort for larger lists.
●In short, Selection Sort is used normally in cases where writes are quite expensive than memory reads.
● However, both Selection and Bubble sorts are taken O(n²) time. So it not re-commanded to use in real-life applications.
Advantages:-
✦ it is popular and easy to implement.
✦ in the bubble sort, elements are swapped in place without using additional temporary storage, so the space requirement is at a minimum.
✦ Bubble sort gives stable and in-place sorting.
Disadvantages:-
✓. The bubble sort is the fact that it does not deal well with a list containing a huge number of items.
✓. The time — inefficient as it having o(n2) complexity.
