EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login

Bubble Sort in Data Structure

By Savi JaggaSavi Jagga

Home » Data Science » Data Science Tutorials » Data Structures Tutorial » Bubble Sort in Data Structure

Bubble Sort in Data Structure

Introduction to Bubble Sort in Data Structure

Bubble Sort in Data Structure is one of the easiest sorting algorithm being used. The idea behind this algorithm is to repeatedly compare the elements one by one and swap the adjacent elements to bring them in the correct sorted order. Thus if there are n number of elements in the array, then each element will undergo n-1 comparisons. This way, after comparing one element with other elements in the array, an element is placed at its place in the sorted list just like a bubble rises up and move. Thus this algorithm is known as Bubble Sort. Several comparisons are more; thus, its complexity is more.

Algorithm for Bubble Sort in Data Structure

Bubble Sort is most often used to provide an insight into the sorting algorithms due to its simplicity. It is a stable as well as an in-place algorithm as it does not require extra storage area. Below is the pseudocode for this algorithm to sort the elements of an array arr in ascending order.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Code:

BubbleSort (arr):
BubbleSort (arr):
n =len(arr)
For i=0 to n-1 Repeat step 3
For j=1 to n-1:
If arr[i] > arr[j]: // Compare which one is greater
swap(arr[i],arr[j])

Explanation: In the above pseudocode, n refers to the number of elements in the array. Then the loop is run from the first element of the array to the last element for comparing every element to the next element of the array, if it is greater then they are swapped otherwise loop is incremented. This way, the first element is placed at its right place.

Example: Lets consider an array arr = [33,7,2,0,1,98,87,56]

First Pass:

I. 33,7,2,0,1,98,87,56
II. 7,33,2,0,1,98,87,56
III. 7,2,33,0,1,98,87,56
IV. 7,2,0,33,1,98,87,56
V. 7,2,0,1,33,98,87,56
VI. 7,2,0,1,33,98,87,56
VII. 7,2,0,1,33,87,98,56
VIII. 7,2,0,1,33,87,56,98

Second Pass:

I. 7,2,0,1,33, 87,56,98
II. 2,7,0,1,33, 87,56,98
III. 2,0,7,1,33, 87,56,98
IV. 2,0,1,7,33, 87,56,98
V. 2,0,1,7,33, 87,56,98
VI. 2,0,1,7,33, 87,56,98
VII. 2,0,1,7,33,56,87,98
VIII. 2,0,1,7,33, 56,87,98

Third Pass:

I. 2,0,1,7,33, 56,87,98
II.0,2,1,7,33,56,87,98
III. 0,1,2,7,33,56,87,98
IV. 0,1,2,7,33,56,87,98
V. 0,1,2,7,33,56,87,98
VI. 0,1,2,7,33,56,87,98
VII. 0,1,2,7,33,56,87,98
VIII. 0,1,2,7,33,56,87,98

Popular Course in this category
Sale
All in One Data Science Bundle (360+ Courses, 50+ projects)360+ Online Courses | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (3,220 ratings)
Course Price

View Course

Related Courses
Oracle DBA Database Management System Training (2 Courses)SQL Training Program (7 Courses, 8+ Projects)

A similar process is repeated until the loop ends. But we can see we already have got the sorted array. This limitation can be corrected using a flag that sees if any element is swapped in one pass, in case no element has been swapped indicates every element has been placed in the right position.

Code:

BubbleSort (arr):
n =len(arr)
swapped = true
For i=0 to n-1 Repeat 3 and 4 step:
For j=1 to n-1:
If arr[i] > arr[j]:
Swap(arr[i],arr[j])
else swapped =false
if(swapped == false)
break;

Program to Implement Bubble Sort in Data Structure

Bubble Sort algorithm is mostly used in computer graphics as it can detect minimal errors such as a swap of 2 elements in almost sorted arrays. It is also capable of fixing the error in linear time complexity. Its one of the famous implementation can be seen in polygon filling algorithm where sorting of bounding lines of polygon occurs using their x coordinate, and order changes occur at every intersection of the lines with incrementing y coordinate.

Program #1 – Bubble Sort Program

Below is the example of an implementation of the bubble Sorting algorithm in python:

Code:

def bubbleSort(myarr):
n = len(myarr)
for i in range(0,n-1):
for j in range(0, n-1):
if myarr[j] > myarr[j+1]:
myarr[j], myarr[j+1] = myarr[j+1], myarr[j] myarr = [33,7,2,0,1,98,87,56] bubbleSort(myarr)
print ("Array after Sorting is:")
for i in range(len(myarr)):
print ("%d" %myarr[i])

Output:

Bubble Sort in Data Structure 1-1

In the above program, one can also iterate the inner loop from 0 to n-i+1 as, after each pass, one element from the last comes to its sorted order location. Thus with each pass, the number of elements to be sorted reduces by 1.

Still, in the above program, one can also optimize to reduce the number of loops by checking if elements have become sorted with every pass.

Example #2 – Optimized Bubble Sort Program

Code:

def bubbleSort(myarr):
n = len(myarr)
for i in range(n):
swapped = False
for j in range(0, n-1):
if myarr[j] > myarr[j+1]:
myarr[j], myarr[j+1] = myarr[j+1], myarr[j] swapped = True
if swapped == False:
break
myarr = [33,7,2,0,1,98,87,56] bubbleSort(myarr)
print ("myarray after Sorting is :")
for i in range(len(myarr)):
print ("%d" %myarr[i],end=" ")

Output:

Bubble Sort in Data Structure 1-2

The complexity of Bubble Sort

  • Worst Case Complexity: O(n*n). This type of case occurs when elements of the array are sorted in reverse order. Thus each element of the array is visited twice.
  • Average Case Complexity: This case is similar to Worst case complexity as in this case array is half sorted. Thus loops are run through half the array. Thus complexity is O(n2).
  • Best Case Time Complexity: O(n). When elements of the array are already sorted, then complexity includes the time to loop through all elements once. Thus it takes linear time in the Best case.
  • Auxiliary Space: O(1) – As Bubble Sort requires no extra space for storing intermediate results; thus, almost no auxiliary space is required.

The disadvantage of Bubble Sort

The main disadvantage of Bubble sort can be seen while dealing with an array containing a huge number of elements. As worst-case complexity of this algorithm is O(n2), thus a lot more time is taken to sort them. Thus it is more suitable for teaching sorting algorithms instead of real-life applications.

Conclusion

It can be concluded that bubble sort is an effortless way of sorting the elements of an array, thus having more time complexity. It is a stable and in-place algorithm which is most used for introducing the concept of sorting algorithms. It is also used in computer graphics because of its feature to detect the minute errors and fix them in linear time.

Recommended Articles

This is a guide to Bubble Sort in Data Structure. Here we discuss the algorithm, complexity, and program to implement bubble sort in data structures with its disadvantages. You may also look at the following articles to learn more –

  1. Top 6 Sorting Algorithms in Python
  2. Different Types of Trees in Data Structure
  3. Array vs ArrayList- Comparision Table
  4. Operations on AVL Tree in Data Structure
  5. Complete Guide to Queue in Data Structure
  6. Searching in Data Structure | Techniques

All in One Data Science Bundle (360+ Courses, 50+ projects)

360+ Online Courses

1500+ Hours

Verifiable Certificates

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

Independence Day Offer - All in One Data Science Bundle (360+ Courses, 50+ projects) Learn More