Read File Integers in Array Bubble Sort C++

Bubble Sort

In this tutorial, you volition learn nearly the bubble sort algorithm and its implementation in Python, Coffee, C, and C++.

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended lodge.

Just similar the movement of air bubbles in the water that rise up to the surface, each element of the array move to the end in each iteration. Therefore, it is called a bubble sort.

---

Working of Bubble Sort

Suppose nosotros are trying to sort the elements in ascending social club.

1. Get-go Iteration (Compare and Swap)

1. Starting from the first index, compare the first and the 2nd elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the 2d and the third elements. Bandy them if they are not in order.
4. The in a higher place process goes on until the last element.

   

   Compare the Next Elements

2. Remaining Iteration

The same process goes on for the remaining iterations.

Subsequently each iteration, the largest element amongst the unsorted elements is placed at the end.

Put the largest element at the cease

In each iteration, the comparison takes place upwardly to the terminal unsorted element.

Compare the adjacent elements

The array is sorted when all the unsorted elements are placed at their correct positions.

The assortment is sorted if all elements are kept in the correct order

---

Chimera Sort Algorithm

            bubbleSort(array)   for i <- 1 to indexOfLastUnsortedElement-1     if leftElement > rightElement       swap leftElement and rightElement end bubbleSort          

---

Bubble Sort Code in Python, Coffee and C/C++

                # Bubble sort in Python  def bubbleSort(array):        # loop to access each assortment element   for i in range(len(array)):      # loop to compare array elements     for j in range(0, len(array) - i - 1):        # compare two side by side elements       # modify > to < to sort in descending order       if array[j] > array[j + 1]:          # swapping elements if elements         # are non in the intended guild         temp = assortment[j]         array[j] = array[j+1]         array[j+1] = temp   information = [-two, 45, 0, 11, -9]  bubbleSort(information)  print('Sorted Array in Ascending Society:') print(information)              

                // Bubble sort in Java  import java.util.Arrays;  form Main {    // perform the bubble sort   static void bubbleSort(int array[]) {     int size = array.length;          // loop to access each array element     for (int i = 0; i < size - 1; i++)            // loop to compare array elements       for (int j = 0; j < size - i - 1; j++)          // compare two adjacent elements         // change > to < to sort in descending club         if (array[j] > array[j + 1]) {            // swapping occurs if elements           // are non in the intended club           int temp = array[j];           array[j] = array[j + 1];           array[j + 1] = temp;         }   }    public static void main(String args[]) {            int[] data = { -2, 45, 0, 11, -ix };          // phone call method using class name     Main.bubbleSort(data);          System.out.println("Sorted Array in Ascending Order:");     System.out.println(Arrays.toString(data));   } }              

                // Bubble sort in C  #include <stdio.h>  // perform the bubble sort void bubbleSort(int array[], int size) {    // loop to access each array chemical element   for (int step = 0; step < size - one; ++stride) {            // loop to compare array elements     for (int i = 0; i < size - footstep - 1; ++i) {              // compare ii adjacent elements       // change > to < to sort in descending order       if (assortment[i] > array[i + 1]) {                  // swapping occurs if elements         // are non in the intended order         int temp = assortment[i];         array[i] = array[i + 1];         array[i + 1] = temp;       }     }   } }  // impress array void printArray(int array[], int size) {   for (int i = 0; i < size; ++i) {     printf("%d  ", array[i]);   }   printf("\n"); }  int principal() {   int data[] = {-two, 45, 0, eleven, -9};      // find the assortment's length   int size = sizeof(data) / sizeof(data[0]);    bubbleSort(data, size);      printf("Sorted Array in Ascending Order:\northward");   printArray(data, size); }              

                // Bubble sort in C++  #include <iostream> using namespace std;  // perform bubble sort void bubbleSort(int assortment[], int size) {    // loop to admission each array element   for (int stride = 0; pace < size; ++step) {            // loop to compare array elements     for (int i = 0; i < size - step; ++i) {        // compare two adjacent elements       // change > to < to sort in descending order       if (assortment[i] > array[i + 1]) {          // swapping elements if elements         // are not in the intended social club         int temp = array[i];         assortment[i] = array[i + 1];         array[i + 1] = temp;       }     }   } }  // impress array void printArray(int assortment[], int size) {   for (int i = 0; i < size; ++i) {     cout << "  " << array[i];   }   cout << "\n"; }  int master() {   int data[] = {-2, 45, 0, 11, -9};      // notice array's length   int size = sizeof(information) / sizeof(data[0]);      bubbleSort(information, size);      cout << "Sorted Assortment in Ascending Order:\north";     printArray(data, size); }              

---

Optimized Bubble Sort Algorithm

In the to a higher place algorithm, all the comparisons are made even if the array is already sorted.

This increases the execution time.

To solve this, we can introduce an extra variable swapped. The value of swapped is set true if there occurs swapping of elements. Otherwise, it is ready simulated.

Afterwards an iteration, if there is no swapping, the value of swapped will be false. This ways elements are already sorted and there is no need to perform farther iterations.

This volition reduce the execution time and helps to optimize the bubble sort.

Algorithm for optimized bubble sort is

            bubbleSort(assortment)   swapped <- false   for i <- 1 to indexOfLastUnsortedElement-1     if leftElement > rightElement       swap leftElement and rightElement       swapped <- true terminate bubbleSort          

---

