First, we make sure the sorts actually work as expected and then we do some timing tests.
^^ Integer Data ^^
** Options Menu **
1 Single Sorting Tests
2 Statistical Tests
3 Create log file and log events
4 Exit
Option number: 1
-- Single Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 1
Insertion Sort
PRNG Seed 1
Number of Samples 20
Maximum Sample Value 20
11 -17
-16 -16
9 -14
-17 -12
-14 -7
17 0
10 0
0 3
7 6
3 7
8 7
0 8
-7 9
11 10
-12 11
13 11
7 12
12 13
16 16
6 17
-- Single Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 2
std::qsort
PRNG Seed 1
Number of Samples 20
Maximum Sample Value 20
11 -17
-16 -16
9 -14
-17 -12
-14 -7
17 0
10 0
0 3
7 6
3 7
8 7
0 8
-7 9
11 10
-12 11
13 11
7 12
12 13
16 16
6 17
-- Single Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 3
Singleton's FORTRAN Sort
PRNG Seed 1
Number of Samples 20
Maximum Sample Value 20
11 -17
-16 -16
9 -14
-17 -12
-14 -7
17 0
10 0
0 3
7 6
3 7
8 7
0 8
-7 9
11 10
-12 11
13 11
7 12
12 13
16 16
6 17
-- Single Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number:
^^ Integer Data ^^
** Options Menu **
1 Single Sorting Tests
2 Statistical Tests
3 Create log file and log events
4 Exit
Option number: 2
-- Statistical Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 1
Insertion Sort
PRNG Seed 1
Number of Samples 1000
Maximum Sample Value 1000
Number of Experiments 100
Runtimes in microseconds
Minimum runtime 524
Maximum runtime 1751
Mean runtime 802
Median runtime 668
-- Statistical Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 2
std::qsort
PRNG Seed 1
Number of Samples 1000
Maximum Sample Value 1000
Number of Experiments 100
Runtimes in microseconds
Minimum runtime 115
Maximum runtime 1751
Mean runtime 481
Median runtime 391
-- Statistical Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 3
Singleton's FORTRAN Sort
PRNG Seed 1
Number of Samples 1000
Maximum Sample Value 1000
Number of Experiments 100
Runtimes in microseconds
Minimum runtime 93
Maximum runtime 1751
Mean runtime 363
Median runtime 174
-- Statistical Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number:
; Copilot and James Pate Williams, Jr.
; 2/8/2025 - 2/9/2025
; We use the eax register for array indices
; The array base in register ecx
; The register ebx is general purpose;
;
;class SortingCPP {
;public:
; static void InsertionSort(std::vector<T>& a)
; {
; for (size_t j = 1; j < a.size(); j++)
; {
; T key = a[j];
; int i = j - 1;
;
; while (i >= 0 && a[i] > key)
; {
; a[i + 1] = a[i];
; i--;
; }
;
; a[i + 1] = key;
; }
; };
.MODEL FLAT, C
.STACK 4096
.DATA
; Allocate space for uninitialized variables
i DWORD ?
j DWORD ?
key DWORD ?
n DWORD ?
t DwORD ?
.CODE
InsertionSortASM PROC
; Parameters:
; array = [esp + 8]
; n = [esp + 12]
push ebp
mov ebp, esp
sub esp, 16 ; Allocate space for local variables
mov ecx, [ebp + 8] ; base of array
mov eax, [ebp + 12] ; n number of array elements
mov [n], eax ; store n
; Initialize variables
mov dword ptr [i], 0 ; i = 0
mov dword ptr [j], 1 ; j = 1
for_loop:
mov eax, [j] ; load j into register
mov ebx, [n] ; load n
cmp eax, ebx ; compare j to n
je Exit ; we are done
mov ebx, [ecx + eax * 4] ; ebx = a[j]
mov [key], ebx ; key = a[j]
dec eax ; j = j - 1
mov [i], eax; ; i = j - 1
inc eax ; increment
inc eax ; j = j + 1
mov [j], eax ; store j
while_loop:
mov eax, [i] ; load i into register
cmp eax, -1 ; is i == -1 ?
jz end_while ; end the while loop
mov ebx, [ecx + eax * 4] ; load a[i]
mov eax, [key] ; load key into register
cmp ebx, eax ; compare a[i] to key
jle end_while ; end the while loop
mov eax, [i] ; load i
mov ebx, [ecx + eax * 4] ; load a[i]
inc eax ; eax = i + 1
mov edx, [ecx + eax * 4] ; load a[i + 1]
;mov [t], ebx ; t = a[i]
mov edx, ebx ; edx = a[i]
mov eax, [i] ; load i again
inc eax ; i + 1
mov [ecx + eax * 4], edx ; a[i + 1] = a[i]
dec eax ; i--
dec eax ; i--
mov [i], eax ; store updated i
jmp while_loop ; continue while
end_while:
mov eax, [i] ; load i
inc eax ; eax = i + 1
mov ebx, [key] ; ebx = key
mov [ecx + eax * 4], ebx ; a[i + 1] = key
jmp for_loop ; continue for loop
Exit:
mov esp, ebp
pop ebp
ret
InsertionSortASM ENDP
END
Numerical Explorations 