University:
Alabama State University
Course:
CSC 212 | Introduction to Data Structures and Algorithms
Academic year:

2024
Views:

344

Pages:

3
Author:

Mikael K. N.

Assignment Implementing QuickSort Algorithms Instructions: 1. Implement the QuickSort algorithm in the programming language of your choice (e.g., C, C++, Java, Python). 2. Include functions/methods for partitioning and the main QuickSort algorithm. 3. Test your implementation with a set of sample data to demonstrate the correctness of your code. 4. Provide comments and explanations for key parts of your code. 5. Discuss the time complexity of your implementation and compare it with other sorting algorithms. def quicksort(arr): """Sort an array using the QuickSort algorithm.""" 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 quicksort(left) + middle + quicksort(right) # Sample usage data_to_sort = [3, 6, 8, 10, 1, 2, 1] print("unsorted data:", data_to_sort); sorted_data = quicksort(data_to_sort) print("Sorted Data:", sorted_data) run proof on terminal : Explanation: • The quicksort function recursively divides the array into smaller subarrays, sorts each subarray, and then combines them. • The pivot is chosen as the middle element of the array, and elements are partitioned into three groups: those less than the pivot, equal to the pivot, and greater than the pivot. • The sorted array is obtained by concatenating the sorted left subarray, the middle elements, and the sorted right subarray. Time Complexity: • The average time complexity of QuickSort is O(n log n), making it efficient for large datasets. • The worst-case time complexity is O(n^2) when poorly chosen pivots lead to unbalanced partitions. • QuickSort is often faster in practice than other sorting algorithms due to its good average-case performance and low overhead.