## Labels

Linux (28) Python (13) Raspberry Pi (5) Bugs (3) Install (3) C (2) Brainf**k (1) HTML (1) Maths (1) Sorts (1)

## Monday, 12 November 2018

### Bubble sort in Python vs C

Sorting algorithms are used to put a elements of a list into a certain order. One example of a sorting algorithm is the bubble sort. The bubble sort works by comparing successive pairs of numbers in the list and then stops when no more swaps are required. The bubble sort is not a very efficient sorting algorithm.

Firstly lets write a bubble sort in Python that sorts the numbers into ascending order.

Create an array of filled with random numbers:
`numbers=[3,5,2,8,6,13,4,1,44]`

Worst case scenario we have to loop through all the numbers once for each number in the list:
```arrayLen=len(numbers)
for i in range(0, arrayLen):
```
Each time we loop through all the numbers the biggest number is moved to the end so we do not need to compare this value again as we already know that is the biggest. We also do not need to go to the last element as we compare it to the next element in the list.
```for j in range(0, arrayLen-i-1):
if( numbers[j] > numbers[j+1] ):
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
```

So putting it all together:
```numbers=[3,5,2,8,6,13,4,1,44]
for i in range(0, arrayLen):
for j in range(0, arrayLen-i-1):
if( numbers[j] > numbers[j+1] ):
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
```

But this code will carry on even when the numbers are already in order so we need to add a if statement to stop the program when no more swaps are being made.

```numbers=[3,5,2,8,6,55,4,1,44]
for i in range(0, len(numbers)):
swap=False
for j in range(0,len(numbers)-i-1):
if ( numbers[j] > numbers[j+1] ):
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
swap=True
if( swap == False ):
break
print(numbers)
```

This program now stops when no more swaps are being made and prints out the array after every pass.

The gives the result of :
```[3, 2, 5, 6, 8, 4, 1, 44, 55]
[2, 3, 5, 6, 4, 1, 8, 44, 55]
[2, 3, 5, 4, 1, 6, 8, 44, 55]
[2, 3, 4, 1, 5, 6, 8, 44, 55]
[2, 3, 1, 4, 5, 6, 8, 44, 55]
[2, 1, 3, 4, 5, 6, 8, 44, 55]
[1, 2, 3, 4, 5, 6, 8, 44, 55]
```

Now lets create an array of random numbers so we are not just testing the same numbers each time.
Change
```numbers=[3,5,2,8,6,55,4,1,44]
```
To
```numbers=[random.randint(1,10000) for _ in range(5000)]
```
And we will also need to import the random library by adding this line to the start of the program.
```import random
```

Lets now add a timer into the program so we can compare it to the C program.
Firstly import the time module by adding this line to the start
```import time
```
And add timing code so the final program looks like this
```import random
import time
numbers = [random.randint(1,10000) for _ in range(5000)]
start=time.time()
for i in range(0, 5000):
swap=False
for j in range(0,5000-i-1):
if ( numbers[j] > numbers[j+1] ):
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
swap=True
if( swap == False ):
break
end=time.time()
print(end-start)
```

Running this gives me a output of around 5s to 6s to sort a list of 5000 elements.

Now lets write a bubble sort in C using the same steps.

```#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
clock_t start,end;
double time_spent;
int numbers[5000],temp,stop;
srand(time(0));
//Initalize array with 5000 random numbers
for(int z=0;z<5000;z++)
numbers[z]=rand()%10000;
//Start timer
start = clock();
for(int i=0; i < 5000; i++)
{
stop=0;
for(int j=0; j < 5000-1;j++)
{
//Swap numbers if element j is bigger than element j+1
if(numbers[j] > numbers[j+1]){
temp=numbers[j];
numbers[j] = numbers[j+1];
numbers[j+1] = temp;
stop=1;

}
}
//Stop if numbers are in order(no swaps occured)
if(!stop)
break;

}
//Stop timer
end = clock();
time_spent = (double)(end-start) / CLOCKS_PER_SEC;
printf("%lf\n", time_spent);
return 0;
}

```

Running this usually takes around 0.1s-0.2s which is a great improvement on Pythons 5s-6s. Although the test isn't perfect it shows how Python is much slower than C. On the other hand the Python script is much shorter, so we trade performance for development time.