Divide and conquer

Divide and conquer

• divide and conquer is a recursive problem solving paradigm that breaks down a complex problem into smaller manageable ones and each one is solved independently and their solutions are combined to derive the solution to the original problem.

1. Base case:
   • Identifying a base case that can be solved without further decomposition and define a criteria to define this case.
2. Recursive decomposition:
   • determine how to breakdown the problem into smaller similar subproblems until reaching the base case.
3. Solve the base case
   • Complete the smallest possible operation directly.
4. Combine subproblems
   • now logically recombine the data to complete your solution

Quicksort

Quicksort is an efficient, in-place, divide and conquer sorting algorithm. It is widely used due to its average-case time complexity of $𝑂(𝑛log⁡𝑛)$ and its ability to sort large datasets efficiently. The key steps involved in QuickSort are:

1. Choose a Pivot:

   • Select a pivot element from the array. The pivot can be any element, but commonly the first, last, or a random element is chosen.

2. Partition the Array:

   • Rearrange the elements such that:
     • Elements less than the pivot are moved to its left.
     • Elements greater than the pivot are moved to its right.
   • This process places the pivot in its correct sorted position.

3. Recursively Apply QuickSort:

   • Apply QuickSort to the subarray on the left of the pivot.
   • Apply QuickSort to the subarray on the right of the pivot.

4. Base Case:

   • The recursion ends when the subarray has one or zero elements, which means it is already sorted.

# quick sort better named pivot sort:

# uses 2 functions main recursive one lets call it quick sort and a second one to comapre and swap values inplace call partition.


def quicksort (list ,low = 0, high = None ):
	if high == None:
		high = len(list) - 1
	if high>low:
		pivot = partition(list,low,high)
		quicksort(list,low,pivot-1)
		quicksort(list,pivot+1,high)
	return list

def partition (list ,left, right):
	i = left
	j = right
	pivot = list[left]
	while i < j:
		while i < right and list[i] < pivot:
			i+=1
		while j > left and list[j] > pivot:
			j-=1
		if i < j:
			list[i],list[j] = list[j],list[i]
	if list[j] < pivot:
		list[j],list[left] = list[left],list[j]
	return i

Explanation of the Code

• Quicksort Function:

  • Checks if the high parameter is None and initialises it.
  • If low < high, it calls the partition function to find the pivot index.
  • Recursively sorts the subarrays to the left and right of the pivot.

• Partition Function: - Chooses the first element as the pivot. - Uses two indices, i starting from left + 1 and j from right. - Moves i rightwards as long as elements are less than or equal to the pivot. - Moves j leftwards as long as elements are greater than or equal to the pivot. - Swaps elements at i and j if i is still less than or equal to j. - When i and j cross, the loop exits, and the pivot is swapped into its correct position. - Returns the index of the pivot.

  ** Divide and Conquer** a recursive problem-solving paradigm that breaks down a complex problem into smaller, manageable subproblems, solves each independently, and combines their solutions to solve the original problem. The key steps are:

  • Base Case: Identify a simple case that can be solved directly.
  • Recursive Decomposition: Break down the problem into smaller, similar subproblems until the base case is reached.
  • Solve the Base Case: Solve the smallest subproblems directly.
  • Combine Subproblems: Combine the solutions of the subproblems to form the solution to the original problem. Quicksort Quicksort is an efficient, in-place, divide and conquer sorting algorithm with an average-case time complexity of $𝑂(𝑛log⁡𝑛)$. The steps involved are:

  1. Choose a Pivot: Select a pivot element from the array.
  2. Partition: Rearrange elements so those less than the pivot are on its left, and those greater are on its right. The pivot is then in its correct position.
  3. Recursively Apply: Apply QuickSort to the subarrays on the left and right of the pivot.
  4. Base Case: Recursion stops when subarrays have one or zero elements, meaning they are already sorted.