Understanding Divide and Conquer algorithms using Quicksort as an example.

So many algorithms and solutions derive from Quicksort. We try and cover a few.Please read on.

This is part of a post in 2 series.
This one is explores partitioning and the next one on the coming sunday will about quicksort.
Contents

1. Divide and Conquer Algorithms. basic theory, its efficiency and more.

2. Partitioning an array and problems where it can be used.

3. Quicksort using Recursion.

4. Quicksort using stack.

5. Analysis of Quicksort.

6. Solving more problems using the techniques developed here.

Divide and Conquer

Imagine a problem whose time complexity is quadratic written as O(n2) order of n-squared where n is the size of the input. In simple terms this will mean that a problem of size 10 will require 100 time units. What happens if we could divide it into 2 independent parts of 5 and 5 and solve it by the same method it would require 585=25 + 5*5=25 = 50 steps + the steps required in dividing the 2 problems. If we can continue the process further by subdividing the steps required would be even lesser.

Consider this figure where we divide an array of size 8 repeatedly till every problem is reduced to size 1.

Points to note here.

The number of elements at every level are halved. So,if the total no of elements are N then the first level will have N/2 elements, then N/4, N/8 and so on. So, if the height is h then no of elements will be N/2^h (2^h is 2 to the power h). This will go on till N/2^h becomes 1. Therefore N/2^h=1, h=log(N)base. At every level the total number of elements is N. 8, 4+4=8,2+2+2+2=8 and so on.
So, time complexity is Nlog(N). More on this later on in the post.

Let us get coding now. Let us define a list first.

a=[5,6,4,9,8,2,3,7]

The zeroth element 5 is our pivot about which we will partition. All elements less than 5 will be to the left and >=5 to the right.

Where will 5 end up? If there are 3 numbers less than 5 then it will be positioned after 3 elements.

Now, the pivot 5 is in its final position. All elements to the left of 5 should be less than 5 and all elements to the right should be >=5. But, they are not. How do we resolve this issue?

How, do we fix this?
Loop from the left and stop at the first element that is greater than pivot(5). Then loop from the right and stop at the first element less than 5. Interchange the two and continue.

We will be done finally.

Here is the code so far alongwith the output.

a=[5,6,4,9,8,2,3,7]
print("original array ",a)
pivot=a[0]
count=0
for x in a:
  if x<pivot:
    count+=1
print("Count ",count)
a[0],a[count]=a[count],a[0]
print("Array with pivot in proper place",a)

left,right=0,len(a)-1
while True:
  while left<right and a[left]<pivot:
    left+=1
  if left >=right:
   break
  while left<right and a[right]>=pivot:
    right-=1
  if left>=right:
      break
  a[left],a[right]=a[right],a[left]
  print("list after an exchange",a)
print("list after full partition",a)

This requires 2 loops. One loop to find the number of elements less than the pivot and place the pivot in the final position and then a while loop that adjusts out of position elements.

Can we do this using one loop only?

Let us try. Start with the original array.

The pivot is 5 and it has to be placed in its final position. What do we know about the final position of the pivot?
We know that its initial value will be 0 and it will increase by 1 eveytime we find an element less than the pivot.

Here is the code for it.

The array is

a=[5,6,4,9,8,2,3,7]

finalposition=0
pivot=a[0]
n=len(a)
for i in range(n):
  if a[i]<pivot:
    finalposition+=1
print(finalposition)

The output as expected is 3 because 2,3 and 4 are less than 5.

When will the final position be incremented for the first time. This will happen when the value being accessed is 4 and the index is 2.

This is the position we are at.

finalposition=0
pivot=a[0]
n=len(a)
for i in range(n):
  if a[i]<pivot:
    finalposition+=1

finalposition has been increased by 1 and it is 1 now. This means that we have found an element which is less than the pivot 5 and so we have 2 elements <=5 now.

So, if partitioning is being done correctly we should have elements <=5 at the positions 0 and 1 now. At the moment we have

Let us swap the element at fp=1 with the element at i=2

