Answer to Question #292409 in Python for kalpana T

Question

Write a program to sort a list of integers using Insertion sort, Mergesort and Quicksort. First take as input the size ‘n’ of the array, then read in the ‘n’ input integers that need to be sorted.

Answer 1

if __name__ == '__main__':
    choice = 1
    while choice != 0:
        print('\nMenu')
        print('1.Use QuickSort')
        print('2.Use Insertion Sort')
        print('3.Use Merge Sort')
        print('0.Quit')

        choice = int(input('Enter your choice: '))

        random_list_of_nums = []
        n = int(input("Enter number of characters: "))
        for i in range(n):
            random_list_of_nums.append(int(input("Enter numbers: ")))

        # QuickSort
        if choice == 1:
            def partition(nums, low, high):
                # We select the middle element to be the pivot. Some implementations select
                # the first element or the last element. Sometimes the median value becomes
                # the pivot, or a random one. There are many more strategies that can be
                # chosen or created.
                pivot = nums[(low + high) // 2]
                i = low - 1
                j = high + 1
                while True:
                    i += 1
                    while nums[i] < pivot:
                        i += 1

                    j -= 1
                    while nums[j] > pivot:
                        j -= 1

                    if i >= j:
                        return j

                    # If an element at i (on the left of the pivot) is larger than the
                    # element at j (on right right of the pivot), then swap them
                    nums[i], nums[j] = nums[j], nums[i]


            def quick_sort(nums):
                # Create a helper function that will be called recursively
                def _quick_sort(items, low, high):
                    if low < high:
                        # This is the index after the pivot, where our lists are split
                        split_index = partition(items, low, high)
                        _quick_sort(items, low, split_index)
                        _quick_sort(items, split_index + 1, high)

                _quick_sort(nums, 0, len(nums) - 1)


            quick_sort(random_list_of_nums)
            print(random_list_of_nums)
            break

        # Insertion Sort
        elif choice == 2:
            def insertion_sort(nums):
                # Start on the second element as we assume the first element is sorted
                for i in range(1, len(nums)):
                    item_to_insert = nums[i]
                    # And keep a reference of the index of the previous element
                    j = i - 1
                    # Move all items of the sorted segment forward if they are larger than
                    # the item to insert
                    while j >= 0 and nums[j] > item_to_insert:
                        nums[j + 1] = nums[j]
                        j -= 1
                    # Insert the item
                    nums[j + 1] = item_to_insert


            # Verify it works
            insertion_sort(random_list_of_nums)
            print(random_list_of_nums)
            break

        # Merge Sort
        elif choice == 3:
            def merge(left_list, right_list):
                sorted_list = []
                left_list_index = right_list_index = 0

                # We use the list lengths often, so its handy to make variables
                left_list_length, right_list_length = len(left_list), len(right_list)

                for _ in range(left_list_length + right_list_length):
                    if left_list_index < left_list_length and right_list_index < right_list_length:
                        # We check which value from the start of each list is smaller
                        # If the item at the beginning of the left list is smaller, add it
                        # to the sorted list
                        if left_list[left_list_index] <= right_list[right_list_index]:
                            sorted_list.append(left_list[left_list_index])
                            left_list_index += 1
                        # If the item at the beginning of the right list is smaller, add it
                        # to the sorted list
                        else:
                            sorted_list.append(right_list[right_list_index])
                            right_list_index += 1

                    # If we've reached the end of the of the left list, add the elements
                    # from the right list
                    elif left_list_index == left_list_length:
                        sorted_list.append(right_list[right_list_index])
                        right_list_index += 1
                    # If we've reached the end of the of the right list, add the elements
                    # from the left list
                    elif right_list_index == right_list_length:
                        sorted_list.append(left_list[left_list_index])
                        left_list_index += 1

                return sorted_list


            def merge_sort(nums):
                # If the list is a single element, return it
                if len(nums) <= 1:
                    return nums

                # Use floor division to get midpoint, indices must be integers
                mid = len(nums) // 2

                # Sort and merge each half
                left_list = merge_sort(nums[:mid])
                right_list = merge_sort(nums[mid:])

                # Merge the sorted lists into a new one
                return merge(left_list, right_list)


            # Verify it works
            random_list_of_nums = merge_sort(random_list_of_nums)
            print(random_list_of_nums)
            break