SORTING

Code in (C++)

// C++ program for the implementation of Bubble sort
    
    void bubbleSort(vector& v) {
        int n = v.size();
    
        // Outer loop that corresponds to the number of
        // elements to be sorted
        for (int i = 0; i < n - 1; i++) {
    
            // Last i elements are already
            // in place
            for (int j = 0; j < n - i - 1; j++) {
              
                  // Comparing adjacent elements
                if (v[j] > v[j + 1])
                  
                      // Swapping if in the wrong order
                    swap(v[j], v[j + 1]);
            }
        }
    }

Time Complexity

                        The above function always runs O(N2) time even if the array is sorted. 
It can be optimized by stopping the algorithm if the inner loop didn’t cause any swap.

Time Complexity: O(N2)

Space Complexity

                            The Space Complexity of the Bubble Sort Algorithm Bubble sort requires only a fixed amount of extra space for the flag, i, and size variables. 
As a result, the space complexity of bubble sort is O. (1).

Auxiliary Space: O(1)