Now, we have elements less than equal to pivot in the range 0 to fp. The next element less than 5 is at index 5.

Increase finalposition by 1.

Swap the elements at positions fp and i.

We have elements <=5 within the range 0 to fp now. One more element less than 5 is at position 6, we increase finalposition once again and swap with i.

The array after the end of the loop is.

finalposition=0
pivot=a[0]
n=len(a)
for i in range(n):
  if a[i]<pivot:
    finalposition+=1
    a[i],a[finalposition]=a[finalposition],a[i]
print(a)

Output

As a last step let us swap the pivot at position 0 with the element 3 at position=finalposition =3.

After interchanging

The complete code and output.

finalposition=0
pivot=a[0]
n=len(a)
for i in range(n):
  if a[i]<pivot:
    finalposition+=1
    a[i],a[finalposition]=a[finalposition],a[i]
a[0],a[finalposition]=a[finalposition],a[0]
print(a)

Output

The array has been partitioned properly.

Our partitioning program is complete and it has many uses. Let us explore a few.

Program to partition an array into even and odd parts.

a=[5,6,4,9,8,2,3,7]
print("original array ",a)
left,right=0,len(a)-1
while True:
  while left<right and a[left]%2==0:
    left+=1
  if left >=right:
   break
  while left<right and a[right]%2!=0:
    right-=1
  if left>=right:
      break
  a[left],a[right]=a[right],a[left]
  print("list after an exchange",a)
print("list after full partition",a)

Output

Program to partition an array into elements less than 0 -ve and greater than equal to 0 +ve.

a=[-5,6,4,9,-8,2,3,-7]
print("original array ",a)
left,right=0,len(a)-1
while True:
  while left<right and a[left]<0:
    left+=1
  if left >=right:
   break
  while left<right and a[right]>=0:
    right-=1
  if left>=right:
      break
  a[left],a[right]=a[right],a[left]
  print("list after an exchange",a)
print("list after full partition",a)

Output

Program to find nth smallest element in an array. Partition the array repeatedly till you find a finalposition=n.

n=4
n-=1 #Adjusted for normal positioning of 1 and array indexing of 0
a=[5,6,4,9,8,2,3,7]
print("original array ",a)
left=0
right=len(a)-1
while True:
  a[left],a[n]=a[n],a[left]
  finalposition=left
  pivot=a[left]
  for i in range(left+1,right+1):
    if a[i]<pivot:
      finalposition+=1
      a[i],a[finalposition]=a[finalposition],a[i]
  if finalposition==n:
    result=pivot
    break
  a[left],a[finalposition]=a[finalposition],a[left]
  if n<finalposition:
    right=finalposition-1
  else:
    left=finalposition+1

print("Transformed array ",a)
print(n+1 ," smallest value is ", pivot)

Output

For n=3

Here is a program that partitions an array into buckets.

buckets = [3, 6, 9]

The partitions will be
[less than 3,],[>=3 to <6],[>=6 to <9],[>=9]

a = [5, 6, 4, 9, 8, 2, 3, -7]
buckets = [3, 6, 9]
partitions = [0]
left = 0
print("original array ", a)
for i in buckets:
    right = len(a) - 1
    pivot = i
    while True:
        while left < right and a[left] < pivot:
            left += 1
        if left >= right:
            break
        while left < right and a[right] >= pivot:
            right -= 1
        if left >= right:
            break
        a[left], a[right] = a[right], a[left]
    partitions.append(left)

partitions.append(len(a))
print("partitions ", partitions)
print("partitioned array ", a)
for i in range(1, len(partitions)):
    start = partitions[i - 1]
    end = partitions[i]

    print(i, ":", a[start:end])

# print("Elements less than ",buckets[0], " are ",a[partitions[0]:partitions[1] +1])
# print("Elements less than ",buckets[1], " are ",a[partitions[0]:partitions[2] +1])
# print("Partitions", partitions)

Output

The code is available at.

We analyze Quicksort next week.

Please give your feedback.