Logo

Navigation
  • Home
  • Services
    • ERP Solutions
    • Implementation Solutions
    • Support and Maintenance Solutions
    • Custom Solutions
    • Upgrade Solutions
    • Training and Mentoring
    • Web Solutions
    • Production Support
    • Architecture Designing
    • Independent Validation and Testing Services
    • Infrastructure Management
  • Expertise
    • Microsoft Development Expertise
    • Mobile Development
    • SQL Server Database and BI
    • SAP BI, SAP Hana, SAP BO
    • Oracle and BI
    • Oracle RAC
  • Technical Training
    • Learn Data Management
      • Business Intelligence
      • Data Mining
      • Data Modeling
      • Data Warehousing
      • Disaster Recovery
    • Learn Concepts
      • Application Development
      • Client Server
      • Cloud Computing Tutorials
      • Cluster Computing
      • CRM Tutorial
      • EDI Tutorials
      • ERP Tutorials
      • NLP
      • OOPS
      • Concepts
      • SOA Tutorial
      • Supply Chain
      • Technology Trends
      • UML
      • Virtualization
      • Web 2.0
    • Learn Java
      • JavaScript Tutorial
      • JSP Tutorials
      • J2EE
    • Learn Microsoft
      • MSAS
      • ASP.NET
      • ASP.NET 2.0
      • C Sharp
      • MS Project Training
      • Silverlight
      • SQL Server 2005
      • VB.NET 2005
    • Learn Networking
      • Networking
      • Wireless
    • Learn Oracle
      • Oracle 10g
      • PL/SQL
      • Oracle 11g Tutorials
      • Oracle 9i
      • Oracle Apps
    • Learn Programming
      • Ajax Tutorial
      • C Language
      • C++ Tutorials
      • CSS Tutorial
      • CSS3 Tutorial
      • JavaScript Tutorial
      • jQuery Tutorial
      • MainFrame
      • PHP Tutorial
      • VBScript Tutorial
      • XML Tutorial
    • Learn Software Testing
      • Software Testing Types
      • SQA
      • Testing
  • Career Training
    • Career Improvement
      • Career Articles
      • Certification Articles
      • Conflict Management
      • Core Skills
      • Decision Making
      • Entrepreneurship
      • Goal Setting
      • Life Skills
      • Performance Development
      • Personal Excellence
      • Personality Development
      • Problem Solving
      • Relationship Management
      • Self Confidence
      • Self Supervision
      • Social Networking
      • Strategic Planning
      • Time Management
    • Education Help
      • Career Tracks
      • Essay Writing
      • Internship Tips
      • Online Education
      • Scholarships
      • Student Loans
    • Managerial Skills
      • Business Communication
      • Business Networking
      • Facilitator Skills
      • Managing Change
      • Marketing Management
      • Meeting Management
      • Process Management
      • Project Management
      • Project Management Life Cycle
      • Project Management Process
      • Project Risk Management
      • Relationship Management
      • Task Management
      • Team Building
      • Virtual Team Management
    • Essential Life Skills
      • Anger Management
      • Anxiety Management
      • Attitude Development
      • Coaching and Mentoring
      • Emotional Intelligence
      • Stress Management
      • Positive Thinking
    • Communication Skills
      • Conversation Skills
      • Cross Culture Competence
      • English Vocabulary
      • Listening Skills
      • Public Speaking Skills
      • Questioning Skills
    • Soft Skills
      • Assertive Skills
      • Influence Skills
      • Leadership Skills
      • Memory Skills
      • People Skills
      • Presentation Skills
    • Finding a Job
      • Etiquette Tips
      • Group Discussions
      • HR Interviews
      • Interview Notes
      • Job Search Tips
      • Resume Tips
      • Sample Resumes
 

C Algorithms – Bubble Sort

By Exforsys | on September 9, 2011 |
C Algorithms

Bubble sort is a simple sorting algorithm, which compares repeatedly each pair of adjacent items and swaps them if they are in the incorrect order. At the first run, the highest element of the list ends on the last place of the sorted list, and then, at the following run, the next highest element ends on one position lower than the previous element and so on. The initial list is finally sorted, when at a run, no swaps occur.

Even though it’s one of the simplest sorting algorithms, it’s almost never used in real life because of the bad performance on large sorting lists. It’s easy to learn, so it’s one of the first algorithms that people learn.

Step by step example :

Having the following list, let’s try to use bubble sort to arrange the numbers from lowest to greatest:

Unsorted list: 9 2 0 1 4 6

First run:

(9 2 0 1 4 6) -> (2 9 0 1 4 6) : 9>2, swap occurs

(2 9 0 1 4 6) -> (2 0 9 1 4 6) : 9>0, swap occurs

(2 0 9 1 4 6) -> (2 0 1 9 4 6) : 9>1, swap occurs

(2 0 1 9 4 6)-> (2 0 1 4 9 6) : 9>4, swap occurs

(2 0 1 4 9 6) -> (2 0 1 4 6 9) : 9>6, swap occurs. The last two elements are in the right order, no swaps occur, it’s the end of the first run.

Second run:

(2 0 1 4 6 9) -> (0 2 1 4 6 9) : 2>0, swap occurs

