Bubble Sort Algorithm
In this Article we are going to work on the bubble sort algorithm in practice in multiple ways to get the sort array using bubble sort algorithm.
What is Bubble Sort Algorithm?
Bubble sort is a sorting algorithm that works by repeatedly stepping through lists that need to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. This passing procedure is repeated until no swaps are required, indicating that the list is sorted. Bubble sort gets its name because smaller elements bubble toward the top of the list.
Bubble sort is also referred to as sinking sort or comparison sort.
Explaination of Bubble Sort
Bubble sort has a worst-case and average complexity of O(n2), where n is the number of items sorted. Unlike the other sorting algorithms, bubble sort detects whether the sorted list is efficiently built into the algorithm. Bubble sort performance over an already sorted list is O(n).
The position of elements in bubble sort plays an important role in determining performance. Large elements at the beginning do not pose a problem as they are easily swapped. The small elements toward the end move to the beginning slowly. As such, these elements are called rabbits and turtles.
The bubble sort algorithm can be optimized by placing larger elements in the final position. After every pass, all elements after the last swap are sorted and do not need to be checked again, thereby skipping the tracking of swapped variables.
so now we've understand the what bubble sort is then start implementing it one by one in all possible ways
1. Incremental Linear Pointer Way
what does it mean by linear pointer way, For first method, we are going to compare current index value with the next indexes values one by one.
Let's See the Code to have better understanding
// Way 1 next index checking with current index
// 1. x pointer is on index 0
// 2. y pointer in on index 1
// each time whenever y execution finishes it increment values for both
// whenever x starts again for next index
for x := range arr {
var swapped bool
y := x + 1
for y = range arr {
if arr[x] < arr[y] {
arr[x], arr[y] = arr[y], arr[x]
swapped = true
}
}
if !swapped {
break
}
}
2. Backward Pointer Way
So in this we're moving our first loop from index 1 instead of 0 and for second loop we're running it from 0 index
Let's See the Code
// Way 2 previous index checking with current index
// 1. x pointer is on index 1
// 2. y pointer is on index 0
// whenever y finishes indexes increments for both
x := 1
for x = range arr {
var swapped bool
y := x - 1
for y = range arr {
if arr[x] < arr[y] {
arr[x], arr[y] = arr[y], arr[x]
swapped = true
}
}
if !swapped {
break
}
}
3. Left and Right Comparison
In this we're running our from both ends one is starting from index 0 and another one is starting from last index and both are incrementing and decrementing
Let's See the Code
// Way 3 comparing from both sides
// In this bubble sort solution we're trying to read values from both sides
// from left and at the same time from right and
// comparing both and swapping both values
for x := range arr {
var swapped bool
y := len(arr) - x - 1
for y = range arr {
if arr[x] < arr[y] {
arr[x], arr[y] = arr[y], arr[x]
swapped = true
}
}
if !swapped {
break
}
}
4. Reverse Method End To Start Comparison
We are running loop from end to start for this example.
Let's Checkout the Code
// Way 4 opposite of way 1
// In this bubble sort we're sorting array via right side
for x := len(arr) - 1; x >= 0; x-- {
var swapped bool
for y := x - 1; y >= 0; y-- {
if arr[x] < arr[y] {
arr[x], arr[y] = arr[y], arr[x]
swapped = true
}
}
if !swapped {
break
}
}
So Guys You have one task as we have example 2 I want you all to perform reverse method for that as well as and comment it below.
Comment Below For Full Code
Don't Forget To Subscribe My Youtube Channel as well:
Labels: algorithm, Golang, sorting, tutorial
0 Comments:
Post a Comment
If have any queries lemme know
Subscribe to Post Comments [Atom]
<< Home