C ++

Information Security (basic)

Python

Postgresql

Raspberrypi

2013

2014

2015

2016

2020

"Understanding Algorithms and Data Structures" by Brunskill and Turner was on the reading list of one the units on my CS course. It has some interesting chapters on searching. Although fairly basic in the scheme of things I found these basic sorting type fun to play around with.

Brunskill & Turner, pose some interesting questions along the way, such as how many comparisons are there?, how many swaps occur? , etc. They add a couple of interesting tweaks to get some performance lift. This is my rough take of the functions for those three search types.

void selection_sort(int numbers [],int size) { int comparisions=0; int swap=0; for (int i=1;i < size;i++) { int i_min=i; for (int j=i+1; j < size;j++) { ++comparisions; if (numbers[j] < numbers[i_min]) i_min =j; } if (i_min != i) { int temp=numbers[i_min]; numbers[i_min]=numbers[i]; numbers[i]=temp; ++swap; } } #cout comparisions & swaps }

void bubble_sort(int numbers [],int size) { int comparisions=0; int swap=0; for (int i=0;i < size;i++) for (int j=0; j< size; j++) { ++comparisions; if (numbers[j] > numbers[j+1]) { int tmp=numbers[j]; numbers[j]=numbers[j+1]; numbers[j+1] = tmp; ++swap; } } #cout comparisions & swaps }

void insertion_sort(int numbers [],int size) { int comparisons=0; int swap=0; for (int i=1;i < size;i++) { int pos=i; int val=numbers[i]; while ( pos >0 && val < numbers[pos-1]) { numbers[pos]= numbers[pos-1]; pos=pos-1; comparisons++; } numbers[pos]=val; swap++; } #cout comparisions & swaps }

**Results** - Running the above, on a various sizes of arrays with random numbers, with the `time` command, unsurprising shows the insertion sort (it does *far* less comparisons than the other two approaches) as the winner.

1. I used an array to store the numbers, using a vector might have been an alternative.

2. Using the time command gives a *very* rough indication of performance - could do alot better by putting a timer around the function call and not the programme itself.

3. The arrays all used different sets random numbers - obliviously they would need to be the same across all three tests to have strong validity.

posted at: 00:00 | path: /cpp | permanent link to this entry