# Programming: Sort

## Sort

### Bubble Sort: `O(N^2)`

Repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed.

- It will start by comparing index 0 with 1
- If index 0 is greater than 1, it will swap them
- Then it will compare index 1 with 2
- At the end of the first iteration, the largest element will be at the end of the list
- In the second iteration, we will not include the last element. We will continue until we have no more elements to compare:

```
# number of comparations
N
N-1
N-2
...
```

This is a Gauss sum:

```
N + N-1 + ... + 2 + 1 = N(N+1)/2 -> O(N^2)
```

```
void bubbleSort(int array[], int size) {
// check if swapping occurs
int swapped;
// run loops two times: one for walking throught the array
for (int i = 0; i < size - 1; ++i) {
swapped = 0;
// loop to compare array elements
for (int j = 0; j < size - i - 1; ++j) {
// compare two adjacent elements
if (array[j] > array[j + 1]) {
// swapping
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = 1;
}
}
// already sorted
if (swapped == 0) {
break;
}
}
}
```

#### Optimized Bubble Sort

- Worst-case performance:
`O(N^2), O(N^2) swaps`

- Best-case performance:
`O(1)`

- Average performance:
`O(lg N)`

- Worst-case space complexity:
`O(1)`

ℹ️

NoteCode examples in different languages are available in gitgub.

## Leave a Comment