Bubble Sort:
You are given an array containing 𝑁 integers. Your task is to implement the Bubble Sort algorithm to sort this array.
Example:
Input:=6,array = {13, 46, 24, 52, 20, 9}
Output: 9, 13, 20, 24, 46, 52
Solution
Note:
Before diving into the solution, give it a try yourself
Approach:
Here’s a breakdown of how the Selection Sort algorithm works:
- First, we will select the range of the unsorted array. For that, we will run a loop(say i) that will signify the last index of the selected range. The loop will run backward from index n-1 to 0(where n = size of the array). The value i = n-1 means the range is from 0 to n-1, and similarly, i = n-2 means the range is from 0 to n-2, and so on.
- Within the loop, we will run another loop(say j, runs from 0 to i-1 though the range is from 0 to i) to push the maximum element to the last index of the selected range, by repeatedly swapping adjacent elements.
- Basically, we will swap adjacent elements(if arr[j] > arr[j+1]) until the maximum element of the range reaches the end.
- Thus, after each iteration, the last part of the array will become sorted. Like: after the first iteration, the array up to the last index will be sorted, and after the second iteration, the array up to the second last index will be sorted, and so on.
- After (n-1) iteration, the whole array will be sorted.
Note: Here, after each iteration, the array becomes sorted up to the last index of the range. That is why the last index of the range decreases by 1 after each iteration. This decrement is achieved by the outer loop and the last index is represented by variable i in the following code. And the inner loop(i.e. j) helps to push the maximum element of range [0….i] to the last index(i.e. index i).
Dry Run:
Iteration 1:
Iteration 2:
Iteration 3:
Iteration 4:
Iteration 5:
CODE
#include<iostream>
using namespace std;
void bubble_sort(int arr[], int n) {
// bubble sort
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
cout << "After Using bubble sort: " << "\n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
int main()
{
int arr[] = {13, 46, 24, 52, 20, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Before Using Bubble Sort: " << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
bubble_sort(arr, n);
return 0;
}
OUTPUT
Output:
Before Using Bubble Sort:
13 46 24 52 20 9
After Using bubble sort:
9 13 20 24 46 52
Time Complexity: O(N2) for the worst and average cases and O(N) for the best case. Here, N = size of the array.
Space Complexity: O(1)
Nice work
ReplyDeleteEach and every point is convered in this
ReplyDelete