void bubbleSort(vector<int>& arr, int n)
{
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(arr[i]>arr[j])
{
swap(arr[i],arr[j]);
}
}
}
}
Problem
Submissions
Hints & solutions
Discuss
Bubble Sort
Easy
0/40
Average time to solve is 15m
133 upvotes
Asked in company
Problem statement
You are given an integer array 'arr' of size 'N'.
You must sort this array using 'Bubble Sort'.
Change in the input array itself. You don't need to return or print the elements.
Input: ‘N’ = 7
'arr' = [2, 13, 4, 1, 3, 6, 28]
Output: [1 2 3 4 6 13 28]
Explanation: After applying bubble sort on the input array, the output is [1 2 3 4 6 13 28].
Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line contains an integer 'N' representing the size of the array.
The second line contains 'N' single space-separated integers representing the elements of the array.
The output contains the array elements after the sorting.
Sample Input 1:
7
2 13 4 1 3 6 28
Sample Output 1:
1 2 3 4 6 13 28
Explanation of Sample Output 1:
After applying bubble sort on the input array, the output is [1 2 3 4 6 13 28].
Sample Input 2:
5
9 3 6 2 0
Sample Output 2:
0 2 3 6 9
Explanation of Sample Output 2:
After applying bubble sort on the input array, the output is [0 2 3 6 9].
Constraints :
1 <= N <= 10^3
0 <= arr[i] <= 10^9
Time Limit: 1 sec
Hint
Hint 1
Apply Bubble Sort.
Approaches (1)
Approach 1
Bubble Sort
- To sort our array using Bubble Sort, we will repeatedly check the adjacent elements in our array, and if they are in the wrong order (i.e., the previous element is greater than the next element), we will swap both of them, we will do this until our array is sorted.
- We will use two nested loops.
- The outer one will go from ‘1’ to ‘n - 1’ using index ‘i’, and the inner loop will go from ‘1’ to ‘n - 1 - i’ using index ‘j’.
- The inner loop should go till ‘n - 1 - i’ elements only because all elements after the index ‘n - i - 1’ will already be sorted because of previous iterations.
- Inside the inner loop, we will check that if the ‘j + 1’th element is greater than the ‘jth’ element, we will swap both elements.
- Inside the inner loop, we will check that if the ‘j + 1’th element is greater than the ‘jth’ element, we will swap both elements.
The steps are as follows:-
// Function to sort an array using Bubble Sort
function bubbleSort(int[] arr, int n):
- Int ‘n’ is the size of the array ‘arr’.
- Iterate from index ‘1’ to ‘n - 1’ on array ‘arr’ using index ‘i’:
- Iterate from index ‘1’ to index ‘n - i - 1’ using index ‘j’:
- If ‘arr[j] > arr[j + 1]’:
- swap(arr[j], arr[j + 1])
- If ‘arr[j] > arr[j + 1]’:
- Iterate from index ‘1’ to index ‘n - i - 1’ using index ‘j’:
Time Complexity
O( N ^ 2 ), where 'N' is the array ‘arr’ size.
In the worst case, we have to do n^2 iterations on the array ‘arr’,
Hence the time complexity is O( N ^ 2 ).
Space Complexity
O( 1 ).
We are only some variables,
Hence the space complexity is O( 1 ).
Code Solution
(100% EXP penalty)
Bubble Sort
All tags
Sort by
Interview problems
Bubble Sort | Easy C++ code
#include<bits/stdc++.h>
using namespace std;
void bubbleSort(vector<int>& arr, int n)
{
// Write your code here.
for(int i=n-1;i>=0;i--){
int didSwap=0;
for(int j=0;j<=(i-1);j++){
if(arr[j]>arr[j+1])
swap(arr[j],arr[j+1]);
}
}
}
20 views
0 replies
0 upvotes
Interview problems
In CPP (Both using Loop and Using Recurrsion)
// void swap(int &i, int &j){
// int temp = i;
// i = j;
// j = temp;
// }
// __________using Loops__________
// void bubbleSort(vector<int>& arr, int n)
// {
// //write your code here
// for(int i=0; i<n; i++){
// for(int j=0; j<n-i-1; j++){
// if(arr[j] > arr[j+1]){
// swap(arr[j], arr[j+1]);
// }
// }
// }
// }
// __________using Recursion__________
void bubbleSort(vector<int>& arr, int n) {
if(n-1 <= 0) return;
for(int i =0; i<n-1; i++){
if(arr[i] > arr[i+1]){
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
bubbleSort(arr, n-1);
}
50 views
0 replies
1 upvote
Interview problems
Bubble Sort Algorithm using Java
public class Solution {
public static void bubbleSort(int[] arr, int n) {
//Your code goes here
int flag=0;
for(int i=n-2;i>=0;i--)
{
for(int j=0;j<=i;j++)
{
if(arr[j]>arr[j+1])
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag=1;
}
}
if(flag==0)
break;
}
}
}
42 views
0 replies
3 upvotes
Interview problems
Recursive C++ solution
void bubbleSortRecursive(vector<int>& arr, int n, int i )
{
int temp=0;
if (i>n -2)
{
return;
}
if (arr[i]>= arr[i+1])
{
temp = arr[i];
arr[i]=arr[i+1];
arr[i+1] = temp;
}
bubbleSortRecursive(arr, n, i+1);
}
void bubbleSort(vector<int>& arr, int n)
{
if (n<0)
{
return;
}
bubbleSortRecursive(arr, n, 0);
bubbleSort(arr, n-1);
return;
}
58 views
0 replies
0 upvotes
Interview problems
Easy Python Solution (Usual approach & recursive approach both)
from typing import List
def bubbleSort(arr: List[int], n: int):
# Your code goes here.
#Without Recursion
# for i in range(n-1, 0, -1):
# for j in range(0, i):
# if arr[j] > arr[j+1]:
# arr[j], arr[j+1] = arr[j+1], arr[j]
#Using Recursion
if n == 1:
return
for j in range(n-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
bubbleSort(arr, n-1)
pass 43 views
0 replies
2 upvotes
Interview problems
Bubble Sort
void bubbleSort(vector<int>& arr, int n)
{
//write your code here
for(int i=0; i<n-1; i++){
for(int j=0; j<n-1-i; j++){
if(arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
}
}
}
}
129 views
0 replies
0 upvotes
Interview problems
BUBBLE SORT
void bubbleSort(vector<int>& arr, int n)
{
int j;
for(int i=0;i<n-1;i++)
for(j=0; j<n-i-1; j++)
if(arr[j]>arr[j+1])
swap((arr[j]), arr[j+1]);
}
65 views
0 replies
0 upvotes
Interview problems
c++
void bubbleSort(vector<int>& arr, int n)
{
//write your code here
// sort(arr.begin(),arr.end());
for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
if(arr[j]>arr[j+1])
swap(arr[j],arr[j+1]);
}
}
}
50 views
0 replies
0 upvotes
Interview problems
one line c++ solution
void bubbleSort(vector<int>& arr, int n)
{
sort(arr.begin(),arr.end());
}
45 views
0 replies
0 upvotes
1
2
3
4
C++ (g++ 5.4)
Console