Category: Source code

Quicksort in C

Quicksort in C

Sorting
Image by Clker-Free-Vector-Images from Pixabay

Normally I wouldn’t mention a sorting algorithm, but by a lucky coincidence, when I had my interview before going to university (Queen’s University Belfast), the bloke who interviewed me back in 1977 was the inventor of Quicksort. Tony Hoare. He left very shortly after so I never got him as a lecturer,

As algorithms go, Quicksort is one of the faster. it works by splitting the list in two and then recursively sorting the two halves. The simplest sorting method Bubble sort uses a double loop and for very small numbers of items to sort is generally more efficient than Quicksort, but it doesn’t take long for Quicksort to catch up.

I was reminded of Quicksort by seeing this article and thought it would be interesting to do a series of test of sorting 5-50 items a few thousand times each in Quicksort and Bubblesort and see where the crossover point is. How many items is the minimum for Quicksort to become faster than Bubble sort?

If you take the Swap functions and BubbleSort from here and partition and quickSort functions from here and use my high precision timing code and add the code below then you can run the comparison. I did it twice, once in Debug and once in Release and the difference is much larger in release. I’ve zipped up the source code including the Visual C++ project code (It is C source code not C++ btw) and high performance timing code and put it on GitHub.

#define NUMLOOPS 5000

int main()
{
    int startarr[]= { 86,91,50,5,79,64,2,57,26,63,12,61,12,92,40,38,11,
                 94,90,38,24,25,54,75,67,56,7,9,32,26,54,48,51,28,
                90,50,37,53,8,75,30,25,59,57,92,42,25,33,84,46 };
    int arr[50];
    stopWatch stw;
    double bTime, qTime;

    bTime = 0.0;
    qTime = 0.0;
    for (int i = 3; i < 50; i++) {
        printf("Bubble sort for %d = ", i);
        for (int j = 1; j < NUMLOOPS; j++) {
            memset(arr, 0, sizeof(arr));                     // Clear arr
            memcpy(arr, startarr, sizeof(int) * i); // copy in i elements
            startTimer(&stw);
            bubbleSort(arr, i);
            stopTimer(&stw);
            bTime += getElapsedTime(&stw);
        }
        bTime /= NUMLOOPS;
        printf("%12.10f.  ", bTime);
        printf("Quicksort sort for %d = ", i);
        for (int j = 1; j < NUMLOOPS; j++) {
            memcpy(arr, startarr, sizeof(int) * i); // copy in i elements
            startTimer(&stw);
            quickSort(arr, 0, i - 1);
            stopTimer(&stw);
            qTime += getElapsedTime(&stw);
        }
        qTime /= NUMLOOPS;
        printf("%12.10f\n", qTime);
    }
    return 0;
}

These are the first 15 and last 5 output lines in Release. The Bubble sort time for 7 is a bit of an oddity just for the actual numbers sorted. But its clear that by 11 values that Bubble sort is slower than QuickSort and the difference just gets worse up to 50. So up to 10 elements, Bubble Sort wins.

Bubble sort for 3 = 0.0000000358.  Quicksort sort for 3 = 0.0000000412
Bubble sort for 4 = 0.0000000407.  Quicksort sort for 4 = 0.0000000445
Bubble sort for 5 = 0.0000000474.  Quicksort sort for 5 = 0.0000000485
Bubble sort for 6 = 0.0000000677.  Quicksort sort for 6 = 0.0000000448
Bubble sort for 7 = 0.0000000191.  Quicksort sort for 7 = 0.0000000097
Bubble sort for 8 = 0.0000000405.  Quicksort sort for 8 = 0.0000000601
Bubble sort for 9 = 0.0000000510.  Quicksort sort for 9 = 0.0000000434
Bubble sort for 10 = 0.0000000568.  Quicksort sort for 10 = 0.0000000653
Bubble sort for 11 = 0.0000000633.  Quicksort sort for 11 = 0.0000000566
Bubble sort for 12 = 0.0000000702.  Quicksort sort for 12 = 0.0000000606
Bubble sort for 13 = 0.0000000845.  Quicksort sort for 13 = 0.0000000743
Bubble sort for 14 = 0.0000000931.  Quicksort sort for 14 = 0.0000001145
Bubble sort for 15 = 0.0000001040.  Quicksort sort for 15 = 0.0000000827
Bubble sort for 16 = 0.0000001142.  Quicksort sort for 16 = 0.0000000892
Bubble sort for 17 = 0.0000001448.  Quicksort sort for 17 = 0.0000000974
...
Bubble sort for 45 = 0.0000008478.  Quicksort sort for 45 = 0.0000002737
Bubble sort for 46 = 0.0000008561.  Quicksort sort for 46 = 0.0000002524
Bubble sort for 47 = 0.0000008948.  Quicksort sort for 47 = 0.0000002643
Bubble sort for 48 = 0.0000009421.  Quicksort sort for 48 = 0.0000003147
Bubble sort for 49 = 0.0000010042.  Quicksort sort for 49 = 0.0000002804

 

 

