We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Sorting: Bubble Sort
  2. Discussions

Sorting: Bubble Sort

Sort by

recency

|

404 Discussions

|

  • bdwoo95
     + 0 comments

    Bubble sort swaps every time a larger number is to the left of a smaller number. Therefore, if we count the number of times a larger number is left of a smaller one, we have the number of swaps.

    void countSwaps(vector<int> a) {
    // The number of swaps = for each number, how many smaller numbers are right of it
    // Put all numbers in a map and check against each element to the right of it
    // Still n^2 time, but removes necessity of all swaps, improving speed
    // If n=a.length(), number of checks is (n)(n-1)/2, the triangle number of n-1.
    int numSwaps = 0;
    map<int, int> numTracker;
    for (int num : a) {
        for (pair<int, int> trackedNum : numTracker) {
            // Compare a number to all numbers before to see how many of them it is smaller than
            if (num < trackedNum.first) {
                // Duplicate numbers must also be considered
                numSwaps += trackedNum.second;
            }
        }
        // Add the number at this index to our map
        numTracker[num]++;
    }
    
    // Smallest and largest numbers can be found in O(n) time.
    int minNum = * std::min_element(a.begin(), a.end());
    int maxNum = * std::max_element(a.begin(), a.end());
    
    cout << "Array is sorted in " << numSwaps << " swaps." << endl;
    cout << "First Element: " << minNum << endl;
    cout << "Last Element: " << maxNum << endl;
}

    This does not improve time complexity, but allows us to avoid swapping entirely. In practice, it should be more efficient, for the same reason insertion and selection sort are "better" than bubble sort despite the same time complexity.

  • sutradharjoy2006
     + 0 comments
    def countSwaps(a):
    count = 0
    n = len(a)-1
    for passes in range(n):
        for i in range(n-passes):
            if a[i]>a[i+1]:
                a[i],a[i+1]=a[i+1],a[i]
                count+=1
    # print(a,passes-1)
    print(f"Array is sorted in {count} swaps.\nFirst Element: {a[0]}\nLast Element: {a[-1]}")

  • henry_stevens00
     + 1 comment

    Having a question where the formatting of the answer needs to be exact is misleading. I had an extra space

    Compiler Message

    Wrong Answer

    Input (stdin)

    3

1 2 3

    Your Output (stdout)

    Array is sorted in 0 swaps.

First Element:  1

Last Element:  3

    Expected Output

    Array is sorted in 0 swaps.

First Element: 1

Last Element: 3

  • busragokmen671
     + 0 comments
    def countSwaps(a):
    temp = 0
    count = 0
    i = 0
   
    while i < len(a):
        idx = 0
        while idx < len(a)-1:
                if a[idx] > a[idx+1]:
                    count = count + 1
                    temp = a[idx]
                    a[idx] = a[idx+1]
                    a[idx+1] = temp
                idx = idx + 1
        i = i + 1
          

    
    print("Array is sorted in " + str(count) + " swaps.") 
    print("First Element:", a[0])
    print("Last Element:", a[len(a)-1])

  • codeacade
     + 0 comments

    Python:

        s = 0
    for i in range(1, len(a)):
        for j in range(i):
            if a[j] > a[i]:
                s += 1
                a[i], a[j] = a[j], a[i]