DEV Community

Cover image for Introduction to Algorithm Part 2: Bubble Sort and Selection Sort.
Michellebuchiokonicha
Michellebuchiokonicha

Posted on

Introduction to Algorithm Part 2: Bubble Sort and Selection Sort.

#algorithms #bubblesortb #selectionsort #programming

This is a series continuation of Introduction to Algorithm: Linear Search versus binary search. Where we also discussed sorted and unsorted searches. You have to go through the first material before jumping on this as it is a continuation and you can only understand this after going through the first.

Here is the link to the first part of this series.
https://dev.to/michellebuchiokonicha/introduction-to-algorithm-linear-search-vs-binary-search-31j0

Bubble sort:

An algorithm is used to sort a set of elements. The idea is to move higher-value elements to the right and lower-value elements to the left.

How it works

Set the swap counter to a non-zero value. Repeat until the swap counter is 0: Reset the swap counter to 0. Look at each adjacent pair If two adjacent elements are not in order, swap them and add one to the swap.

Example:

Let swapCounter = 2;
Let arr=[9,4,5,1,8,7,2]
Enter fullscreen mode Exit fullscreen mode

First, we need to reset the swap counter to zero then we look at each adjacent pair.

To reset, swapCounter now equals 0. swapCounter == 0;

The first pair is 9 and 4


[9,4,5,1,8,7,2]
Enter fullscreen mode Exit fullscreen mode

They are out of order.
We need to swap them.
Then swapCounter++;
swapCounter = 1;
Now, we have

[4,  9,5,1,8,7,2]
Enter fullscreen mode Exit fullscreen mode

The next pair is 9 and 5.
They are also out of order.

[4,  9,5,1,8,7,2]
Enter fullscreen mode Exit fullscreen mode

We need to swap them
swapCounter++;
swapCounter == 2;
Now we have

[4,5,  9,1,8,7,2]
Enter fullscreen mode Exit fullscreen mode

The next pair is 9 and 1. They are out of order [4,5, 9,1,8,7,2] so we need to swap them. swapCounter++; swapCounter == 3; Now we have

[4,5,1,  9,8,7,2]
Enter fullscreen mode Exit fullscreen mode

The next pair is 9 and 8.
They are not out of order

[4,5,1,  9,8,7,2]
Enter fullscreen mode Exit fullscreen mode

so we swap them
swapCounter++;
swapCounter == 4;

[4,5,1,8,  9,7,2]
Enter fullscreen mode Exit fullscreen mode

The next pair is 8 and 7.
They are out of order

[4,5,9,1,  8,7,2]
Enter fullscreen mode Exit fullscreen mode

so we swap them
swapCounter++
swapCounter = 5;
Now we have

[4,5,9,1,7, 8,2]
Enter fullscreen mode Exit fullscreen mode

The next pair is 8 and 2.
They are out of order

[4,5,9,1,7,  8,2]
Enter fullscreen mode Exit fullscreen mode

so we swap them swapCounter++;

swapCounter = 6;
Enter fullscreen mode Exit fullscreen mode

Now we have

[4,5,9,1,7,2,  8]
Enter fullscreen mode Exit fullscreen mode

We start from the top again with this new array.

The idea is to repeat this procedure until the swapCounter == 0;

So we reset the swapCounter again swapCounter = 0;

Arr = [4,5,9,1,7,2,8]
Enter fullscreen mode Exit fullscreen mode

The first pair here is 4 and 5.
They are inorder

[4,5,  9,1,7,2,8]
Enter fullscreen mode Exit fullscreen mode

so we don’t swap them.
Hence, we don’t increase the swapCounter.
swapCounter == 0

The next one is 5 and 9. They are in order

[4,5,9,  1,7,2,8]
Enter fullscreen mode Exit fullscreen mode

so we don’t swap them
Hence, we don’t increase the swapCounter.
swapCounter == 0.

The next one is 9 and 1.
They are out of order

[4,5,9,1,7,2,8]
Enter fullscreen mode Exit fullscreen mode

so we swap them.

[4,5,1,  9,7,2,8]
Enter fullscreen mode Exit fullscreen mode

swapCounter++;
swapCounter = 1;
Now we have

[4,5,1,  9,7,2,8]
Enter fullscreen mode Exit fullscreen mode

The next pair is 9 and 7.
They are out of order

[4,5,1,  9,7,2,8]
Enter fullscreen mode Exit fullscreen mode

so we swap them

[4,5,1,7  9,2,8]
Enter fullscreen mode Exit fullscreen mode

swapCounter++;
swapCounter = 2;
Now we have

