Algorithms today are in great need, specially the one's having speed-up the process of what they are supposed to do. Making the algorithm run faster, or take up less space while executing is what many coders & designers have tried doing for generations. And the reason is due to the technological advancements in the real-world. We have tried our best to speed-up the process of heap sort, by logically modifying the algorithm.
It's just a start, so the positives & negatives are welcome regarding our paper.
ABSTRACT
Today there are several efficient algorithms that cope with the popular task of sorting. This paper presents the comparison between the classical heap sort and the new logical heap sort, which is a start for us. The reason of starting with heap sort was mainly because;it’s one of the efficient algorithms in sorting the elements for us, today. Many tests between the classical heap sort and the modified heap sort were run to lead us to the conclusion of this paper. We look forward to discover new logics in algorithms to make them more efficient using Vedic Mathematics. In short, make the algorithm reach its destination much faster.
Keywords: Complexity, Performance of Algorithm, Heapsort, Sorting, Heap Property
INTRODUCTION
A heap is either a large area of memory which is used by the programmer to dynamically allocate or de-allocate them or, it is a balance, left-justified binary tree where every parent’s value is larger compared to its children. The heap sort uses the second definition[1].The heap sort, at present, is one of the fastest sorting algorithms with both its worst case and average case runtime being the same, O (n log n)[3]. Thus, it makes the algorithm most important in the sorting category. Heap sort is a comparison-based sorting algorithm. In the classical heap sort, a max or the min heap is formed before the sorting takes place. In the max heap, the largest element present in the whole heap is shifted to the top. Whereas, in the min heap the minimum element present in the heap is shifted to the top of the heap[2]. The minimum element (from the min-heap) or the maximum element (from the max-heap) is extracted from the heap, till none remains in it, the values extracted in a sorted order[3]. Each extraction from the heap puts the element at the last empty location in the array in a sorted order, the rest of it being unsorted. For heap sort to be applied, the tree has to obey the heap property. The property states that every node’s children should have smaller value compared to the nodes’ value itself[5]. If at any point in the heap we find it being disobeyed, we compare the values from among the node and its children, and then put the larger value in the parent. This process continues till every node in the heap, follows this property.
THE HEAP SORT
How the heap sort works, we have considered the following situation.
Abbildung in dieser Leseprobe nicht enthalten
Fig 1.
The unsorted array taken by us, is constructed into somewhat we call a tree structure. Each node of the tree has either two children or, one child or, has no child at all. The ones with no child are called as the Leaf nodes. Each node of a tree consists of three parts- left child, the value of node &, the right child[8]. A node not having either of the children will have the value NULL. Now, each node will occupy 12 bytes- for a 32-bit system, which will make it needing more space on the memory. We surely do not want that as our aim is not only to speed up the process, but also require less space on our system. What we really follow is that instead of constructing the tree itself, we imagine it as a tree and instead of using pointers to point to the left & right of the node, we assign values to it as follows[10],
Abbildung in dieser Leseprobe nicht enthalten
For heap sort to be done, we need each node of the tree to follow the heap property, i.e.
Abbildung in dieser Leseprobe nicht enthalten
The parent in the heap is always the largest when compared to both its children. All leaf nodes will automatically follow the heap property[11]. A tree is a heap if all the nodes in it follow the heap property. If the heap property is found to be violated then, we exchange the value of the largest among the 3 nodes with the root’s value.
The first step in heap sorting is to build a MAX_ or MIN_HEAP.
Abbildung in dieser Leseprobe nicht enthalten
The creation of max heap or the min heap depends on the requirement of user. If sorting is to be done in ascending order, a max heap is built. Else, a min heap is built.In this function itself, another procedure MAX_HEAPIFY is called.
Abbildung in dieser Leseprobe nicht enthalten
This goes on building the heap by ignoring the leaf nodes (done by taking “i=heapSize/2” in BUILD_MAX_HEAP() ), and covers up all the nodes. The step wise iteration of the process is shown by the following snippets:
Abbildung in dieser Leseprobe nicht enthalten
Fig. 2a
Abbildung in dieser Leseprobe nicht enthalten
Fig. 2b
Abbildung in dieser Leseprobe nicht enthalten
Fig. 2c
The final result of the process is as shown in figure 3.
Abbildung in dieser Leseprobe nicht enthalten
Fig. 3
This is how the working of heap sort is done. The procedure till now is common to our modified algorithm. The algorithm changes from here on.
Abbildung in dieser Leseprobe nicht enthalten
THE LOGICALLY-MODIFIED ALGORITHM
Till now, we had kept exchanging the root element with the last element in the max heap one-by-one.What we tried, was exchanging 2 nodes at the same time which required less number of comparisons with each other and also, required less number of looping.
Abbildung in dieser Leseprobe nicht enthalten
This part of the algorithm is the modified algorithm of ours. The working of our logic is shown in following snippets,
Abbildung in dieser Leseprobe nicht enthalten Fig. 4a – Iteration 1
Abbildung in dieser Leseprobe nicht enthalten Fig. 4b - Iteration 2
Abbildung in dieser Leseprobe nicht enthalten Fig. 4c
Abbildung in dieser Leseprobe nicht enthalten Fig. 4d
Abbildung in dieser Leseprobe nicht enthalten Fig. 4e
Abbildung in dieser Leseprobe nicht enthalten
PERFORMANCE ANALYSIS
The following table gives out the average sorting time of both the heap sort and the modified heap sort algorithm. The values are taken randomly.
Table 1
Abbildung in dieser Leseprobe nicht enthalten
CONCLUSION
We have implemented both the algorithms for different number of data items. Our algorithm has successfully worked on limited data we had taken, and got satisfactory results. We have applied our algorithm for different number of data items, and also ran the algorithm in the worst possible case. The results of both algorithms varied and can be seen in the table above.
FUTURE SCOPE
What we are now trying is to seek, in the near future, a way to make our own algorithm more efficient, if possible. We are to do this by taking the help of Vedic Mathematics, which attempts on solving our day-to-day complex problems in the most efficient way.If it’s possible anyhow, to implement the same logic in our algorithm, our aim of making the algorithm running much faster, that is, reaching their destination much faster than before, will be fulfilled. Our target is not only heap sort, but some of the many algorithms where our aim of research and analysis can be fulfilled.
REFERENCES
[1] Knuth D.E The art of programming-sorting andsearching. 2nd edition AddisonWesley.
[2] Hoare C A R Quicksort. Computer journal 5(1):10~15.
[3] I.Wegner: BOTTOM-UP-HEAPSORT beating on averageQUICKSORT(if n is not very small). Proceedings of theMFCS90, LNCS 452,516-522, 1990
[4] S.Carlsson: Avariant of HEAPSORT with almost optimalnumber of comparisons. Information Processing Letters24:247-250, 1987.
[5] I.Wegner: The worst case complexity of Mc diarmid andReed's variant of BOTTOM-UP-HEAP SORT is less thannlogn+1.1n. Proceedings of the STACS91, LNCS 480:137-147, 1991.
[6] Xio dong wang,ying jie wu an improved heap sortalgorithm with nlogn –0.788928n comparisons in worstcase. Journal of computer science andtechnology22 (6):898~903
[7] S. Haldar: “Heapsort with n log(n+1) + n – 2log(n+1)-2 key comparisons using |_ n/2 _| additional bits”, Technical Report RUU-CS-93-14, April 1993.
[8] PankajSareen, “Comparison of Sorting Algorithms (On Basis of Average Case)”, IJARCSSE, Volume-3, Issue-3, March 2013.
[9] Cormen T., Leiserson C., Rivest R., and Stein C., Introduction to Algorithms, McGraw Hill, 2001.
[10] Vandana Sharma, Satwinder Singh and Dr. K. S. Kahlon, “Performance Study of Improved Heap Sort Algorithm and Other Sorting Algorithms on Different Platforms”, IJCSNS International Journal of Computer Science and Network Security, VOL.8 No.4, April 2008
Frequently asked questions
What is the main topic of this document?
This document compares the classical heap sort algorithm with a logically-modified heap sort algorithm, aiming to improve efficiency. The analysis includes performance comparisons and considerations for future improvements using Vedic Mathematics.
What is a heap, as defined in this context?
In the context of heap sort, a heap is a balanced, left-justified binary tree where every parent's value is larger than its children's values (max-heap). This definition is used within the heap sort algorithm.
What is the time complexity of the classical heap sort algorithm?
The heap sort algorithm has a time complexity of O(n log n) for both the worst case and average case scenarios, making it one of the faster sorting algorithms.
How does the classical heap sort work?
The classical heap sort involves building a max-heap or min-heap from the unsorted array. The largest (or smallest) element is extracted from the heap and placed in the sorted portion of the array. This process is repeated until all elements are sorted.
What is the heap property mentioned in the document?
The heap property states that in a max-heap, every node's value should be greater than or equal to the values of its children. If this property is violated, the node's value is exchanged with the larger child until the heap property is restored.
What is the key difference in the logically-modified heap sort algorithm?
The modified algorithm attempts to exchange two nodes simultaneously, potentially reducing the number of comparisons and iterations required compared to the classical heap sort.
What is the goal of using Vedic Mathematics in future improvements?
The future scope involves exploring Vedic Mathematics to potentially enhance the efficiency of the modified heap sort algorithm, with the goal of achieving faster execution speeds.
What does the performance analysis section show?
The performance analysis section presents a table comparing the average sorting times of the classical heap sort and the modified heap sort algorithms for different numbers of data items.
What is the conclusion of the comparison?
The implemented modified algorithm shows satisfactory results on the tested data. The results varied and can be seen in the table within the performance analysis section.
What future work is planned?
The authors intend to explore how Vedic Mathematics might make the algorithm more efficient. Their research and analysis won't be limited to just the heap sort algorithm.
- Quote paper
- Bhanu Prakash Lohani (Author), Pradeep K. Kushwaha (Author), Abhijeet Ashri (Author), Mohit Aggarwal (Author), Akhil V. Raj (Author), 2014, Performance Study of Logically-Modified Heap Sort Algorithm, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/284417
