Python: Bubble Sort Analysis

 

Here's a Python function that sorts a list of numbers in ascending order. Identify the time complexity of this function. Then optimize this function and explain why it is faster. Don't use Python's in-built sort() method.

      def sort_list(list_to_sort):
  """
  This function sorts a list of numbers in ascending order using the bubble sort algorithm.

  Args:
    list_to_sort: A list of numbers to be sorted.

  Returns:
    A new list with the numbers sorted in ascending order.
  """
  # Create a copy of the list to avoid modifying the original
  sorted_list = list_to_sort.copy()
  n = len(sorted_list)

  # Iterate through the list n-1 times
  for i in range(n-1):
    # Flag to track if any swaps were made in a pass
    swapped = False
    # Iterate through the unsorted portion of the list
    for j in range(n-i-1):
      # Compare adjacent elements and swap if necessary
      if sorted_list[j] > sorted_list[j+1]:
        sorted_list[j], sorted_list[j+1] = sorted_list[j+1], sorted_list[j]
        swapped = True
    # If no swaps were made, the list is already sorted
    if not swapped:
      break

    # Return the sorted list
    return sorted_list

# Example usage
my_list = [1, 9, 5, 2, 1, 8, 6, 6, 3, 4, 10, 7]
sorted_list = sort_list(my_list)
print(sorted_list)  # Output: [1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10]
    

________________________________________

      def sort_list(list_to_sort):
  """
  This function sorts a list of numbers in ascending order using the bubble sort algorithm.

  Args:
    list_to_sort: A list of numbers to be sorted.

  Returns:
    A new list with the numbers sorted in ascending order.
  """
  # Create a copy of the list to avoid modifying the original
  sorted_list = list_to_sort.copy()
  n = len(sorted_list)

  # Iterate through the list n-1 times
  for i in range(n-1):
    # Flag to track if any swaps were made in a pass
    swapped = False
    # Iterate through the unsorted portion of the list
    for j in range(n-i-1):
      # Compare adjacent elements and swap if necessary
      if sorted_list[j] > sorted_list[j+1]:
        sorted_list[j], sorted_list[j+1] = sorted_list[j+1], sorted_list[j]
        swapped = True
    # If no swaps were made, the list is already sorted
    if not swapped:
      break

  # Return the sorted list
  return sorted_list

# Example usage
my_list = [1, 9, 5, 2, 1, 8, 6, 6, 3, 4, 10, 7]
sorted_list = sort_list(my_list)
print(sorted_list)  # Output: [1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10]
    

Time Complexity:

The provided function uses the Bubble Sort algorithm. The time complexity of bubble sort is O(n^2) in the worst and average case. This is because in the worst-case scenario, the function needs to compare and potentially swap each element with every other element in the list. This results in a nested loop structure, where each loop iterates over 'n' elements, leading to a time complexity of O(n * n) or O(n^2).

Optimization:

      def sort_list(list_to_sort):
  """
  This function sorts a list of numbers in ascending order using the insertion sort algorithm.

  Args:
    list_to_sort: A list of numbers to be sorted.

  Returns:
    A new list with the numbers sorted in ascending order.
  """
  # Create a copy of the list to avoid modifying the original
  sorted_list = list_to_sort.copy()
  n = len(sorted_list)

  # Iterate through the list, starting from the second element
  for i in range(1, n):
    # Store the current element
    key = sorted_list[i]
    # Move elements greater than the current element one position to the right
    j = i - 1
    while j >= 0 and key < sorted_list[j]:
      sorted_list[j + 1] = sorted_list[j]
      j -= 1
    # Insert the current element at its correct position
    sorted_list[j + 1] = key

  # Return the sorted list
  return sorted_list

# Example usage
my_list = [1, 9, 5, 2, 1, 8, 6, 6, 3, 4, 10, 7]
sorted_list = sort_list(my_list)
print(sorted_list)  # Output: [1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10]
    

Explanation:

The optimized function uses the Insertion Sort algorithm. It has a time complexity of O(n^2) in the worst case, but it is typically faster than Bubble Sort for nearly sorted lists.

• How Insertion Sort Works:

  1. It iterates through the list, starting from the second element.

  2. For each element, it compares it to the elements before it and shifts elements to the right until it finds the correct position for the current element.

  3. The current element is then inserted at its correct position.

• Why Insertion Sort is Faster than Bubble Sort:

  1. Fewer Swaps: Insertion sort performs fewer swaps than Bubble Sort, especially when the list is partially sorted.

  2. Adaptive: Insertion sort is adaptive, meaning it takes advantage of any existing order in the input list. If the list is already sorted, insertion sort completes in linear time.

Conclusion:

While both Bubble Sort and Insertion Sort have a time complexity of O(n^2) in the worst case, Insertion Sort is generally faster due to its adaptive nature and fewer swaps. Therefore, the optimized function using Insertion Sort is faster than the original function using Bubble Sort.