[4,5,1,7,  9,2,8]
Enter fullscreen mode Exit fullscreen mode

The next pair is 9 and 2.
They are out of order

[4,5,1,  9,2,8]
Enter fullscreen mode Exit fullscreen mode

so we swap them.

[4,5,1,2  9,8]
Enter fullscreen mode Exit fullscreen mode

swapCounter++;
swapCounter == 3;
Now we have

[4,5,1,7,2,  9,8]
Enter fullscreen mode Exit fullscreen mode

The next pair is 9 and 8.
They are out of order

[4,5,1,2  9,8]
Enter fullscreen mode Exit fullscreen mode

so we swap them.

[4,5,1,2,  9,8]
Enter fullscreen mode Exit fullscreen mode

swapCounter++;
swapCounter == 4;
Now we have

[4,5,1,7,2,8,9]
Enter fullscreen mode Exit fullscreen mode

Now we have

[4,5,1,7,2,8,9]
Enter fullscreen mode Exit fullscreen mode

So we have to start again since we got to the end of the swap. Reset swapCounter
swapCounter == 0;

The first pair here is 4 and 5. It is in order.

[4,5, 1,7,2,8,9]
Enter fullscreen mode Exit fullscreen mode 
swapCounter == 0;
Enter fullscreen mode Exit fullscreen mode

The next pair is 5 and 1.
It is out of order

[4,5, 1,7,2,8,9]
Enter fullscreen mode Exit fullscreen mode

we need to swap them
swapCounter++;

swapCounter == 1;

Now we have

[4,1,5,  7,2,8,9]
Enter fullscreen mode Exit fullscreen mode

The next pair is 5 and 7. It is in order