Optimized Bubble Sort in Python, Java, and C/C++

                # Optimized Bubble sort in Python  def bubbleSort(assortment):        # loop through each element of array   for i in range(len(assortment)):              # keep rail of swapping     swapped = Simulated          # loop to compare array elements     for j in range(0, len(array) - i - 1):        # compare ii adjacent elements       # change > to < to sort in descending guild       if array[j] > array[j + 1]:          # swapping occurs if elements         # are not in the intended gild         temp = array[j]         assortment[j] = array[j+1]         array[j+1] = temp          swapped = True                # no swapping means the array is already sorted     # so no need for further comparison     if non swapped:       intermission  data = [-2, 45, 0, 11, -ix]  bubbleSort(data)  print('Sorted Array in Ascending Order:') print(information)              

                // Optimized Bubble sort in Coffee  import java.util.Arrays;  form Main {    // perform the chimera sort   static void bubbleSort(int array[]) {     int size = assortment.length;          // loop to access each assortment chemical element     for (int i = 0; i < (size-1); i++) {            // check if swapping occurs       boolean swapped = false;              // loop to compare next elements       for (int j = 0; j < (size-i-i); j++) {          // compare 2 array elements         // change > to < to sort in descending order         if (array[j] > array[j + 1]) {            // swapping occurs if elements           // are not in the intended social club           int temp = array[j];           array[j] = array[j + one];           array[j + 1] = temp;                      swapped = true;         }       }       // no swapping means the array is already sorted       // and then no need for further comparison       if (!swapped)         break;      }   }    public static void primary(Cord args[]) {            int[] data = { -2, 45, 0, 11, -9 };          // call method using the class proper noun     Main.bubbleSort(data);          System.out.println("Sorted Array in Ascending Order:");     System.out.println(Arrays.toString(data));   } }              

                // Optimized Chimera sort in C  #include                                      // perform the bubble sort void bubbleSort(int array[], int size) {    // loop to access each assortment element   for (int step = 0; stride < size - ane; ++step) {          // check if swapping occurs       int swapped = 0;          // loop to compare array elements     for (int i = 0; i < size - step - 1; ++i) {              // compare two array elements       // modify > to < to sort in descending gild       if (array[i] > array[i + 1]) {                  // swapping occurs if elements         // are not in the intended society         int temp = assortment[i];         array[i] = assortment[i + 1];         array[i + 1] = temp;                  swapped = 1;       }     }          // no swapping ways the array is already sorted     // so no need for further comparison     if (swapped == 0) {       break;     }        } }  // print array void printArray(int assortment[], int size) {   for (int i = 0; i < size; ++i) {     printf("%d  ", array[i]);   }   printf("\northward"); }  // principal method int main() {   int data[] = {-ii, 45, 0, eleven, -9};      // observe the array's length   int size = sizeof(information) / sizeof(data[0]);    bubbleSort(data, size);      printf("Sorted Array in Ascending Order:\n");   printArray(data, size); }                              

                // Optimized bubble sort in C++  #include                                      using namespace std;  // perform bubble sort void bubbleSort(int array[], int size) {        // loop to admission each array element   for (int step = 0; step < (size-1); ++step) {            // check if swapping occurs     int swapped = 0;          // loop to compare ii elements     for (int i = 0; i < (size-step-one); ++i) {                // compare 2 array elements       // change > to < to sort in descending society       if (array[i] > array[i + one]) {          // swapping occurs if elements         // are not in intended order          int temp = array[i];         array[i] = array[i + 1];         array[i + 1] = temp;                  swapped = 1;       }     }      // no swapping means the array is already sorted     // and then no need of further comparing     if (swapped == 0)       suspension;   } }  // print an array void printArray(int array[], int size) {   for (int i = 0; i < size; ++i) {     cout << "  " << array[i];   }   cout << "\north"; }  int main() {   int information[] = {-two, 45, 0, 11, -9};      // detect the array's length   int size = sizeof(data) / sizeof(information[0]);      bubbleSort(data, size);      cout << "Sorted Array in Ascending Order:\n";   printArray(data, size); }                              

---

Bubble Sort Complication

Time Complexity
Best	O(n)
Worst	O(due north2)
Average	O(n2)
Space Complexity	O(1)
Stability	Yes

---

Complexity in Particular

Bubble Sort compares the adjacent elements.

Cycle	Number of Comparisons
1st	(n-1)
2d	(due north-2)
3rd	(n-3)
.......	......
concluding	i

Hence, the number of comparisons is

            (northward-1) + (n-two) + (northward-3) +.....+ 1 = n(n-one)/2          

most equals to northii

Hence, Complexity: O(n²)

Also, if nosotros find the code, bubble sort requires two loops. Hence, the complexity is n*n = due north2

1. Time Complexities

• Worst Case Complication: O(north2)
  If nosotros desire to sort in ascending order and the assortment is in descending order and so the worst case occurs.
• Best Case Complexity: O(n)
  If the assortment is already sorted, and then in that location is no demand for sorting.
• Average Case Complexity: O(n2)
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

• Space complexity is O(1) because an extra variable is used for swapping.
• In the optimized bubble sort algorithm, 2 extra variables are used. Hence, the space complexity will exist O(ii).

---

Chimera Sort Applications

Bubble sort is used if

• complexity does not affair
• brusk and simple code is preferred

---

Similar Sorting Algorithms

• Quicksort
• Insertion Sort
• Merge Sort
• Selection Sort

christianprolemare.blogspot.com

Source: https://www.programiz.com/dsa/bubble-sort

Share this post