Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
      • 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
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
      • 17
      • 18
        Graph Representation
      • 19

  • Bogosort

    We have worked with sorted lists for many different problems. We have used built-in functions to sort some arrays. Yet, it’s not obvious how those built-in functions actually work under the hood. In this chapter, we’ll discuss some of the most popular sorting algorithms that are used in different places - depending on the application.
    The first algorithm we’ll discuss is the most ridiculous of all of the sorting algorithms. It’s called Bogosort. It’s not used anywhere in real-world applications, and you’ll soon see why.
    Given n numbers, the algorithm works by randomly shuffling those numbers and then checking if the resulting list is sorted:
    from random import shuffle
    a = [3, 1, -2, 5, 6]            # Initial numbers
    while True:                     # Loop until the array is sorted
        is_sorted = True
        for i in range(1, len(a)):  # A loop to check if the array is sorted
            if a[i] < a[i-1]:       # If we find an element smaller then previous => it's not sorted
                is_sorted = False   # We set the variable to False and stop the loop
        if is_sorted:               # If the array is sorted => stop the infinite loop
        else:                       # Otherwise shuffle the list again
    print(a)                        # Finally print the resulting list
    This algorithm is random and it can take infinitely long to complete. Therefore, it would be really dangerous and inefficient to use something like this in production applications.
    You are asked to compute the number of iterations it would take for a Bogosort algorithm to finally find a solution.


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


    The program should print the number of iterations it would take the Bogosort algorithm to complete the search.


    5 5 -1 2 3 9


    The number 10 is a random number - it could’ve been 2, or 200. You might get different numbers when running the same program on the same input several times.


    Time limit: 30 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

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