Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • 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: 0.99 seconds

    Memory limit: 512 MB

    Output limit: 10 MB

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