DEV Community: Bhav Kushwaha

QuickSort - Time Analysis (Part2)

Bhav Kushwaha — Fri, 29 Sep 2023 14:26:16 +0000

Stating the Fundamentals

1) Suppose we have a simple function to print every item in a list:

def print_items(list):
 for items in list:
  print item

This function goes through every item in the list and prints out.

2) Now consider the same function but with a 1 second sleep() associated with every iteration in it.

from time import sleep
def print_items2(list):
 for items in list:
  sleep(1)
  print item

The Key points:

Both functions loop through the list once, so theoriticaly they both have O(n) time complexity.
But the print_items() is evidently faster than the latter since it doesn't contains the sleep function and is executed faster.
So even though both functions are the same speed in Big O notation like O(n), print_items is practically faster.

From the above example we gather:

When we write Big O notation like O(n), it really means this:

c is some fixed amount of time that your algorithm takes, called constant.

For Example, it might be 10 ms for print_items and 1 sec for print_items2.

Example of Binary Search vs Simple Search

Suppose both the algorithms had the following constants:

You might assume Simple Search is way faster due to a very low constant value than Binary Search.

But now considering a list of 4 Billion Elements!

NOTE : Here the constant c doesn't get considered and Binary Search is proved to be more faster.

QuickSort vs MergeSort Case

In this case the constant associated with the time complexity plays an important role is determining the better performing Sorting Algorithm.

Quicksort has a smaller constant than Mergesort!
Sof if they're both O(n) time, then quicksort is faster!
And Quicksort is faster in practice too, since it hits the average case way more often than the worst case.

Different Cases of Quicksort

Worst Case

The performance of quicksort heavily depends on the pivot you choose.
Suppose you always choose the first element as the pivot, and you call a quicksort on an array that is already sorted.

Here, quicksort doesn't check whether the array is sorted or not, it will try to sort it again.
Stack Size in Worst Case: O(n)

Best Case

Now instrad, suppose you always picked the middle element as the pivot. Look at the call stack now:

It's so short! Because you divided the array in half everytime, you don't need to make as many recursive calls. You hit the base case sooner and the call stack is much shorter.
Stack Size in Best Case: O(logn)

Average Case

Now take any element as the pivot and the rest of elements are divided in sub-arrays. You will get the result exactly same as the best case.
Stack Size in Average Case: O(logn)

Something about the Call Stack at every level

The first operation takes O(n) time since you touched all 8 elements on this level of stack. But actually you touch O(n) elements on every level of the call stack.

Even if you partition the array differently, you still are touching O(n) elements everytime.

So each level takes O(n) time to complete.

Conclusion

We conclude with the above findings that the Height of Call Stack is O(logn) and each level takes O(n) time.

The entire Quicksort Algorithm will take: O(n) * O(nlogn) = O(nlogn)

The Time Complexity of the Best-Case & Average-Case of Quicksort.

In the Worst-Case, there are O(n) levels, so the algorithm takes O(n) * O(n) = O(n^2)

NOTE: If you always choose a random element in the array as the pivot, quicksort will complete in O(nlogn) time on average.

Quicksort is one of the fastest sorting algorithms out there!

Quicksort (Grokking Algorithms)

Bhav Kushwaha — Fri, 29 Sep 2023 07:02:48 +0000

Quicksort is a sorting algorithm which is frequently used in real life.

Let's explore different senarios where we can implement Quicksort:-

Array Containing 0 or 1 Element

Empty arrays and single element array will not need to be sorted. The base case will be the result for them.

Array Containing 2 Elements

An array containing two Elements is also easy to sort.

Array Containing 3 Elements

In order to sort an array containing three elements, we need to break it down to the base case using the Divide & Conquer approach.

First pickup an element from the array, called the pivot.

(Will discuss how to pickup a good pivot later, for now lets take the first element as pivot.)

Now find the elements smaller than the pivot and the elements larger than the pivot.

This is called Partioning. You have :
1) A sub-array of all the numbers less than the pivot
2) The pivot
3) A sub-array of all the numbers more than the pivot

The two two sub-arrays obtained are not neccessarily sorted. Therefore, we come come across 2 cases:

1) If the sub-arrays are sorted then we can combine the whole thing

left array + pivot + right array = Sorted Array

2) If the sub-arrays are not sorted then we have to sort them.

We can do that by applying quicksort on the sub-arrays (since we know the results of sorting an array containing 0 or 1 elements or 2 elements array).

quicksort([15, 10]) + [33] + quicksort([])

> [10, 15, 33]

Similary, we can choose any element of the array as pivot and apply the above steps to obtain a sorted array.

Array Containing 4 Elements

Suppose we are given an array

We choose 33 as the pivot element.

The left sub-array has 3 elements. We had already seen how to sort an array of three elements: call quicksort on it recursively.

