Hackerrank - Sorting: Bubble Sort Solution
2 min read

Hackerrank - Sorting: Bubble Sort Solution

Hackerrank - Sorting: Bubble Sort Solution

Consider the following version of Bubble Sort:

for (int i = 0; i < n; i++) {
    
    for (int j = 0; j < n - 1; j++) {
        // Swap adjacent elements if they are in decreasing order
        if (a[j] > a[j + 1]) {
            swap(a[j], a[j + 1]);
        }
    }
    
}

Given an array of integers, sort the array in ascending order using the Bubble Sort algorithm above. Once sorted, print the following three lines:

  1. Array is sorted in numSwaps swaps., where  is the number of swaps that took place.
  2. First Element: firstElement, where  is the first element in the sorted array.
  3. Last Element: lastElement, where  is the last element in the sorted array.

Hint: To complete this challenge, you must add a variable that keeps a running tally of all swaps that occur during execution.

For example, given a worst-case but small array to sort:  we go through the following steps:

swap    a       
0       [6,4,1]
1       [4,6,1]
2       [4,1,6]
3       [1,4,6]

It took  swaps to sort the array. Output would beArray is sorted in 3 swaps. First Element: 1 Last Element: 6

Function Description

Complete the function countSwaps in the editor below. It should print the three lines required, then return.

countSwaps has the following parameter(s):

  • a: an array of integers .

Input Format

The first line contains an integer, , the size of the array .
The second line contains  space-separated integers .

Constraints

Output Format

You must print the following three lines of output:

  1. Array is sorted in numSwaps swaps., where  is the number of swaps that took place.
  2. First Element: firstElement, where  is the first element in the sorted array.
  3. Last Element: lastElement, where  is the last element in the sorted array.

Sample Input 0

3
1 2 3

Sample Output 0

Array is sorted in 0 swaps.
First Element: 1
Last Element: 3

Explanation 0
The array is already sorted, so  swaps take place and we print the necessary three lines of output shown above.

Sample Input 1

3
3 2 1

Sample Output 1

Array is sorted in 3 swaps.
First Element: 1
Last Element: 3

Explanation 1
The array is not sorted, and its initial values are: . The following  swaps take place:

At this point the array is sorted and we print the necessary three lines of output shown above.

Solution in Python

from itertools import product
def countSwaps(a):
    swaps = 0
    for i,j in product(range(len(a)),range(len(a)-1)):
        if a[j]>a[j+1]:
            a[j],a[j+1] = a[j+1],a[j]
            swaps += 1
    print("Array is sorted in %s swaps." %swaps)
    print("First Element:", a[0])
    print("Last Element:", a[-1])

n = int(input())
a = list(map(int,input().split()))
countSwaps(a)

Additional Info

The following two gives same output

for i in range(n):
    for j in range(n-1):
    	print(i,j)
from itertools import product
for i,j in product(range(n),range(n-1)):
    print(i,j)
    

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×