Can you compile this?

Can you compile this?

No return
Image by PublicDomainPictures from Pixabay

It’s just a little bit of C. I compiled it with these three compilers. MS VC (16.7.7 on Windows) gcc, and clang on Ubuntu 20.04 LTS. MS VC picked up the _Noreturn and complained, gcc 9.33 compiled it with not a whisper while clang 10.0.0 warned about void in the main function but compiled it anyway.

Both the clang and gcc compiled files ran and as you’d expect sat in an infinite loop until I control-c’d it.

However soon MS VC will compile it. According to this blog entry, MSVC from 16.8 preview 3 supports C11 and the _Noreturn feature (which tells the compiler that the function never returns) will be ok. Both gcc and clang support C11 so no problems.

#include <stdio.h>

_Noreturn void nrloop() {
	while (1) {
		;
	}
}

void main() {
	nrloop();
}

 

When would I use such a function, you might ask. IO can’t see me using it much unless I wnt to write a background thread function that just runs forever. I have indeed written such a function recently but it was in Delphi not C. Another use is a function that exits perhaps vi a jmp. It also lets the compiler know so it can optimize return code away.

As I said, I don’t think I’ll be using it much if at all.

So what do you think this code does?

So what do you think this code does?

Math(s) symbols
Image by Chuk Yong from Pixabay

Here’s a little C function. It’s not exactly intuitive what it does and I’ve renamed it to prevent giving it away.

  float mystery( float number )
  {
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       
    i  = 0x5f3759df - ( i >> 1 );               
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   
    return y;
  }

If it helps, this line is really the heart of it.

    i  = 0x5f3759df - ( i >> 1 );  

Mystified? Well it’s a fast inverse square root. No one really knows who wrote it though John Carnack of Quake and Doom fame popularised it. There’s an interesting discussion about the author but no one really knows.

There’s less need for this type of thing nowadays because of all the fast silicon but back 20-25 years ago when graphics processors were in their very infancy, it was a highly useful optimization. Mind you , you’d need to know assembly language inside out to come up with stuff like this.

More on Shuffledness

More on Shuffledness

DEck of playing cards
Dowload from Creazilla.com

So I’ve updated my shuffledness calculation. This is a bit of a work in progress so probably isn’t the last version.  One of the things I’m interested in is what is the optimal number of swaps to get a good shuffled deck of cards. The shuffle algorithm picks two random indexes in the array 0-51 and then swaps the contents.

Obviously doing this 10 times would only shuffle at most 20 cards and probably fewer as there’s no checks for repeats. The only check is that both indexes (indices?) are not the same. So I want to experiment and see what an optimal value for numTries should be..

void ShuffleDeck(int numtries) {
	int firstIndex, secondIndex;
	for (int i = 0; i < numtries; i++) {
		do {
			firstIndex = rand() % 52;
			secondIndex = rand() % 52;
		}
		while (firstIndex == secondIndex);
		int value = deck[firstIndex];
		deck[firstIndex] = deck[secondIndex];
		deck[secondIndex] = value;
	}
}

Anyway, I’ve added a CalcDistance() function. This looks at each card and calculates how far it has moved from it’s original position.  It then divides this by the maximum distance it could have moved to get a move “factor”. These are summed up and divided by 52 to give an average move factor. That’s your CalcDistance() function.

float CalcDistance() {
	float distance = 0.0f;
	for (int i = 0; i < 52; i++) {
		float distanceDiv = (i < 26) ? 51 - i : i-1;
		//printf("%i: %3.0f\n", i, distanceDiv);
		distance += (abs(deck[i] - i) / distanceDiv);
	}
	return distance/52.0f;
}

The only thing odd about this function is the distanceDiv value which starts at 51, decreases to 25 then increases to 50. The printf let me check that was correct.

