Category: Memoirs of James Pate Williams Jr
Blog Entry (c) Tuesday, June 3, 2025, Sorting Algorithms by James Pate Williams, Jr.
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
Blog Entry (c) Sunday, June 1, 2025, MIDI Guitar Experiment 06 01 2025, “The Bars Have It”
Blog Entry © Saturday, May 31, 2025, Air Density and Ballistic Density Computations by James Pate Williams, Jr.
Online references: https://www.grc.nasa.gov/WWW/K-12/airplane/atmosmet.html and https://www.nist.gov/system/files/documents/calibrations/metv29i1p67-2.pdf
Density Published Density
1.183473 1.183472
1.306584 1.306582
1.202410 1.202408
0.694163 0.694162
Exercises from Exterior ballistics, 1935
By Lieutenant Commander Ernest Edward Herrmann
Percentage Differences Exercise 1 Page 41
Percentage Difference [1] = 0.294283%
Percentage Difference [2] = 0.026383%
Percentage Difference [3] = 0.094477%
Percentage Difference [4] = 0.050340%
Percentage Difference [5] = 0.026880%
Percentage Difference [6] = 0.008545%
Percentage Difference [7] = 0.001676%
Percentage Difference [8] = 0.008220%
Three Altitude Related Density Calculations
Rho1 is from Exterior ballistics, 1935
Rho2 is from NASA
Rho3 is from Wikipedia
h ft Rho1 SI Rho2 SI Rho3
0 1.000000 1.226614 1.208993
1000 0.968902 1.215727 1.174010
2000 0.938772 1.204914 1.139806
3000 0.909578 1.194175 1.106369
4000 0.881292 1.183510 1.073689
5000 0.853886 1.172917 1.041752
6000 0.827332 1.162397 1.010547
7000 0.801604 1.151949 0.980062
8000 0.776676 1.141574 0.950286
Three Altitude Related Ballistic Density Calculations
Rho1 is from Exterior ballistics, 1935
Rho2 is from NASA Rho3 is from Wikipedia
STP = Temperature = 59 F Pressure = 29.53 Humidity = 78%
Temp Press h ft Rho1 SI Rho2 SI Rho3
65 29.60 1000 0.968902 1.203134 1.161848
85 29.75 18000 0.566291 0.992155 0.656245
57 30.25 8000 0.776676 1.174418 0.977626
69 29.80 13000 0.663193 1.077573 0.801819
32 30.15 15000 0.622587 1.157366 0.822138
Test Case from Exterior ballistics, 1935
Temperature 84 F Pressure 29.90 In Hg
Density SI = 0.959428 Book Density = 0.960
Altitude 18,000 Feet
Density SI = 0.999439 Book Density = 0.991
Blog Entry © Friday, May 30, 2025, Ballistic Coefficient Exercises from Exterior ballistics, 1935 Written by Ernest Edward Herrmann, C/C++ Code by James Pate Williams, Jr., BA, BS, Master of Software Engineering, PhD Computer Science
#include <iomanip>
#include <iostream>
double BookAnswers[] = {
0.15710, 0.49268, 0.51734, 0.67524,
0.84437, 1.01811, 1.01401, 1.09482 };
double MyAnswers[] = {
0.157563, 0.492810, 0.517829, 0.675580,
0.844597, 1.018197, 1.014027, 1.094910 };
double PD[8];
int main()
{
std::cout << "Percentage Differences" << std::endl;
std::cout << std::fixed << std::setprecision(6);
for (int i = 0; i < 8; i++)
{
PD[i] = 100.0 * fabs(BookAnswers[i] - MyAnswers[i]) /
(0.5 * (BookAnswers[i] + MyAnswers[i]));
std::cout << "Percentage Difference [" << i + 1 << "] = ";
std::cout << PD[i] << '%' << std::endl;
}
}
Blog Entry © Wednesday, May 28, 2025, More C/C++ Siacci Method Ballistic Screenshots by James Pate Williams, Jr., BA, BS, MSWE, PhD
Blog Entry © Tuesday, May 27, 2025, Translation of a Siacci’s Method C# App to C/C++ by James Pate Williams, Jr., BA, BS, MSWE, PhD
Universal Audio Poly MAX Synth Instrumental Experiment May 25, 2025 (c) James Pate Williams, Jr.
Blog Entry © Saturday, May 25, 2025, Return to Baseball Ballistics by James Pate Williams, Jr. BA, BS, Master of Software Engineering, PhD Computer Science Return to Baseball Ballistics
Blog Entry © Friday, May 23, 2025, NASA Geopotential Altitude and the Variation of the Gravitational Acceleration by James Pate Williams, Jr., BA, BS, Master of Software Engineering, PhD Computer Science
More source code is available upon request.
Reference: 19770009539.pdf
Win32 C/C++ application output to a Win32 window:
H Z1 Z2 Z3 g
80000 79005.7 79005.7 79005.7 9.56735
80500 79493.3 79493.3 79493.3 9.56590
81000 79980.9 79980.9 79980.9 9.56446
81500 80468.3 80468.3 80468.3 9.56301
82000 80955.7 80955.7 80955.7 9.56156
82500 81443.0 81443.0 81443.0 9.56011
83000 81930.2 81930.2 81930.2 9.55867
83500 82417.4 82417.4 82417.4 9.55722
84000 82904.5 82904.5 82904.5 9.55577
84500 83391.5 83391.5 83391.5 9.55433
85000 83878.4 83878.4 83878.4 9.55288
85500 84365.3 84365.3 84365.3 9.55144
H Geopotential Altitude
Z1 Geopotential Gauss-Legendre 128 Steps
Z2 Geopotential Simpson's Rule 256 Steps
Z3 Geopotential Trapezoidal Rule 512 Steps
g gravitational acceleration in m/s/s
https://ntrs.nasa.gov/api/citations/19770009539/downloads/19770009539.pdf
See Table 8. Page 9
// NASAGeopotentialAltitude.cpp : Defines the entry point for the application.
// Copyright (c) Friday, May 23, 2025 by James Pate Williams, Jr.
// BA, BS, MSWE, PhD All Applicable Rights Reserved
#include "stdafx.h"
#include "GeopotentialAltitude.h"
#include "Integration1d.h"
#include "NASAGeopotentialAltitude.h"
#include <math.h>
#include <stdio.h>
#include <tchar.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAX_LOADSTRING 100
// Global Variables:
HINSTANCE hInst; // current instance
TCHAR szTitle[MAX_LOADSTRING]; // The title bar text
TCHAR szWindowClass[MAX_LOADSTRING]; // the main window class name
// Forward declarations of functions included in this code module:
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK About(HWND, UINT, WPARAM, LPARAM);
int APIENTRY _tWinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPTSTR lpCmdLine,
int nCmdShow)
{
UNREFERENCED_PARAMETER(hPrevInstance);
UNREFERENCED_PARAMETER(lpCmdLine);
// TODO: Place code here.
MSG msg;
HACCEL hAccelTable;
// Initialize global strings
LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
LoadString(hInstance, IDC_NASAGEOPOTENTIALALTITUDE, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);
// Perform application initialization:
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_NASAGEOPOTENTIALALTITUDE));
// Main message loop:
while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
return (int) msg.wParam;
}
//
// FUNCTION: MyRegisterClass()
//
// PURPOSE: Registers the window class.
//
// COMMENTS:
//
// This function and its usage are only necessary if you want this code
// to be compatible with Win32 systems prior to the 'RegisterClassEx'
// function that was added to Windows 95. It is important to call this function
// so that the application will get 'well formed' small icons associated
// with it.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_NASAGEOPOTENTIALALTITUDE));
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = MAKEINTRESOURCE(IDC_NASAGEOPOTENTIALALTITUDE);
wcex.lpszClassName = szWindowClass;
wcex.hIconSm = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));
return RegisterClassEx(&wcex);
}
//
// FUNCTION: InitInstance(HINSTANCE, int)
//
// PURPOSE: Saves instance handle and creates main window
//
// COMMENTS:
//
// In this function, we save the instance handle in a global variable and
// create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HWND hWnd;
hInst = hInstance; // Store instance handle in our global variable
hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
if (!hWnd)
{
return FALSE;
}
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
return TRUE;
}
//
// FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
// PURPOSE: Processes messages for the main window.
//
// WM_CREATE - creates a multiple line edit control
// WM_COMMAND - process the application menu
// WM_PAINT - Paint the main window
// WM_DESTROY - post a quit message and return
//
//
#define ID_EDITCHILD 100
char asciiData[16384];
char asciiLine[16384];
TCHAR textData[16384];
void ConvertCharToTChar(const char* charArray, TCHAR* tcharArray, size_t tcharSize) {
#ifdef _UNICODE
MultiByteToWideChar(CP_ACP, 0, charArray, -1, tcharArray, (int)tcharSize);
#else
strncpy(tcharArray, charArray, tcharSize - 1);
tcharArray[tcharSize - 1] = '\0'; // Ensure null-termination
#endif
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;
PAINTSTRUCT ps;
HDC hdc;
static HWND hwndEdit;
static double zArray[] = {
80000, 80500, 81000, 81500, 82000, 82500,
83000, 83500, 84000, 84500, 85000, 85500 };
static vector<double> z(12);
static vector<double> potential1(12);
static vector<double> potential2(12);
static vector<double> potential3(12);
static vector<double> potential4(12);
size_t numberPoints = z.size();
for (size_t i = 0; i < z.size(); i++)
{
z[i] = zArray[i];
}
switch (message)
{
case WM_CREATE:
GeopotentialAltitude::GaussianLegendre(
numberPoints, z, potential1);
GeopotentialAltitude::SimpsonsRule(
numberPoints, z, potential2);
GeopotentialAltitude::TrapezoidalRule(
numberPoints, z, potential3);
strcpy_s(asciiData, 16384, "H\tZ1\tZ2\tZ3\tg\r\n");
for (size_t i = 0; i < z.size(); i++)
{
double zi = z[i];
double p1 = potential1[i];
double p2 = potential2[i];
double p3 = potential3[i];
double g = g0 * pow(r0 / (r0 + p1), 2.0);
sprintf_s(
asciiLine, 16384,
"%5.0lf\t%5.1lf\t%5.1lf\t%5.1lf\t%7.5lf\r\n",
zi, p1, p2, p3, g);
strcat_s(asciiData, 16384, asciiLine);
}
strcat_s(asciiData, "H Geopotential Altitude\r\n");
strcat_s(asciiData, "Z1 Geopotential Gauss-Legendre 128 Steps\r\n");
strcat_s(asciiData, "Z2 Geopotential Simpson's Rule 256 Steps\r\n");
strcat_s(asciiData, "Z3 Geopotential Trapezoidal Rule 512 Steps\r\n");
strcat_s(asciiData, "g gravitational acceleration in m/s/s\r\n");
strcat_s(asciiData, "https://ntrs.nasa.gov/api/citations/19770009539/downloads/19770009539.pdf\r\n");
strcat_s(asciiData, "See Table 8. Page 9\r\n");
ConvertCharToTChar(asciiData, textData, sizeof(textData));
// https://learn.microsoft.com/en-us/windows/win32/controls/use-a-multiline-edit-control
hwndEdit = CreateWindowEx(
0, L"EDIT", // predefined class
NULL, // no window title
WS_CHILD | WS_VISIBLE | WS_VSCROLL |
ES_LEFT | ES_MULTILINE | ES_AUTOVSCROLL,
0, 0, 0, 0, // set size in WM_SIZE message
hWnd, // parent window
(HMENU) ID_EDITCHILD, // edit control ID
hInst,
/*(HINSTANCE) GetWindowLongPtr(hWnd, GWLP_HINSTANCE),*/
NULL); // pointer not needed
// Add text to the window.
SendMessage(hwndEdit, WM_SETTEXT, 0, (LPARAM) textData);
return 0;
case WM_COMMAND:
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
// Parse the menu selections:
switch (wmId)
{
case IDM_ABOUT:
DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
break;
case IDM_EXIT:
DestroyWindow(hWnd);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
break;
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
// TODO: Add any drawing code here...
EndPaint(hWnd, &ps);
break;
case WM_SIZE:
// Make the edit control the size of the window's client area.
MoveWindow(hwndEdit,
0, 0, // starting x- and y-coordinates
LOWORD(lParam), // width of client area
HIWORD(lParam), // height of client area
TRUE); // repaint window
return 0;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
// Message handler for about box.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
UNREFERENCED_PARAMETER(lParam);
switch (message)
{
case WM_INITDIALOG:
return (INT_PTR)TRUE;
case WM_COMMAND:
if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return (INT_PTR)TRUE;
}
break;
}
return (INT_PTR)FALSE;
}