[4,1,5,7,  2,8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 1;

The next pair is 7 and 2. It is out of order

[4,1,5,7,  2,8,9]
Enter fullscreen mode Exit fullscreen mode

so we swap
swapCounter++;
swapCounter == 2;
Now we have

[4,1,5,2,7,  8,9]
Enter fullscreen mode Exit fullscreen mode

The next pair is 7 and 8. They are in order

[4,1,5,2,7,8,  9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 2;

The next pair is 8 and 9. They are in order.

[4,1,5,2,7,8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 2;

We start from the beginning again
Reset the swapCounter
swapCounter == 0;

The first pair is out of order

[4,1,5,2,7,8,9]
Enter fullscreen mode Exit fullscreen mode

so we swap them
swapCounter++;
swapCounter == 1;
Now we have

[1,4,  5,2,7,8,9]
Enter fullscreen mode Exit fullscreen mode

The next pair is 4 and 5. They are in order


[1,4,5,  2,7,8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 1;

The next pair is 5 and 2. They are out of order

[1,4,5,  2,7,8,9]
Enter fullscreen mode Exit fullscreen mode

so we swap them

[1,4,5,  2,7,8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter++;
swapCounter == 2;
Now we have

[1,4,2,5,  7,8,9]
Enter fullscreen mode Exit fullscreen mode

The next pair is 5 and 7. They are in order.

[1,4,2,5,7,  8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 2;

The next pair is 7 and 8.
They are in order.

[1,4,2,5,7,8,  9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 2;

The next pair is 8 and 9. They are in order.

[1,4,2,5,7,8,  9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 2;

We start from the beginning again
Reset swapCounter
swapCounter == 0;

arr = [1,4,2,5,7,8,9]
Enter fullscreen mode Exit fullscreen mode

The first pair is 1 and 4. They are in order

[1,4,  2,5,7,8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 0;

The next pair is 4 and 2. They are out of order

[1,4,  2,5,7,8,9]
Enter fullscreen mode Exit fullscreen mode

so swap them.
swapCounter++;
swapCounter == 1;
Now we have

[1,2,4,  5,7,8,9]
Enter fullscreen mode Exit fullscreen mode

The next pair is 4 and 5. They are in order

[1,2,4,5,  7,8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 1;

The next pair is 5 and 7. They are in order

[1,2,4,5,7,  8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 1;

The next pair is 7 and 8. They are in order

[1,2,4,5,7,8,  9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 1;

The next pair is 8 and 9. They are in order.

[1,2,4,5,7,8,9]
Enter fullscreen mode Exit fullscreen mode

swapCounter == 1;

We start from the beginning
Reset
swapCounter = 0;

The first pair is 1 and 2. They are in order. The next pair is 2 and 4. They are in order. The next pair is 4 and 5. They are in order. The next pair is 5 and 7. They are in order The next pair is 7 and 8. They are in order. The next pair is 8 and 9. They are in order

So we have

[1,2,4,5,7,8,9]
Enter fullscreen mode Exit fullscreen mode


swapCounter = 0;

Here, we can declare the entire array sorted since swapCounter = 0;

Worst-case scenario: The array is in reverse order, we have to bubble each of the n elements all the way across the array, and since we can only fully bubble one element into position per pass, we must do this n times. The formula is O(n square) since you have to go through all the elements

Best-case scenario: The array is already perfectly sorted and we make no swaps on the first pass. The formular is omega(n).

Selection Sort

It is an algorithm that sorts a set of elements. The idea is to find the smallest unsorted element and add it to the sorted list.

To achieve this: Repeat the process of finding the smallest element in the array Search the unsorted part of the data to find the smallest value Swap the smallest found value with the first element of the unsorted part.


Let arr = [9,4,6,3,5,7,1,8]
Enter fullscreen mode Exit fullscreen mode

We search through the array to find the smallest value smallestValue = 1;

Next, swap that value with the first element of the unsorted part So we swap 9 and 1 We now have

[1,  4,6,3,5,7,9,8]
Enter fullscreen mode Exit fullscreen mode

We repeat the process again for the unsorted part

The smallest value of the unsorted array is 3

[1,  4,6,3,5,7,9,8]
Enter fullscreen mode Exit fullscreen mode

Swap it with the first element of the unsorted part. So we swap 4 and 3 Now, we have

[1,3,  6,4,5,7,9,8]
Enter fullscreen mode Exit fullscreen mode

Next, we repeat again

smallestValue of the unsorted part = 4

[1,3,  6,4,5,7,9,8]
Enter fullscreen mode Exit fullscreen mode

Swap it with the first element of the unsorted part We swap 6 and 4 Now we have

[1,3,4,  6,5,7,9,8]
Enter fullscreen mode Exit fullscreen mode

Next, we repeat again the smallestValue of the unsorted array = 5

[1,3,4,  6,5,7,9,8]
Enter fullscreen mode Exit fullscreen mode

Swap 6 and 5 Now we have

[1,3,4,5,  6,7,9,8]
Enter fullscreen mode Exit fullscreen mode

Next, we repeat again

The smallestValue of the unsorted part = 6
[1,3,4,5,   6,7,9,8]
Enter fullscreen mode Exit fullscreen mode

Which happens to be the first element of the unsorted part

[1,3,4,5,6,  7,9,8]
Enter fullscreen mode Exit fullscreen mode 
Next the smallestValue = 7;
It is also the first element of the unsorted part
[1,3,4,5,6,  7,9,8]
it becomes
[1,3,4,5,6,7,  9,8]
Enter fullscreen mode Exit fullscreen mode 
Next, the smallestValue = 8;
[1,3,4,5,6,7,  9,8]
Enter fullscreen mode Exit fullscreen mode

Swap 9 and 8 Now we have

[1,3,4,5,6,7,8,  9]
Enter fullscreen mode Exit fullscreen mode

Next, the only value left is 9

[1,3,4,5,6,7,8,  9]
Enter fullscreen mode Exit fullscreen mode

We move it to the sorted part.

[1,3,4,5,6,7,8,9]
Enter fullscreen mode Exit fullscreen mode

Worst-case scenario: We have to loop over all the elements of the array to find the smallest unsorted element and we must repeat this process n times since only one element gets sorted on each pass. It is represented as O(n square).

Best-case scenario: there is no way to guarantee the array is sorted until we go through the same process for all the elements. It is represented as omega(n square).

Follow me on Twitter Handle: https://twitter.com/mchelleOkonicha

Follow me on LinkedIn Handle: https://www.linkedin.com/in/buchi-michelle-okonicha-0a3b2b194/

Top comments (2)

Collapse
 
kalkwst profile image
Kostas Kalafatis •

Hey there, great article! I just wanted to share a tip with you - did you know that dev.to has a built-in functionality for making series? It can be a great way to organize related content and keep readers engaged. When you're writing your post, just click on the hexagon next to Save draft, and you can create a series from there. Keep up the good work!

Collapse
 
michellebuchiokonicha profile image
Michellebuchiokonicha •

Thank you. This is really informative. I’d do that. Cheers.

Read next

ccoveille profile image

Go: the future encoding/json/v2 module

Christophe Colombier -

tanujav profile image

Count Good Nodes in Binary Tree | LeetCode | Java

Alysa -

respect17 profile image

A Friendly Guide to Coding Collaboration

Kudzai Murimi -

rrajat profile image

Fine-tune your first large language model (LLM) with LoRA, llama.cpp, and KitOps in 5 easy steps

Rajat Raina -