1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
\documentclass{article}
\usepackage{geometry}
\usepackage{hyperref}
\usepackage{pgfplots}
\usepackage{tikz}
\usepackage{minted}
\usepackage{booktabs}
\usepackage{siunitx}
\usepackage{algorithm2e}
\geometry{a4paper}
\begin{document}
\begin{center}
\Huge
Sorting in x86\_64 linux Assembly
\vspace{1cm}
\Large
Navid S.
\vspace{0.5cm}
Andreas K. L.
\vspace{0.5cm}
Mikkel T.
\vspace{1cm}
\large
October 20$^\text{th}$ 2025
\end{center}
\newpage
\tableofcontents
\newpage
\section{Introduction}
Sorting is one of the most fundamental operations in programming. Sorting algorithms play a crucial role
in efficient searching, organization and interpretation of data, and optimization problems. Furthermore,
sorting is often times the first step towards designing complicated algorithms in computer science. This
project aims to study efficient sorting of a list of coordinates by the second value of each coordinate,
in Assembly. Although abstract high level languages such as Python and Java allow faster and convenient development,
Assembly provides precise control over program flow, memory usage and instruction level execution, making Assembly an excellent
evironment for benchmarking and performance analysis. In this project the two algorithms quick-sort and insertion-sort
will be implemented and compared against each other. Quick-sort is expected to excel on large random datasets,
while insertion-sort is more suitable for small or nearly sorted cases.
Several test
instances consisting of uniformly random coordinates will be created with the goal of comparing the implementations
actual runtime to their theoretical runtimes. These datasets will be ranging from 10,000 to 5,000,000 elements, including edge
cases with duplicates or nearly sorted lists.
\section{Design}
\section{Implementation}
\section{Evaluation}
\begin{tikzpicture}
\begin{axis}[xlabel={size},ylabel={seconds}]
\addplot[only marks] table [x=size, y=real, col sep=comma]
{../benchmark_results.csv};
\end{axis}
\end{tikzpicture}
\section{Conclusion}
\end{document}
|