TIME COMPLEXITY OF BUBBLE SORT >
Bubble sort has a worst-case and average complexity of О(n2), where n is the number of items being sorted. When the list is already sorted (best-case), the complexity of bubble sort is only O(n).
.
OTHER NAME OF BUBBLE SORT >
Sinking Sort: Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
.
PROCEDURE >
procedure bubbleSort(A : list of sortable items)
n := length(A)
repeat
swapped := false
for i := 1 to n-1 inclusive do
/* if this pair is out of order / if A[i-1] > A[i] then / swap them and remember something changed */
swap(A[i-1], A[i])
swapped := true
end if
end for
until not swapped
end procedure
.
ASCENDING ORDER
ALGORITHM >
Steps:
- Start
- First get array list with integers and named by a[]
- Then perform a for iteration range upto length(array)-1 by i
- Inside that loop get a nested for loop with length(array)-2 pointed by j
- Then check the value of the jth value with the j+1th value.
- If the j is bigger than j+1 then swap between them.
- If iteration performed successfully then print the array a[].
- Stop the program.
.
PYTHON PROGRAM >
|
1 2 3 4 5 6 7 |
>>> a=[6,2,8,0,3,1,5,4] >>> for i in range(len(a)): ... for j in range(len(a)-1): ... if(a[j]>a[j+1]): ... a[j],a[j+1]=a[j+1],a[j] ... >>> print("Sorted Array: ",a) |
C PROGRAM >
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<stdio.h> int main() { int arr[] = {6,2,8,0,3,1,5,4}; int n= sizeof(arr)/sizeof(arr[0]); int i,j,temp=0; for(i=0; i<n-1;i++) { for(j=0; j<n-i-1; j++) { if(arr[j]>arr[j+1]) { temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } }//i printf("\nSorted Array: [ "); for(i=0; i<n; i++) { if(i==n-1) { printf("%d ]\n",arr[i]); } else { printf("%d, ",arr[i]); } } return 0; } |
INPUT/OUTPUT:
Sorted Array: [0, 1, 2, 3, 4, 5, 6, 8]
.
DESCENDING ORDER :
ALGORITHM >
Steps
- Start
- First get array list with integers and named by a[]
- Then perform a for iteration range upto length(array)-1 by i
- Inside that loop get a nested for loop with length(array)-2 pointed by j
- Then check the value of the jth value with the j+1th value.
- If the j is lesser than j+1 then swap between them.
- If iteration performed successfully then print the array a[].
- Stop the program.
.
PROGRAM >
|
1 2 3 4 5 6 7 |
>>> a=[6,2,8,0,3,1,5,4] >>> for i in range(len(a)): ... for j in range(len(a)-1): ... if(a[j]<a[j+1]): ... a[j],a[j+1]=a[j+1],a[j] ... >>> print("Sorted Array: ",a) |
C PROGRAM >
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<stdio.h> int main() { int arr[] = {6,2,8,0,3,1,5,4}; int n= sizeof(arr)/sizeof(arr[0]); int i,j,temp=0; for(i=0; i<n-1;i++) { for(j=0; j<n-i-1; j++) { if(arr[j]<arr[j+1]) { temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } }//i printf("\nSorted Array: [ ") for(i=0; i<n; i++) { if(i==n-1) { printf("%d ]\n",arr[i]); } else { printf("%d, ",arr[i]); } } return 0; } |
INPUT/OUTPUT:
Sorted Array: [8, 6, 5, 4, 3, 2, 1, 0]
.
STATEMENT > A class contains 50 students who acquired marks in 10 subjects write a program to display top
10 students roll numbers and marks in sorted order by using bubble sorting technique.
PROGRAM:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
>>> from random import randint >>> >>> def bubble_sort(x): ... n=len(x) ... for i in range(0, len(x)): ... for j in range(0, n-i-1): ... if x[j]['total'] < x[j+1]['total']: ... (x[j],x[j+1])=(x[j+1],x[j]) ... return x ... >>> l=[] >>> for i in range(50): ... l.append( {"name":"abc"+str(i), "roll":i, "marks":[randint(10,99) for i in range(10)], "total":0}) ... >>> for i in range(50): #l ... for j in l[i]["marks"]: ... l[i]["total"]+=j ... >>> bubble_sort(l) >>> for i in range(0,10): ... print("\n", l[i]) ... # Output is generated different in different times because random function is used. |
.
INPUT/OUTPUT:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
{'name': 'abc22', 'roll': 22, 'marks': [85, 64, 72, 75, 61, 64, 61, 65, 93, 79], 'total': 719} {'name': 'abc5', 'roll': 5, 'marks': [33, 81, 82, 93, 73, 97, 57, 81, 52, 35], 'total': 684} {'name': 'abc18', 'roll': 18, 'marks': [59, 60, 38, 97, 96, 78, 17, 97, 40, 97], 'total': 679} {'name': 'abc25', 'roll': 25, 'marks': [55, 11, 79, 76, 70, 63, 69, 86, 91, 66], 'total': 666} {'name': 'abc16', 'roll': 16, 'marks': [99, 85, 62, 38, 43, 99, 72, 15, 96, 37], 'total': 646} {'name': 'abc4', 'roll': 4, 'marks': [35, 92, 21, 59, 50, 31, 67, 76, 94, 97], 'total': 622} {'name': 'abc9', 'roll': 9, 'marks': [72, 57, 38, 97, 57, 97, 62, 59, 16, 50], 'total': 605} {'name': 'abc20', 'roll': 20, 'marks': [91, 94, 70, 21, 92, 22, 23, 76, 79, 37], 'total': 605} {'name': 'abc43', 'roll': 43, 'marks': [73, 49, 48, 58, 39, 49, 90, 98, 53, 45], 'total': 602} {'name': 'abc34', 'roll': 34, 'marks': [68, 84, 76, 87, 65, 25, 25, 39, 31, 97], 'total': 597} |
.
This is a quick review about Bubble sorting algorithm. If you want to get the results in JAVA program then put a comment mentioning that.
.
