Quick Sort

How to use playfair cypher to encode and decode messages

Sorting algorithms are the digital world's heroes, keeping data organized. Today, we'll tackle Quick Sort, a powerful algorithm known for its swiftness in tackling large datasets. Buckle up for a journey through partitioning and pivots!

The Divide-and-Conquer Spirit

Quick Sort shares the divide-and-conquer approach with Merge Sort. Here's the core idea:

Choose a pivot element (typically the first or last element). Rearrange the list such that elements less than the pivot are placed on its left side and elements greater than or equal to the pivot are placed on its right side. Recursively apply Quick Sort to the left and right sublists. The Power of Partitioning

Partitioning is the heart of Quick Sort. It efficiently rearranges the list based on the chosen pivot:

Iterate through the list starting from the element after the pivot. If the current element is less than the pivot, swap it with the element at the "partitioning index." The partitioning index starts at the first element (excluding the pivot) and keeps track of the boundary between elements less than the pivot and those greater than or equal to it. Increment the partitioning index. Once you reach the end of the list, swap the pivot with the element at the partitioning index. This places the pivot in its rightful position, separating the two sublists

def partition(data, low, high):
 
  pivot = data[high - 1]  # Choose the last element as the pivot
  i = low - 1  # Partitioning index
 
  # Rearrange elements based on the pivot
  for j in range(low, high - 1):
    if data[j] <= pivot:
      i += 1
      data[i], data[j] = data[j], data[i]
 
  data[i + 1], data[high - 1] = data[high - 1], data[i + 1]
  return i + 1  # Return the pivot's final position
 
def quick_sort(data, low, high):
  """
  Sorts a list of data in ascending order using Quick Sort algorithm.
 
  Args:
      data: A list of sortable elements.
      low: Index of the lower bound of the sublist.
      high: Index of the upper bound of the sublist (exclusive).
 
  Returns:
      None (sorts the data in-place).
  """
  if low < high:
    # Partition the list
    pivot_index = partition(data, low, high)
 
    # Recursively sort the left and right sublists
    quick_sort(data, low, pivot_index)
    quick_sort(data, pivot_index + 1, high)
 
# Example usage
unsorted_data = [8, 3, 1, 4, 2]
quick_sort(unsorted_data, 0, len(unsorted_data))  # Sort the entire list
print(f"Unsorted data: {unsorted_data}")
 

This code defines the partition and quick_sort functions. The partition function rearranges the list based on the pivot, while quick_sort recursively calls itself on the left and right sublists after partitioning.

Strengths and Weaknesses of Quick Sort:

Strengths: Extremely efficient for large datasets (average-case time complexity is logarithmic), in-place sorting (modifies the original list). Weaknesses: Performance can deteriorate in the worst case (quadratic time complexity) if the pivot selection is poor, not stable (may change the order of equal elements). Quick Sort offers impressive speed but can be susceptible to the choice of pivot. Understanding average-case and worst-case scenarios is crucial for optimal performance.