This new post, is going to be the first in a series of posts in which the problem raised will be resolved. The problem will be raised in order to solve it using 6 different algorithms, of which 5, are sorting algorithms and one will be a direct method of obtaining the result.
Given a T vector, which contains n positive integers (n <10^6), and an integer m > 0, we want an algorithm that prints the m numbers less than T. We know that m is much smaller than n. We want an experimental analysis and analytic study of different solutions to this problem. Solutions should be considered in both ways, ordering the data set and direct resolution using those algorithms: SelectionSort, Insertion Sort, Merge Sort, quicksort, heap, select (k-element).
To proceed with the resolution of this problem, I will be creating a series of posts, 1 per algorithm, 6 in total. With the explanation of the algorithm and its own implementation. At the end of each post we will proceed to make an analytical study of it.
Each Post always will be structured as follows.
- Introduction: A brief presentation of the algorithm to be explained .
- Explication: Understanding the algorithm using text and images.
- Implementation: Development of the algorithm according to the structure explained in the previous section. Code will be programmed in Java.
- Analysis: At the end, a mathematical analysis of the efficiency of the algorithm.
The algorithms to solve this problem are:
- Insertion Sort.
- Heap (Binary heap).
- Select (k-element).
After the completion all the algorithms, I will post a summary of all the results of all 6 algorithms.
Greetings! For any questions, leave them in comments. See you in the next post!
Problem extracted from the subject of design algorithms (DA) of the University of the Basque Country. EHU / UPV. School of Computing.