Question

Create a Python program that will take an unsorted list of 1000 integers and sort them using a bubble sort and an insertion sort. Your output should include displaying both sorted lists (from each algorithm) identifying each sorted list by the algorithm used.

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

Note: Please maintain proper code spacing (indentation), just copy the code part and paste it in your compiler/IDE directly, no modifications required.

#code with no comments, for easy and error free copying

import random


def bubble_sort(lst):
    for i in range(len(lst)):
        for j in range(len(lst) - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]


def insertion_sort(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and key < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key


def main():
    lst=[random.randint(0,1000) for i in range(1000)]
    lst1=lst.copy()
    lst2=lst.copy()
    bubble_sort(lst1)
    print("list sorted using bubble sort:\n")
    print(lst1)
    insertion_sort(lst2)
    print("\nlist sorted using insertion sort:\n")
    print(lst2)

main()

#same code with comments, for learning

import random


# method to sort a list using bubble sort algorithm
def bubble_sort(lst):
    # looping from i=0 to length-1
    for i in range(len(lst)):
        # looping from j=0 to length-i-2
        for j in range(len(lst) - i - 1):
            if lst[j] > lst[j + 1]:  # comparing elements at j and j+1
                # swapping values at j and j+1
                lst[j], lst[j + 1] = lst[j + 1], lst[j]


# method to sort a list using insertion sort algorithm
def insertion_sort(lst):
    # looping from i=1 to length-1
    for i in range(1, len(lst)):
        # storing value at i as key value
        key = lst[i]
        # moving elements between indices 0 and i-1 that are greater than key to one place right
        j = i - 1
        while j >= 0 and key < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        # adding key to index j+1
        lst[j + 1] = key


# main method
def main():
    # creating a list containing 1000 random integers between 0 and 1000
    lst = [random.randint(0, 1000) for i in range(1000)]
    # taking two copies of lst
    lst1 = lst.copy()
    lst2 = lst.copy()
    # passing first copy to bubble_sort(), printing sorted list
    bubble_sort(lst1)
    print("list sorted using bubble sort:\n")
    print(lst1)
    # passing second copy to insertion_sort(), printing sorted list
    insertion_sort(lst2)
    print("\nlist sorted using insertion sort:\n")
    print(lst2)


# calling main()
main()

#output (random)