Therefore, we can now easily repeat the steps learned above to sort the 4 elements array.

Sorting an array of 5 elements (Different Pivots)

Given Array :

Different Pivot Elements :

Notice: all the sub-arrays of any pivot lies between 0-4 elements, and we can easily sort them as seen in the above examples.

Example 1)

Example 2)

The Code for Quicksort

def quicksort(array):

 if len(array) < 2:
  return array
  # Base Case: arrays with 0 or 1 elements

 else:
  pivot = array[0]
  # Recursive Case

  less = [ i for i in array [1:] if i <= pivot] 
  # Sub-array to the left of the pivot

  greater = [ i for i in array [1:] if i > pivot] 
  # Sub-array to the right of the pivot

  return quicksort(less) + [pivot] + quicksort(greater)


print quicksort([10, 5, 2, 3])

Divide & Conquer (Grokking Algorithms)

Bhav Kushwaha — Tue, 29 Aug 2023 14:25:04 +0000

In this article we will use 2 Examples to explain the concept of Divide & Conquer.

The First Example will be a visual one and the latter one will be a code one.

EXAMPLE 1

Suppose you are a farmer with a plot of land. You want to divide this farms evenly into square plots. You want the plots to be as big as possible.

The following Constraints are present:-

Here to solve the farmer's problem, we will use Divide & Conquer Strategy!

The Divide & Conquer Strategy consists of two cases:-

Base Case : The simplest possible case!
Recursive Case : Divid eor decrease your problem until it becomes the Base Case.

Now solving the Farmer's problem:

Let's start by marking out the bigest boxes you can use.

You can fit two 640x640 boxes in there and some land is still left to be divided!

Now, apply the same algorithm to the remaining land!

The biggest box we can create is 400 x 400 m with 400 x 240 remaining area.

Now mark a box to get an even smaller segment.

Going for an even smaller box!

Hey Look! we encountered the Base Case !

So for the original farm, the biggest plot size you can use is 80 x 80 m.

EXAMPLE 2

You are given an array of numbers. You have to add all the numbers and return the total.

It's pretty easy to do it with a loop:

def sum(arr):
 total = 0
 for x in arr:
  total += x
 return total

But the challenge is to do it using Recursion!

Follow these steps to solve the problem:-

1 ) Figure out the Base Case

Think about the simplest case. Here, if we get an array with 0 or 1 element then thats pretty easy to sum up.

2 ) We need to move more closer to an empty array wit hevery recursive call.

3 ) Now the Sum Function Works :-

It's Principal :

Sum Function in Action and Recursion taking place :

Tip: When we are writing a recursive function involving an array, the base case is often an empty array with one element.

Chapter 3 : Recursion (Grokking Algorithms)

Bhav Kushwaha — Wed, 26 Jul 2023 05:33:47 +0000

Topics covered in Chapter 3 : Recursion

What is Recursion?
Base Case & Recursive Case
The Stack
Call Stack
The Call Stack with Recursion

What is Recursion?

It is Explained using an Example of Grandma's Boxes & Key.

You want to open your Grandma's suitcase but the key to it is in this Box.
But this box contains more boxes inside those boxes. And the key is in a box somewhere.
Here we can use 2 Algorithms to find the key:

Using Loops
Using Recursion

Important Points to note:

There is no 100% guaranteed performance benefit of using recursion, infact sometimes loops perform better.

Base Case & Recursive Case

Every Recursive Function has two parts:-

Base Case

Here, the function doesn't call itself and thus this case prevents a chance of infinite loop.

Recursive Case

Here, the function calls itself again.

The Stack

The best example to explain a stack is a Todo-List.
It enables two features : 1. Push() & 2. Pop()

The Call Stack

Our computer uses a stack internally called the Call Stack.

Example:

def greet(name):
    print "hello, " + name + "!"
    greet2(name)
    print "getting ready to say bye..."
    bye()

This function calls 2 other functions:

def greet2(name):
    print "how are you, " + name + "?"

def bye():
    print "ok bye!"

Visually the above code is implemented:

Explaination:

Firstly Greet Function is called
Secondly Greet2 is called
Greet2 is executed and poped
Bye Function is called
Bye is executed and poped
In the end, Greet is returned too as there's nothing else to be done.

The Call Stack with Recursion

Explained by an Example - Factorial of a Number

The Code for Factorial :-

def fact(x):
 if x==1:
  return 1
 else:
  return x * fact(x-1)

NOTE:

Using Stack is convenient but there's a cost; saving all that info can take up a lot of memory. Your Stack becomes too tall!
It can be solved using 1. Loops instead or 2. Tail Recursion
Suppose we write a recursive function that runs forever, then the program will run out of space & it will exit with a Stack-Overflow Error.