quick sort

Quicksort is an efficient, comparison-based sorting algorithm that uses the divide-and-conquer approach. It works by selecting a 'pivot' element from the array, partitioning the other elements into two sub-arrays (those less than the pivot and those greater than the pivot), and recursively sorting the sub-arrays.

 

The key steps are:

1. Pick a pivot: Choose an element from the array. The choice of pivot can be done in various ways (e.g., first element, last element, random element, or median).
2. Partition the array: Rearrange the elements so that all elements smaller than the pivot come before it, and all elements larger come after it.
3. Recursively apply quicksort: Apply the same process to the sub-arrays formed by splitting at the pivot.
4. Base case: An array of one or zero elements is already sorted.

 

Key Properties:

• Time complexity:
  • Average: O(n log n)
  • Worst case: O(n²) (when the pivot is chosen poorly, e.g., always the smallest or largest element)
• Space complexity: O(log n) due to the recursion stack.

 

Quicksort Python Implementation (easy)

def quicksort(arr):
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr
    else:
        # Choose the pivot (we are using the last element as pivot here)
        pivot = arr[-1]
        # Partition the array into two halves
        less_than_pivot = [x for x in arr[:-1] if x <= pivot]
        greater_than_pivot = [x for x in arr[:-1] if x > pivot]
        
        # Recursively apply quicksort to the partitions
        return quicksort(less_than_pivot) + [pivot] + quicksort(greater_than_pivot)

# Example usage:
arr = [33, 10, 55, 71, 29, 76, 2, 40]
sorted_arr = quicksort(arr)
print(sorted_arr)

 

In-place Quicksort: The above implementation creates new lists in every recursion step, increasing memory usage. A more efficient in-place quicksort modifies the original array.

 

Quicksort Python Implementation (modifying the original array)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1  # Index of the smaller element
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap

    # Place pivot in the correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)  # Partitioning index
        quicksort(arr, low, pi - 1)  # Sort the left of pivot
        quicksort(arr, pi + 1, high)  # Sort the right of pivot


# Example usage:
arr = [33, 10, 55, 71, 29, 76, 2, 40]
quicksort(arr, 0, len(arr) - 1)
print(arr)