Category: Computer Science

Who Knew? Better Code for Selection Sort

I have been using inferior code for the Selection Sort since 1979. Last night I found the more efficient pseudo code:

Data Structure and Algorithms Selection Sort – Tutorialspoint

Here is my old code for the Selection Sort in C#:

Old Code for the Algorithm

And my new code from the more efficient pseudo code found online:

New and Better Code
Common Swap Function (Procedure)

Both implementations require n * (n – 1) / 2 comparisons which for an array of length 15 is 15 * 14 /2 = 15 * 7 = 105. The second implementation requires typically fewer calls to the swap function.

Selection Sort Test 15-Element Random Array
Selection Sort Test 15-Element Reverse Ordered Array
Selection Sort Test 15-Element Sorted Array

The first number after the unsorted array is the number of comparisons which is always 105 in our 15-element test cases. The second number is the tally of the swap function calls.

Anagrams and Their Computer Solution by James Pate Williams, Jr., BA, BS, MSwE, PhD

An anagram is also known as a word jumble. You take a word and apply a permutation to the word to get an alphabetic jumble of the word. A permutation of three distinct characters is based on three index permutation table:

123 132 213 231 312 321.

So, the scrambling of the word “THE” is as follows:

THE TEH HTE HET ETH EHT.

As you can see there are n-factorial permutations of n objects.

0! = 1

1! = 1

2! = 2 * 1 = 2

3! = 3 * 2 * 1 = 6

4! = 4 * 3 * 2 * 1 = 4 * 3! = 24

Etc. Several years ago I created a program to solve single word anagrams of length less than or equal about a dozen.

12! = 479,001,600

This is about the limit of finding all the permutations of up to length twelve on a desktop computer. The algorithm is extremely easy to understand and implement. First find a suitable list of English words and if the list is unsorted then sort the list alphabetically in ascending order. Hash the dictionary words using a hash table of length 128 * 128 + 128 = 16,512 elements. The dictionary I used has 152,512 words so there are hash table collisions. The hash value is computed using the first three characters of the word in ASCII (7-bit) encoding. Then for each permutation of the anagram a hash value is computed and if the current permutation is found in the hash table the word associated with the hash table entry is returned and the algorithm is finished.

Singleton’s Sorting Algorithm 1979 and 2018 by James Pate Williams, Jr., BS, BS, MSwE, PhD

I first implemented Singleton’s sorting algorithm in the Summer of 1979. The programming language was Data General’s version of Dayton BASIC (Beginner’s All-purpose Symbolic Instruction Code). This variant of BASIC was interpretive like C#, Java, and Pascal. Below is my BASIC version and run-times for double precision numbers in an inverted sequence.

Summer of 1979 BASIC Singleton’s Sorting Algorithm

Zoom forward to my current computer and C# programming language in 2018.

C# Singleton’s Sorting Algorithm 2008 – 2018 Random Lists of Double Precision Numbers

Baseball Ballistics by James Pate Williams, Jr., BS, BS, MSwE, PhD

There are analytic equations that are applicable to the trajectory of a batted or thrown baseball:

Click to access 04-LAJPE-782_Chudinov.pdf

I created a C# application to test the preceding equations against numerical methods of calculating the trajectory of a baseball. The baseball has an initial velocity of 90 miles per hour and an angle of inclination of 20 degrees. The classical model certainly overestimates the trajectory.

Powers of Two – Excel by James Pate Williams, Jr. BA, BS, MSwE, PhD

First Function in Excel (Assumes that You Have Access to an Office 365 Subscription)

Please attempt the following procedure:

  1. Type Excel in the Windows 10 Search Box
  2. Select the Excel App
  3. Select Blank workbook
  4. Maximize the Excel Window
  5. Type x in Cell A1
  6. Tab to Cell B1
  7. Type y in Cell B1
  8. Type 0 in Cell A2
  9. Type 1 in Cell B2
  10. Type 1 in Cell A3
  11. Type 2 in Cell B3
  12. Type 2 in Cell A4
  13. Type 4 in Cell B4
  14. Type 3 in Cell A5
  15. Type 8 in Cell B5
  16. Type 4 in Cell A6
  17. Type 16 in Cell B6
  18. Type 5 in Cell A7
  19. Type 32 in Cell A8
  20. Highlight Cells A1 and B1
  21. From the Toolbar Select Alignment and Right Alignment
  22. Select File Save As
  23. Select “Documents” and “Powers of Two” as the filename
  24. Highlight Cells A1 to B7
  25. Select Insert from Toolbar
  26. Select Charts Scatter
  27. Select the Chart
  28. Select the Big + Sign on the Right
  29. Label the y-axis “y = 2 ^ n”
  30. Label the x-axis “n”
  31. Relabel the Title of the Chart as “Powers of Two”

Note that x is in the finite set { 0, 1, 2, 3, 4, 5 }

Note that y is the function y = 2 ^ x where ^ is the exponentiation operator

Powers of Two TablePowers of Two Chart

A Simple and Utilitarian C# Matrix Class by James Pate Williams, BA, BS, MSwE, PhD

We designed and implemented a simple and utilitarian C# matrix class for double precision numbers. The class has the binary matrix operators +, -, *, / which are addition, subtraction, multiplication, and division of two matrices. We also include an operator for multiplication of matrix by a scalar and an operator for dividing a matrix by a scalar. We have included functions to compute the p-norm, p, q-norm, and max norm of a matrix. We also can calculate using truncated infinite series the exponential, cosine, and sine function of a matrix. The exponential and trigonometric functions use a powering function that raises a matrix to a non-negative integral power.

Below is a screenshot of the test Windows Forms application. We execute the four binary matrix operators in the order +, -, *, / e.g. A+B, A-B, A*B, A/B. In order to divide by B, the matrix B must be square and non-singular, that is square and invertible.

Matrix Example Application Screenshot

The B matrix has the form of the matrix in the online discussion:

http://www.purplemath.com/modules/mtrxinvr2.htm

We create a project named MatrixExample. In this project we add a Matrix class whose code is given below:

Matrix

I leave it as an exercise for the reader to test the various norms and other functions.