Sorting
This lesson covers around 20 minutes of video content including:
- Bubble Sort and its Efficiency
- Merge Sort and its Efficiency
- Quick Sort and its Efficiency
Bubble Sort and its Efficiency
Merge Sort and its Efficiency
Quick Sort and its Efficiency
Implementations of these algorithms
Use these implementations in the editor below for syntax highlighting and better understanding.
Bubble Sort
def bubbleSort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n-1):
# range(n) also work but outer loop will repeat one time more than needed.
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
print ("%d" %arr[i])
Merge Sort, a Divide and Conquer Algorithm
Iterative Approach
def mergeSort(a):
current_size = 1
# Outer loop for traversing Each
# sub array of current_size
while current_size < len(a) - 1:
left = 0
# Inner loop for merge call
# in a sub array
# Each complete Iteration sorts
# the iterating sub array
while left < len(a)-1:
# mid index = left index of
# sub array + current sub
# array size - 1
mid = min((left + current_size - 1),(len(a)-1))
# (False result,True result)
# [Condition] Can use current_size
# if 2 * current_size < len(a)-1
# else len(a)-1
right = ((2 * current_size + left - 1,
len(a) - 1)[2 * current_size
+ left - 1 > len(a)-1])
# Merge call for each sub array
merge(a, left, mid, right)
left = left + current_size*2
# Increasing sub array size by
# multiple of 2
current_size = 2 * current_size
# Merge Function
def merge(a, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * n1
R = [0] * n2
for i in range(0, n1):
L[i] = a[l + i]
for i in range(0, n2):
R[i] = a[m + i + 1]
i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] > R[j]:
a[k] = R[j]
j += 1
else:
a[k] = L[i]
i += 1
k += 1
while i < n1:
a[k] = L[i]
i += 1
k += 1
while j < n2:
a[k] = R[j]
j += 1
k += 1
# Driver code
a = [12, 11, 13, 5, 6, 7]
print("Given array is ")
print(a)
mergeSort(a)
print("Sorted array is ")
print(a)
Quick Sort, a Divide and Conquer Algorithm
Iterative Approach
def partition(arr,l,h):
i = ( l - 1 )
x = arr[h]
for j in range(l , h):
if arr[j] <= x:
# increment index of smaller element
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[h] = arr[h],arr[i+1]
return (i+1)
# Function to do Quick sort
# arr[] --> Array to be sorted,
# l --> Starting index,
# h --> Ending index
def quickSortIterative(arr,l,h):
# Create an auxiliary stack
size = h - l + 1
stack = [0] * (size)
# initialize top of stack
top = -1
# push initial values of l and h to stack
top = top + 1
stack[top] = l
top = top + 1
stack[top] = h
# Keep popping from stack while is not empty
while top >= 0:
# Pop h and l
h = stack[top]
top = top - 1
l = stack[top]
top = top - 1
# Set pivot element at its correct position in
# sorted array
p = partition( arr, l, h )
# If there are elements on left side of pivot,
# then push left side to stack
if p-1 > l:
top = top + 1
stack[top] = l
top = top + 1
stack[top] = p - 1
# If there are elements on right side of pivot,
# then push right side to stack
if p+1 < h:
top = top + 1
stack[top] = p + 1
top = top + 1
stack[top] = h
# Driver code to test above
arr = [4, 3, 5, 2, 1, 3, 2, 3]
n = len(arr)
quickSortIterative(arr, 0, n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i])
Source for Implementations of Bubble, Merge, and Quick Sorts - 1, 2, 3.
