LAB_2

Assignment Number: 2
NAME: Md Muaz Sayyed ROLLNO: 60

CLASS: TY-IT-A BATCH: 3
___________________________________________________________________
Problem Statement:
1. Quick sort analysis code
2. Make a table of n and execution time and graph of it.
3. Determine time complexity of quick sort using substitution approach for best
case and worst case.
Answer:
QUICKSORT (array A, start, end)

{
if (start < end)
{
p = partition(A, start, end)
QUICKSORT (A, start, p - 1)
QUICKSORT (A, p + 1, end)
}
}
Code:
import time
import matplotlib.pyplot as plt
import numpy as np
def partition(arr, low, high):

pivot = arr[high]
start = low + 1
end = high
while start < end:

while start <= end and arr[start] <= pivot:
start += 1
while start <= end and arr[end] > pivot:
end -= 1
if start <= end:
arr[start], arr[end] = arr[end], arr[start]
else:
break
arr[low], arr[end] = arr[end], arr[low]

return end
def quick_sort(arr, low, high):

if low < high:
pivot_index = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)

quick_sort(arr, pivot_index + 1, high)
def generate_quick_sort_plot(start_n, end_n):

data = []
print("n\tExecution Time (seconds)")

print("---------------------------")
for n in range(start_n, end_n):

arr = np.random.rand(n)
start_time = time.perf_counter()
quick_sort(arr, 0, len(arr) - 1)
end_time = time.perf_counter()
execution_time = (end_time - start_time)
data.append((n, execution_time))
print(f"{n}\t {execution_time:.6f}")
# Generate plot
n_values, time_values = zip(*data)
plt.figure(figsize=(7, 5))
# Plot for n vs execution time

plt.plot(n_values, time_values, label='Execution Time')
plt.title('n vs Execution Time (Quick Sort )')
plt.xlabel('n')
plt.ylabel('Execution Time (seconds)')
plt.legend()
plt.show()
# Set the range for n

start_n_quick_sort = 1000
end_n_quick_sort = 10000
# Generate plot for Quick Sort with Provided Partition

generate_quick_sort_plot(start_n_quick_sort, end_n_quick_sort)
Output:
Randomised Quick Sort
import time
import matplotlib.pyplot as plt
import numpy as np
import random
def partition(arr, low, high):

pivot = arr[random.randint(low, high)]
start = low + 1
end = high
while start < end:

while start <= end and arr[start] <= pivot:
start += 1
while start <= end and arr[end] > pivot:
end -= 1
if start <= end:
arr[start], arr[end] = arr[end], arr[start]
else:
break
arr[low], arr[end] = arr[end], arr[low]

return end
def quick_sort(arr, low, high):

if low < high:
pivot_index = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)

quick_sort(arr, pivot_index + 1, high)
def generate_quick_sort_plot(start_n, end_n):

data = []
print("n\tExecution Time (seconds)")

print("---------------------------")
for n in range(start_n, end_n):

arr = np.random.rand(n)
start_time = time.perf_counter()
quick_sort(arr, 0, len(arr) - 1)
end_time = time.perf_counter()
execution_time = (end_time - start_time)
data.append((n, execution_time))
print(f"{n}\t {execution_time:.6f}")
# Generate plot
n_values, time_values = zip(*data)
plt.figure(figsize=(7, 5))
# Plot for n vs execution time

plt.plot(n_values, time_values, label='Execution Time')
plt.title('n vs Execution Time (Quick Sort )')
plt.xlabel('n')
plt.ylabel('Execution Time (seconds)')
plt.legend()
plt.show()
# Set the range for n

start_n_quick_sort = 1000
end_n_quick_sort = 10000
# Generate plot for Quick Sort with Provided Partition

