diff options
| -rw-r--r-- | report/report.tex | 21 |
1 files changed, 20 insertions, 1 deletions
diff --git a/report/report.tex b/report/report.tex index d8670e2..5eeddee 100644 --- a/report/report.tex +++ b/report/report.tex @@ -347,5 +347,24 @@ is efficient sorting, correct usage of registers, memory and syscalls will great affect and boost performance. \section{Conclusion} - +In this project insertionsort and quicksort have been implemented in assembly x86 64 +with the goal of studying efficient sorting. Although the algorithms perform the same task, + they are in fact very different. Firstly, from the benchmarks we have learned that the +algorithms are heavily affected by the dataset itself. Both algorithms have very +different run times on the sorted, reversed, and random datasets, despite the sets +having the same size. As discussed, earlier insertionsort and quicksort have roughly +the same performance on reversed datasets, insertionsort is optimal on sorted or +small datasets, and quicksort excels on random and very large datasets. So one +could say that efficient sorting requires an efficient algorithm well suited for +the dataset. But it should also be mentioned that in most general cases with +random output quicksort will most likely outperform insertionsort. Furthermore, +from the testings we have learned that the stable tests used on insertion sort +cannot be used on quicksort, since quicksort doesn’t preserve the order the inputs. +This means that the algorithms might produce different results even if used +on the same dataset. Another important observation has been that although the algorithms +themselves determine the asymptotic run times, the concrete implementations also matter +for the total run times. Which means that memory usage, registers, stack management, and +syscalls should also be considered while trying to create a fast sorting algorithm. Summing +all these observations up in one sentence, we can conclude that a recipe to efficient sorting +is choosing a well suited algorithm supported by a smart implementation. \end{document} |