(0 2 1 4 6 9) -> (0 1 2 4 6 9): 2>1, swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 2<4, no swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 4<6, no swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 6<9, no swap occurs, it is the end of the list -> end of the second run.

The array is already sorted, but the algorithm doesn’t know that, so it requires another pass with no swaps in order to know the elements are in the right place.

Third run:

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 0<1, no swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 1<2, no swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 2<4, no swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 4<6, no swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 6<9, no swap occurs

The algorithm now knows that the list is sorted.

Sample code:

  1.  #include &lt; iostream &gt;
  2. using namespace std;
  3. int main()
  4. {
  5. 	int a[100];  // The sorting array
  6. 	int n;		// The number of elements
  7. 	cout &lt;&lt; &quot;Please insert the number of elements to be sorted: &quot;;
  8. 	cin &gt;&gt; n;	// The total number of elements
  9. 	for(int i=0;i&lt; n;i++)
  10. 	{
  11. 		cout &lt;&lt; &quot;Input &quot; &lt;&lt; i &lt;&lt; &quot; element: &quot;;
  12. 		cin &gt;&gt;a[i]; // Adding the elements to the array
  13. 	}
  14. 	cout &lt;&lt; &quot;Unsorted list:&quot; &lt;&lt; endl;	// Displaying the unsorted array
  15. 	for(int i=0;i&lt; n;i++)
  16. 	{
  17. 		cout &lt;&lt; a[i] &lt;&lt; &quot; &quot;;
  18. 	}
  19. 	int flag=-1;	// The flag is necessary to verify is the array is sorted, 0 represents sorted array
  20. 	int k=n;		// Another variable is required to hold the total number of elements
  21. 	while(flag!=0 &amp;&amp; k&gt;=0)		// Conditions to check if the array is already sorted
  22. 	{
  23. 		k=k-1;		
  24. 		flag=0;
  25. 		for (int i=0;i &lt; k;i++)
  26. 		{
  27. 			if(a[i]&gt;a[i+1])		// Check if the two adjacent values are in the proper order, if not, swap them
  28. 			{
  29. 				int aux=a[i];		// The swap procedure
  30. 				a[i]=a[i+1];
  31. 				a[i+1]=aux;
  32. 				flag=1;		// A swap has taken place, this means a new run of the algorithm must take place
  33. 			}				// to determine if the array is sorted.
  34. 		}
  35. 	}
  36. 	cout &lt;&lt; &quot;nSorted list:&quot; &lt;&lt; endl;	// Display the sorted array
  37. 	for(int i=0;i &lt; n;i++)
  38. 	{
  39. 		cout &lt;&lt; a[i] &lt;&lt; &quot; &quot;;
  40. 	}
  41.  
  42. 	return 0;
  43. }

Output:

Code explanation:

  1. while(flag!=0 &amp;&amp; k&gt;=0)
  2. {
  3. 		k=k-1;		
  4. 		flag=0;
  5. 	...
  6. }

A flag is required to check if any swaps have occurred at a run of the algorithm. If a swap has taken place, the flag becomes 1, and the while loop gets at least one more pass. When the flag is 0, it means that no swap has taken place so the arrays has been sorted and the while loop gets ignored.

Also, the k must be greater or equal to 0, this represents the number of elements of the list, and at each pass it decrements its value by 1. If this condition and the previous one are both true at the same time, then the array isn’t sorted, and the program enters the while loop. If one of the conditions is false, then the array has been sorted out.

Complexity:

Compares – there is a for loop embedded inside a while loop (n-1)+(n-2)+(n-3)+ … +1 which results in O(n^2), Swaps – Best Case 0, or O(1) and on Worst Case (n-1)+(n-2)+(n-3) + … +1 , or O(n^2).

Advantages:

  • it is easy to learn;
  • few lines of code;
  • works very well on already sorted lists, or lists with just a few permutations.

Disadvantages:

  • not effective for large numbers of sorting elements;
  • complexity is O(n^2).

Conclusion:

It is the best algorithm to begin learning sorting algorithms because it is the simplest. It is very easy to implement in every programming language. In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). Also, the bubble sort is considered a comparison algorithm, as it compares the elements at each run.

« « C Algorithms – The Problem of Sorting the Elements
C Algorithms – Insertion Sort » »

Author Description

Avatar

Editorial Team at Exforsys is a team of IT Consulting and Training team led by Chandra Vennapoosa.

Free Training

RSSSubscribe 394 Followers
  • Popular
  • Recent
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Merge Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Insertion Sort

    September 9, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Selection Sort

    September 11, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Heap Sort

    September 11, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Graph Theory

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment

Exforsys e-Newsletter

ebook
 

Related Articles

  • C Algorithms – Dijkstra’s Algorithm
  • C Algorithms – Breadth-First Search (BFS)
  • C Algorithms – Depth-First Search (DFS)
  • C Algorithms – Topological Sort
  • C Algorithms – Graph Theory

Latest Articles

  • Project Management Techniques
  • Product Development Best Practices
  • Importance of Quality Data Management
  • How to Maximize Quality Assurance
  • Utilizing Effective Quality Assurance Strategies
  • Sitemap
  • Privacy Policy
  • DMCA
  • Trademark Information
  • Contact Us
© 2023. All Rights Reserved.IT Training and Consulting
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptReject Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT