a = int(input('Enter your first number:'))
b = int(input('Enter your first number:'))
if a >= b:
x = a
y = b
else:
x = b
y = a
while y!=0:
r = y
y = x%y
x = r
print(x)
def gcd(a,b):
if b==0:
return a
elif a < b:
return gcd(b,a)
else:
return gcd(a-b, b)
def gcd(a,b):
if b==0:
return a
else:
return gcd(b, a % b)
def fib(n)
if n==0 or n==1:
return 1
else:
return fib(n-1)+fib(n-2)
import itertools
for j in itertools.permutations([2,5,6]):
print(j)
def recursion_permutation(list, first, last):
if first >= last:
print(list)
for i in range(first, last):
list[i], list[first] = list[first], list[i]
recursion_permutation(list, first+1, last)
list[i], list[first] = list[first], list[i]
x=[1,2,3,4]
recursion_permutation(x,0,len(x))
def moveTower(height, fromPole, toPole, withPole):
if height>=1:
moveTower(height-1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
moveTower(height-1,withPole,toPole,fromPole)
def moveDisk(fp,tp):
print("moving disk from %s to %s\n" %(fp,tp))
def bubble_sort(a_list):
for pass_num in range(len(a_list) - 1, 0, -1):
for i in range(pass_num):
if a_list[i] > a_list[i + 1]:
temp = a_list[i]
a_list[i] = a_list[i + 1]
a_list[i + 1] = temp
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(a_list)
print(a_list)
Suppose you have a bunch of music on your computer. For each artist, you have a play count.
One way is to go through the list and find the most-played artist. Add that artist to a new list.
To find the artist with the highest play count, you have to check each item in the list. This takes $O(n)$ time, as you just saw. So you have an operation that takes $O(n)$ time, and you have to do that n times:
This takes $O(n × n)$ time or $O(n^2)$ time.
def selection_sort(a_list):
for fill_slot in range(len(a_list) - 1, 0, -1):
pos_of_max = 0
for location in range(1, fill_slot + 1):
if a_list[location] > a_list[pos_of_max]:
pos_of_max = location
temp = a_list[fill_slot]
a_list[fill_slot] = a_list[pos_of_max]
a_list[pos_of_max] = temp
def insertion_sort(a_list):
for index in range(1, len(a_list)):
current_value = a_list[index]
position = index
while position > 0 and a_list[position - 1] > current_value:
a_list[position] = a_list[position - 1]
position = position - 1
a_list[position] = current_value
def merge_sort(a_list):
print("Splitting ", a_list)
if len(a_list) > 1:
mid = len(a_list) // 2
left_half = a_list[:mid]
right_half = a_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = 0
j = 0
k = 0
#continue
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
a_list[k] = left_half[i]
i = i + 1
else:
a_list[k] = right_half[j]
j = j + 1
k = k + 1
while i < len(left_half):
a_list[k] = left_half[i]
i = i + 1
k = k + 1
while j < len(right_half):
a_list[k] = right_half[j]
j = j + 1
k = k + 1
print("Merging ", a_list)
Base case
An array with two elements is pretty easy to sort, too.
What about an array of three elements?
We use D&C to solve this problem. Let's pick a pivot at first, say, 33.
This is called partitioning. Now you have:
A sub-array of all the numbers less than the pivot
The pivot
A sub-array of all the numbers greater than the pivot
If the sub-arrays are sorted, then you can combine the whole thing like this—left array + pivot + right array—and you get a sorted array.
Suppose you have this array of five elements.
For example, suppose you pick 3 as the pivot. You call quicksort on the sub-arrays.
def quick_sort(a_list):
quick_sort_helper(a_list, 0, len(a_list) - 1)
def quick_sort_helper(a_list, first, last):
if first < last:
split_point = partition(a_list, first, last)
quick_sort_helper(a_list, first, split_point - 1)
quick_sort_helper(a_list, split_point + 1, last)
#continue
def partition(a_list, first, last):
pivot_value = a_list[first]
left_mark = first + 1
right_mark = last
done = False
while not done:
while left_mark <= right_mark and a_list[left_mark] <= pivot_value:
left_mark = left_mark + 1
while left_mark <= right_mark and a_list[right_mark] >= pivot_value:
right_mark = right_mark - 1
#continue
if right_mark < left_mark:
done = True
else:
temp = a_list[left_mark]
a_list[left_mark] = a_list[right_mark]
a_list[right_mark] = temp
temp = a_list[first]
a_list[first] = a_list[right_mark]
a_list[right_mark] = temp
return right_mark
a_list=[54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(a_list)
print(a_list)
Quicksort is unique because its speed depends on the pivot you choose.
Actually, the big O of the quick sort algorithm depends on the pivot you pick.
In the best case, the big O of quick sort is $O(nlogn)$. However, in the worst case, the big O of it turns to be $O(n^2)$.
Why?
Worst Case
Best Case
The average case is the best case, if you pick pivot randomly.