Explanation

• Concept: Quick sort is a divide-and-conquer algorithm that selects a pivot element, partitions the array around the pivot, and recursively sorts the partitions.
• Process: Quick sort selects a pivot element, partitions the array into elements less than and greater than the pivot, and recursively sorts the partitions.
• Steps:
  • Select a pivot element.
  • Partition the array into elements less than and greater than the pivot.
  • Recursively sort the partitions.
• Efficiency: Quick sort has an average time complexity of O(n log n) but can degrade to O(n^2) in the worst case. It is generally faster than other O(n log n) algorithms for large datasets.

Python Implementation

      
          from typing import List

def quick_sort(arr: List[int]) -> List[int]:
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def run_algo():
    arr = [int(x) for x in input("Enter array (space separated): ").split()]
    sorted_arr = quick_sort(arr)
    print("Sorted array:", sorted_arr)

if __name__ == "__main__":
    run_algo()

        

Test Cases

• Random Order

  Input:

  • Array: [64, 25, 12, 22, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 12, 22, 11] is sorted in ascending order.

• Already Sorted

  Input:

  • Array: [11, 12, 22, 25, 64]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array is already sorted, so the output remains the same.

• Reverse Order

  Input:

  • Array: [64, 25, 22, 12, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 22, 12, 11] is sorted in ascending order.

• Single Element

  Input:

  • Array: [42]
  • Target:

  Expected Output: [42]

  Explanation: A single element array is already sorted.

• Empty Array

  Input:

  • Array: []
  • Target:

  Expected Output: []

  Explanation: An empty array remains empty after sorting.

Python Test Cases Implementation

          def run_tests():
    tests = [
        {"input": [64, 25, 12, 22, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [11, 12, 22, 25, 64], "expected": [11 ,12, 22, 25, 64]},
        {"input": [64, 25, 22, 12, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [42], "expected": [42]},
        {"input": [], "expected": []},
    ]
    for i, test in enumerate(tests, 1):
        result = quick_sort(test["input"])
        assert result == test["expected"], f"Test {i} failed: Expected {test['expected']}, got {result}"
        print(f"Test {i} passed.")
if __name__ == "__main__":
    run_tests()