Added Heap Sort, Quick Sort and Radix Sort

Aditi-1400 · Aditi-1400 · commit d8e15a3766de · 2020-09-30T22:36:41.000+05:30
diff --git a/python/sorting/Heap Sort.py b/python/sorting/Heap Sort.py
@@ -0,0 +1,42 @@
+# Code for heap sort in Python
+
+
+def heapify(arr, n , i):
+	root = i #root
+
+	l = 2*i+1 #left child
+	r = 2*i+2 #right child
+
+	if(l<n and arr[i] < arr[l]):
+		root = l
+
+	if(r<n and arr[root] < arr[r]):
+		root = r
+
+	if(root!=i):
+		arr[i], arr[root] = arr[root], arr[i]
+
+		heapify(arr, n, root) 
+
+
+
+
+def sort(arr, n):
+	
+	#Building maxheap
+	for i in range(n//2 - 1, -1, -1):
+		heapify(arr, n, i)
+	for i in range(n-1,0,-1):
+		arr[i], arr[0] = arr[0], arr[i]
+		heapify(arr, i , 0)
+
+
+
+
+a = [2,4,15,2,3,7,90]
+n = len(a)
+sort(a,n)
+print("Sorted Array: \n")
+for i in range(n):
+	print(f"{a[i]}", end = " ")
+
diff --git a/python/sorting/Quick Sort.py b/python/sorting/Quick Sort.py
@@ -0,0 +1,32 @@
+# Quick sort implementation in python
+
+
+def partition(arr, low, high):
+	i = low -1
+	pivot = arr[high]
+
+	for j in range(low, high):
+		if(arr[j] < pivot):
+			i = i+1
+			arr[i], arr[j] = arr[j], arr[i]
+
+	arr[i+1],arr[high] = arr[high], arr[i+1]
+	return (i+1)
+
+
+def quicksort(arr, low, high):
+
+	if(low< high):
+		pi = partition(arr, low, high)
+		quicksort(arr, low, pi-1)
+		quicksort(arr, pi, high)
+	
+
+
+
+arr = [10,2,4,7,56,12,18]
+n = len(arr)
+quicksort(arr,0, n-1)
+print("Sorted array: \n")
+for i in range(n):
+	print(f"{arr[i]}", end = ' ')
diff --git a/python/sorting/Radix Sort.py b/python/sorting/Radix Sort.py
@@ -0,0 +1,42 @@
+def sort(arr, exp1): 
+	n = len(arr) 
+
+
+	output = [0] * (n) 
+	count = [0] * (10) 
+
+
+	for i in range(0, n): 
+		index = (arr[i]/exp1) 
+		count[int((index)%10)] += 1
+
+
+	for i in range(1,10): 
+		count[i] += count[i-1] 
+	i = n-1
+	while i>=0: 
+		index = (arr[i]/exp1) 
+		output[ count[ int((index)%10) ] - 1] = arr[i] 
+		count[int((index)%10)] -= 1
+		i -= 1
+	i = 0
+	for i in range(0,len(arr)): 
+		arr[i] = output[i] 
+
+
+
+
+def radixsort(arr):
+	largest = max(arr)
+	exp = 1 # place of digit
+	while (largest/exp)>0:
+		sort(arr, exp)
+		exp *= 10
+
+
+arr = [170, 45, 11, 815, 645, 24, 2, 70]
+n = len(arr)
+radixsort(arr)
+
+for i in range(n):
+	print(f"{arr[i]}", end = " ")
