Algorithms and Data Structures

Bubble sort

Given an array of n integers, we’d like to sort them in increasing order. Bubble sort is one of the most popular and straightforward algorithms to achieve this (keep in mind that it’s not fast - so, most of the production algorithms use different techniques to sort a list of numbers).
With the bubble sort algorithm, we run several loops on the given array and swap any neighboring elements that are not in order. So, if , we swap those two to make sure the array is in increasing order.
More specifically, we take the initial array a (say a is [4, 1, -1, 0, 2, 8]) and look at the first two elements. If they are not in order, we swap their places (in our case [1, 4, -1, 0, 2, 8]). Then we move to the next pair. If they are not in order, we swap their places (in our case [1, -1, 4, 0, 2, 8]). We repeat this process until reaching the end of the array (in our example this will result in [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → no change → done).
The the loop starts again from the beginning. We look at the first pair in the array and compare them. If they are not in order, we swap them. Then we move on to the next pair, then to the one after those, and repeat it until reaching the end of the array. In our example this would result in: [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → no change.
This process is repeated until the whole array is completely sorted:
a = [...]
while True:                                 # run until the array is sorted
    is_sorted = True                        # if we change something, we set this to False
    for i in range(len(a) - 1):             # run from 0 ... n-2
        if a[i] > a[i + 1]:                 # if something is not in order
            is_sorted = False               # => array was not sorted
            a[i], a[i + 1] = a[i + 1], a[i] # swap a[i] and a[i + 1]
    
    if is_sorted:                           # stop the process if `a` is sorted
        break
print(a)
There is one optimizations we can do to avoid performing unnecessary steps:
  • We know that after each iteration, the largest elements appear at the very end of the array. So, after k steps, the top k elements of the array are for sure sorted and are at the very end of the array. Therefore, we can skip iterating over those in the inner loop
a = [...]
for u in range(len(a) - 1, 0, -1):          # u = upper bound for the inner loop
    is_sorted = True                        # if we change something, we set this to False
    for i in range(u):                      # run from 0 ... u-1
        if a[i] > a[i + 1]:                 # if something is not in order
            is_sorted = False               # => array was not sorted
            a[i], a[i + 1] = a[i + 1], a[i] # swap a[i] and a[i + 1]
    
    if is_sorted:                           # stop the process if `a` is sorted
        break
print(a)
The worst-case scenario for the bubble sort algorithm is the case of numbers being in the complete opposite order (descending) instead of ascending. In that case, the algorithm will perform operations. Which is a lot compared to faster algorithms, which we will cover later in the course.
Let’s simulate the algorithm on several arrays:
[4, 1, -1, 0, 2, 8]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    2. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    3. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
    4. i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
    5. i = 4 ⇒ do nothing
  1. u = 4
    1. i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
    2. i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
  1. u = 3
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. is_sorted is True ⇒ break
  1. print [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    2. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    3. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    4. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    5. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
  1. u = 4
    1. i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
    2. i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
    3. i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
    4. i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]
  1. u = 3
    1. i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
    3. i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]
  1. u = 2
    1. i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]
  1. u = 1
    1. i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. print [-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
  1. u = 5
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
    5. i = 4 ⇒ do nothing
    6. is_sorted is True ⇒ break
  1. print [1, 2, 3, 4, 5]

Challenge

n people are participating in a competition. You are asked to arrange them in an order of increasing height. At each step, you are allowed to ask two neighbor participants to swap places. You don’t have much time, so, you’d like to do this as efficiently as possible.
You’ve decided to write a program that would print the indices of the participants that should switch positions. Indexing starts from 0.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ ).
The next line contains n space-separated integers ( ≤ ≤ ) the heights of participants.

Output

The program should print the pairs of indices of participants that need to switch positions. Each pair needs to be printed on a separate line. In case of multiple optimal answers, any configuration is acceptable.

Examples

Input
Output
5 1 4 8 2 -1
2 3 3 4 1 2 2 3 1 2 0 1

Explanation

  1. 2 ↔ 3 ⇒ 1 4 2 8 -1
  1. 3 ↔ 4 ⇒ 1 4 2 -1 8
  1. 1 ↔ 2 ⇒ 1 2 4 -1 8
  1. 2 ↔ 3 ⇒ 1 2 -1 4 8
  1. 1 ↔ 2 ⇒ 1 -1 2 4 8
  1. 0 ↔ 1 ⇒ -1 1 2 4 8
 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue