Results for Combsort Combsort is just a single, easy line more than bubble sort, but performs spectacularly in fact, almost as well as the grotesquely more complex quicksort. Results for Quicksort Quicksort is of high complexity and owes its performance on sorted data to the built-in insertion-sort.
On already sorted data it slows down a trifle. Results for Heapsort Heapsort is of medium complexity and does a very good job. As the number of data elements grows, bubble sort slows to a crawl and becomes useless. Results for Bubble Sort Bubble sort is very fast on already sorted data, but very slow on random data. After the tables had been sorted, they were sorted again to measure the time for sorting already sorted data. The test program was run on a PC (16 MHz 386SX) and on an AS/400 (B35). The times below are measured in 1/1000ths of a second and are the averages of sorting four different random sequences. Comparison of Table Sorting MethodsThe above implementations of bubble sort, heapsort, quicksort, and combsort were tested on from 200 to 1600 items, each consisting of a 9-character key and 11 characters of data. It is clearly correct, as it (unless the table is empty) ends with JUMP-SIZE = 1 (ensured by the `+3') and therefore degenerates into bubble sort: The careful termination test (JUMP-SIZE NOT > 1) also caters for the case where the table is empty. Here is then the magic code (re-using declarations and a code paragraph from bubble sort). Quicksort performs badly with certain types of data this can be improved by judicious choice of a pivot point at each sort, f.This can be avoided by using a secondary sort when the partition size is less than some magic figure. Quicksort performs badly once the amounts of data become small due to the overhead of recursion.You can add stability to the sort by extending the key to include a sequence number, so that there are in fact no duplicate keys. Bubble sort is, in contrast, stable (its one good feature). This means that two records with the same key may not end up in the same order after sorting. This is easiest to implement in a language such as Pascal or C, but quite possible in COBOL, as we shall see. There are some notable aspects of quicksort that you should be aware of, even if the detailed mechanism is not important:
If you ever need to sort significant amounts of data, use this method. QuicksortSorting is a problem which has been solved. Additionally, heapsort is quite compact compared to the quicksort algorithm presented later: 3. The advantage of heapsort over bubble sort is simply that it is a lot faster for large amounts of data 2n(log2n) comparisons are needed on average.
0 kommentar(er)