This is the current state of the program which I’ve listed fully below. Enjoy! It’s 63 lines long.

// shuffledness.c : This measures how shuffled a deck of cards is
// cards are hjeld as values 0-51 in a 52 int aaray.

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int deck[52];
time_t t;

// Order the cards 0-51. 0 = Acew Hards,13 = Ace Clubs,26 = Ace of Diamonds and 51 = King of Spades
void InitDeck() {
	for (int i = 0; i < 52; i++) {
		deck[i] = i;
	}
}

// Works on glovbal array deck and calculates a value for how displayed each card is
float CalcDisorder() {
	int total=0;
	for (int i = 1; i < 52; i++) {
		total += abs(deck[i] - deck[i - 1]);
	}
	printf("Total = %d\n", total);
	return total / (52.0f * 26.0f);
}

// Sum up distance card moved/max distance
float CalcDistance() {
	float distance = 0.0f;
	for (int i = 0; i < 52; i++) {
		float distanceDiv = (i < 26) ? 51 - i : i-1;
		//printf("%i: %3.0f\n", i, distanceDiv);
		distance += (abs(deck[i] - i) / distanceDiv);
	}
	return distance/52.0f;
}

// Shuffle a deck by swapping two random cards a specified number of times
void ShuffleDeck(int numtries) {
	int firstIndex, secondIndex;
	for (int i = 0; i < numtries; i++) {
		do {
			firstIndex = rand() % 52;
			secondIndex = rand() % 52;
		}
		while (firstIndex == secondIndex);
		int value = deck[firstIndex];
		deck[firstIndex] = deck[secondIndex];
		deck[secondIndex] = value;
	}
}

int main() {
	/* Intializes random number generator */
	srand((unsigned)time(&t));
	for (int i = 0; i < 25; i++) {
		InitDeck();
		ShuffleDeck(1000);
		printf("CalcDisorder() ==%f x %f = %f\n", CalcDisorder(),CalcDistance(),(double)CalcDisorder() * CalcDistance());
	}
	return 0;
}