generate_quick_sort_plot(start_n_quick_sort, end_n_quick_sort)
Output:
Time Complexity for best case and worst case:
Best case:
The best case occurs when we select the pivot as the mean.
Quick Sort ()
{
P =partition();-----n
n
QuickSort(left);-----------
2
n
QuickSort(right);--------
2
}
{
1,∧n=1
T (n)=
2T
n
2()
+ n ,∧n>1
Here
2T ( n2 ) signifies that the a problemof ¿ is divided into 2 problems
n
of ¿( ¿ )each .n: the number of
2
comparisons required to identify the exact position of itself (every element)
Using Substitution Method:
T ( n )=2 T ()
n
2
+n n>1−−(1)T ( n )=2 2 T
n
[ ( ) ]
n
+ + n−−(2)
2∗2 2
Substitue eq ( 2 ) ∈eq(1)
T ( n )=4 T ( n4 )+2 nT ( n )=4 [ 2 T ( n8 )+ n4 ]+2 n−−(3)T ( n )=8 T ( n8 )+3 n

Let 2k =n ,thus k =log n
k
T ( n )=2 +T
( 2n )+kn
k
Maximum value of k can be log n
T ( n )=n+ nlognT ( n )=Ο(nlogn )
Therefore, Best case is Ο ( nlogn ) .
Worst Case:
The worst case will occur when the array gets divided into two parts, one part
consisting of N-1 elements and the other and so on.
Quick Sort ()
{
P =partition();-----n
QuickSort(left);----------- (n-1)
QuickSort(right);----0
}
T ( n )=T ( n−1 ) +n T (n-1) is time taken by remaining element except for pivot element.
n: the number of comparisons required to identify the exact position of itself (every
element)
Using Substitution Method

T ( n )=T ( n−1 ) +n−−( 1 )T ( n−1 )=T ( n−2 )+ n−1−−( 2 )Substitute equation 2 in equation 1
T ( n )=T ( n−2 ) +n−1+nT ( n )=T ( n−2 ) +2 n−1T ( n )=( T ( ( n−2 )−1 ) +n−3 ) +2 (n−3)−1
T ( n )=T ( n−3 ) +3 n−2−1T ( n−4 ) + 4 n−3−2−1T ( n−k )+ kn− ( k−1 ) −… ..2 k−k
k ( k + 1) n ( n+1 ) 2 n 2 n
T ( n−k )+ kn− Let k =nT ( 0 )+ n2− n − − T ( n )=Ο(n 2)
2 2 2 2
Therefore, Worst case is Ο(n 2).

LAB_2

Uploaded by

Copyright:

Available Formats

LAB_2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

LAB_2

Uploaded by

Copyright:

Available Formats

Assignment Number: 2

NAME: Md Muaz Sayyed ROLLNO: 60

QUICKSORT (array A, start, end)

def partition(arr, low, high):

while start < end:

arr[low], arr[end] = arr[end], arr[low]

def quick_sort(arr, low, high):

quick_sort(arr, low, pivot_index - 1)

def generate_quick_sort_plot(start_n, end_n):

print("n\tExecution Time (seconds)")

for n in range(start_n, end_n):

execution_time = (end_time - start_time)

# Plot for n vs execution time

# Set the range for n

# Generate plot for Quick Sort with Provided Partition

def partition(arr, low, high):

while start < end:

arr[low], arr[end] = arr[end], arr[low]

def quick_sort(arr, low, high):

quick_sort(arr, low, pivot_index - 1)

def generate_quick_sort_plot(start_n, end_n):

print("n\tExecution Time (seconds)")

for n in range(start_n, end_n):

execution_time = (end_time - start_time)

# Plot for n vs execution time

# Set the range for n

# Generate plot for Quick Sort with Provided Partition

Using Substitution Method:

T ( n )=4 T ( n4 )+2 nT ( n )=4 [ 2 T ( n8 )+ n4 ]+2 n−−(3)T ( n )=8 T ( n8 )+3 n

Maximum value of k can be log n

T ( n )=n+ nlognT ( n )=Ο(nlogn )

Therefore, Best case is Ο ( nlogn ) .

Using Substitution Method

Therefore, Worst case is Ο(n 2).

You might also like