Numerical Explorations

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