AlphaCodingSkills

Bubble Sort


Advertisements

Previous Page Next Page

Bubble sort is the simplest sorting algorithm. The Bubble sort is based on the idea that every adjacent elements are compared and swapped if found in wrong order.

Example:

To understand the bubble sort, lets consider an unsorted array [1, 23, 10, -2] and discuss each step taken to sort the array in ascending order. In every pass, two adjacent elements are checked and swapped if found in wrong order.

First Pass: 1 and 23 are compared and found in correct order(ascending order in this case). After that 23 and 10 are compared, since (23>10), hence these numbers are swapped. Then 23 and -2 are compared and swapped.

Second Pass: 1 and 10 are compared and found in correct order. Then 10 and -2 are compared, since (10>-2), hence these numbers are swapped. After that 10 and 23 are compared and found in correct order.

Third Pass: 1 and -2 are compared, since (1>-2), hence these numbers are swapped. After that (1 and 10) and (10 and 23) are checked and found in correct order.

Bubble Sort

Implementation of Bubble Sort



# function for bubble sort
def bubblesort(MyList):
  for i in range(len(MyList)): 
    for j in range(len(MyList)-i-1):
      if(MyList[j]>MyList[j+1]):
        MyList[j] , MyList[j+1] = MyList[j+1], MyList[j]

# test bubble sort code                 
MyList = [1, 10, 23, 50, 4, 9, -4]
print("Original List")
for i in MyList:
  print(i, end=" ")
print("\n")

bubblesort(MyList)
print("Sorted List")
for i in MyList:
  print(i, end=" ")

Output

Original List
1 10 23 50 4 9 -4 

Sorted List
-4 1 4 9 10 23 50 



public class MyClass {
  // function for bubble sort
  static void bubblesort(int Array[]) {
    int n = Array.length;
    int temp;   
    for(int i=0; i<n; i++) 
    {
      for(int j=0; j<n-i-1; j++)
      {
        if(Array[j]>Array[j+1])
        {
          temp = Array[j];
          Array[j] = Array[j+1];
          Array[j+1] = temp;
        }
      }
    }
  }

  // function to print array
  static void PrintArray(int Array[]) 
    { 
        int n = Array.length; 
        for (int i=0; i<n; i++) 
        {  
          System.out.print(Array[i] + " "); 
        }
        System.out.println(); 
    } 

  //test bubble sort code
  public static void main(String[] args) {
    int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
    System.out.println("Original Array");
    PrintArray(MyArray);

    bubblesort(MyArray);
    System.out.println("\nSorted Array");
    PrintArray(MyArray);  
  }
}

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50 



#include <iostream>
using namespace std;

  // function for bubble sort
  static void bubblesort(int Array[], int n) 
  {
    int temp;
    for(int i=0; i<n; i++) 
    {
      for(int j=0; j<n-i-1; j++)
      {
        if(Array[j]>Array[j+1])
        {
          temp = Array[j];
          Array[j] = Array[j+1];
          Array[j+1] = temp;
        }
      }
    }
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      cout<<Array[i]<<" "; 
    }
    cout<<"\n"; 
  } 

 // test bubble sort code
 int main (){
    int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    cout<<"Original Array\n";
    PrintArray(MyArray, n);

    bubblesort(MyArray, n);
    cout<<"\nSorted Array\n";
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50



#include <stdio.h>

  // function for bubble sort
  static void bubblesort(int Array[], int n) 
  {
    int temp;
    for(int i=0; i<n; i++) 
    {
      for(int j=0; j<n-i-1; j++)
      {
        if(Array[j]>Array[j+1])
        {
          temp = Array[j];
          Array[j] = Array[j+1];
          Array[j+1] = temp;
        }
      }
    }
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      printf("%i ",Array[i]); 
    }
    printf("\n"); 
  } 

 // test bubble sort code
 int main (){
    int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    printf("Original Array\n");
    PrintArray(MyArray, n);

    bubblesort(MyArray, n);
    printf("\nSorted Array\n");
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50 



using System;

namespace MyApplication { 
   class MyProgram {
       // function for bubble sort
       static void bubblesort(int[] Array) 
       {
        int n = Array.Length;
          int temp;
          for(int i=0; i<n; i++) 
          {
            for(int j=0; j<n-i-1; j++)
            {
              if(Array[j]>Array[j+1])
              {
                temp = Array[j];
                Array[j] = Array[j+1];
                Array[j+1] = temp;
              }
            }
          }
       }

     // function to print array
     static void PrintArray(int[] Array) 
     { 
        int n = Array.Length; 
        for (int i=0; i<n; i++) 
        {  
          Console.Write(Array[i] + " "); 
        }
        Console.Write("\n"); 
     } 
 
    // test bubble sort code
    static void Main(string[] args) {
     int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
     Console.Write("Original Array\n");
     PrintArray(MyArray);

     bubblesort(MyArray);
     Console.Write("\nSorted Array\n");
     PrintArray(MyArray);  
    }
  }
}

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50

Time Complexity:

The time complexity of bubble sort is O(N²) in all cases even if the whole array is sorted because the entire array need to be iterated for every element and it contains two nested loops.


Previous Page Next Page