# James PK's Technical Journal

[ Home | Journal ]

## Mon, 16 Dec 2013

### C++ - Basic Sorting

"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.

Selection
```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
}
```
Bubble
```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
}
```
Insertion
```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.