Because I’m multiplying the two factors (disorder and Distance, the final value is never getting much above 0.35 and I’d prefer it to be in the range 0-0.999. Suggestions welcomed.

.

39 Puzzles in C

39 Puzzles in C

Simon Grantham PuzzlesThose of you who have used the Putty utility to connect to a remote computer using SSH might recognise the name chiark. It’s also the home of various puzzles that are coded in C and they’ve made the source code available.  You can read about each puzzle via the online documentation.

The puzzles are one player games and run natively on Unix (GTK), on Windows, and on Mac OS X. As usual I’ve added these to the C code links as well. Puzzles are near enough to games to count! I’ve screen grabbed 15 of them but there are almost 40 in total.

If you like this sort of thing and have an idea for a game, take a look at the devel page. The puzzles are split into three parts, front, middle and back ends. If you want to implement a new front end (SDL2 anyone?) then you just change the front end.

A better random number generator

A better random number generator

Binary numbers
Image by Gordon Johnson from Pixabay

How’s this for a minimal RNG implementation in C?

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

https://www.pcg-random.org/

is a website dedicated to random numbers using their algorithms, The whole site is good but I particularly like the party tricks page where they show that one of their random number generators generates a sequence that contains interesting things like source of a C file, zip files and text from hamlet.

More thoughts on shuffledness

More thoughts on shuffledness

Shuffling
Image by Hucklebarry from Pixabay

Thinking about what I said, it can’t be just about how far a card moves when shuffled but how much disordering occurs as well. If you shuffled the deck and discovered 7 cards in a sequence like 2,3,4,5,6 of hearts deep into the deck, they would have moved from near the top of the deck (an “ordered deck” is A-K in Hearts, Clubs, Diamonds and Spades) then it probably wasn’t a very good shuffle.

One way to measure “disorder” is to subtract each card’s ordinal value from it’s successor and sum up the absolute value of them . Ordinal value is the value 0-51 where 0 = Ace Hearts, 1 = 2 Hearts and so on. In an ordered deck the sum of all these subtractions will be 51. In a well shuffled deck I would guess it might be something like 1352 (52 x 26). Absolute value is the abs(x) function of x which is always positive if x is negative.  abs(-8) = 8. abs(8) = 8.

So now for shuffledness we have two values. Displacement and disorder. If both are calculated as a value between 0 and 1 then multiplying them together might work as a measure of shuffledness.

Here’s a very simple example of calculating the value for disorder. So far the calculations have never got a total much above 900, and not near 1352. I’ll run a few experiments and see the range of values.

// shuffledness.c : This measures how shuffled a deck of cards is
// cards are held as values 0-51 in a 52 int array.

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int deck[52];
time_t t;

// Order the cards 0-51. 0 = Acew Hards,13 = Ace Clubs,26 = Ace of Diamonds and 51 = King of Spades
void InitDeck() {
	for (int i = 0; i < 52; i++) {
		deck[i] = i;
	}
}

// Works on glovbal array deck and calculates a value for how displayed each card is
float CalcDisorder() {
	int total=0;
	for (int i = 1; i < 52; i++) {
		total += abs(deck[i] - deck[i - 1]);
	}
	printf("Total = %d\n", total);
	return total / (52.0f * 26.0f);
}

// Shuffle a deck by swapping two random cards a specified number of times
void ShuffleDeck(int numtries) {
	int firstIndex, secondIndex;
	for (int i = 0; i < numtries; i++) {
		do {
			firstIndex = rand() % 52;
			secondIndex = rand() % 52;
		}
		while (firstIndex == secondIndex);
		int value = deck[firstIndex];
		deck[firstIndex] = deck[secondIndex];
		deck[secondIndex] = value;
	}
}

int main() {
	/* Intializes random number generator */
	srand((unsigned)time(&t));
	InitDeck();
	ShuffleDeck(1000);
	printf("CalcDisorder() == %f\n", CalcDisorder());
	return 0;
}

That’s about 50 lines long. I’ll work on it and add the displacement calculation and try and get a maximum figure the the disorder calculation.

Fascinating look at the BBC Micro game Elite

Fascinating look at the BBC Micro game Elite

BBC Micro EditeThis is somewhat off-topic and a little bit of self-indulgence because (a) it’s about a computer that existed over 36 years ago and (b) a game that was programmed in 6502 assembler. It’s also a game I played a lot back in 1984.

The reason for including it here is because a British Web Developer called Mark Moxon has created an excellent website about the game, looking at the algorithms, source code etc. of the BBC Micro version of Elite. Everything you wanted to know about how it works.

I’d sum up this website as the “Cliff’s Notes” to the BBC Micro version of Elite. Be sure to click the three bars at the top left as the Navigation Bar gives an idea of just how much there is in this website. There’s bit by bit breakdowns of variables for example, in generating System Data.

Government
  ----------
  The government is given by a 3-bit value, taken from bits 3-5 of w1_lo. This
  value determine the type of government as follows:
  
    0 = Anarchy
    1 = Feudal
    2 = Multi-government
    3 = Dictatorship
    4 = Communist
    5 = Confederacy
    6 = Democracy
    7 = Corporate State

This is a remarkable piece of work, I can’t imagine how many hours Mark has put into it. Possibly as many as it took to develop the game originally!

Quake II – still a favourite

Quake II – still a favourite

Quake II screenshotOh I do play much newer games such as Far Cry 5 which I’ve completed recently but Quake II was a favourite of mine back in 1997 when I bought it. I’m more of a Quake than a Doom person. Unfortunately for me, my then PC couldn’t run it. It was only two years old as well.  But I got a new PC in 1998 and that played it just fine. I’m not saying I’m a saddo but I can play it through on the hardest level without losing a life.

The reason I mention it because of an article I came across that described the different ID Tech Game engines and the games made with each engine. All have been open sourced (Up to ID Tech 4). Quake II was written using the ID Tech 2 engine itself written in C and assembler.

For some reason the link to Quake II source code is wrong in that article but you can find it on GitHub. In one of 18 of ID Tech’s 18 repositories there.

If you are interested in downloading and trying to understand the Quake II source code, I strongly recommend you read Fabien Sangard’s walkthough of the code.

Interesting C Program- What do you think it does?

Interesting C Program- What do you think it does?

Question mark
Image by Gordon Johnson from Pixabay

This is a past IOCCC winner. It needs a #include <stdio.h> to compile.

#define _ -F<00||--F-OO--;
int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

When I compiled and ran it in Visual Studio it output 0.25 which is not the value it’s intended to output. That said it also messed up the formatting.

I can’t recommend this formatting BTW but then that’s the idea, to obfuscate i.e. disguise its purpose! So have you figured it out yet? I put the image on the right so as not to break up the program listing…