The task is to complete the insert() function which is used to implement Insertion Sort. 
Example 1:
Input:
N = 5
arr[] = { 4, 1, 3, 9, 7}
Output:
1 3 4 7 9
Example 2:
Input:
N = 10
arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Output:
1 2 3 4 5 6 7 8 9 10
Your Task: 
You don't have to read input or print anything. Your task is to complete the function insert() and insertionSort() where insert() takes the array, it's size and an index i and insertionSort() uses insert function to sort the array in ascending order using insertion sort algorithm. 
Expected Time Complexity: O(N*N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 1000
1 <= arr[i] <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #Sort the array using insertion sort

class Solution:
    def insert(self, alist, index, n):
        #code here
        
    #Function to sort the list using insertion sort algorithm.    
    def insertionSort(self, alist, n):
        #code here

Solutions:
class Solution:

	def insert(self, alist, index, n):
		x = alist[index]
		j = index - 1
		while j >= 0 and alist[j] > x:
			alist[j + 1] = alist[j]
			j -= 1
		alist[j + 1] = x

	def insertionSort(self, alist, n):
		for i in range(1, n):
			self.insert(arr, i, n)


class Solution:

	def insert(self, alist, index, n):
		j = index
		while j > 0 and alist[j - 1] > alist[j]:
			temp = alist[j]
			alist[j] = alist[j - 1]
			alist[j - 1] = temp
			j -= 1
		return alist

	def insertionSort(self, alist, n):
		for i in range(n):
			alist = self.insert(alist, i, n)
		return alist


class Solution:

	def insertionSort(self, alist, n):
		for i in range(1, len(alist)):
			key = alist[i]
			j = i - 1
			while j >= 0 and alist[j] > key:
				alist[j + 1] = alist[j]
				j -= 1
			alist[j + 1] = key
		return alist


class Solution:

	def insertionSort(self, alist, n):
		for i in range(n):
			tmp = alist[i]
			j = i - 1
			while j >= 0 and alist[j] > tmp:
				alist[j + 1] = alist[j]
				j = j - 1
			alist[j + 1] = tmp


class Solution:

	def insertionSort(self, alist, n):
		for i in range(1, n):
			for j in reversed(range(i)):
				if alist[j] > alist[j + 1]:
					(alist[j], alist[j + 1]) = (alist[j + 1], alist[j])
				else:
					break
		return alist


class Solution:

	def insert(self, alist, index, n):
		pass

	def insertionSort(self, alist, n):
		for i in range(n):
			mini = i
			for j in range(i + 1, n):
				if alist[j] < alist[mini]:
					mini = j
			(alist[mini], alist[i]) = (alist[i], alist[mini])
		return alist


class Solution:

	def insertionSort(self, alist, n):
		alist.sort()
		return alist


class Solution:

	def insert(self, alist, index, n):
		for index in range(n):
			alist.append(alist[index])

	def insertionSort(self, alist, n):
		alist.sort()
		return alist


class Solution:

	def insert(self, alist, index, n):
		if index == n:
			return
		j = index - 1
		key = arr[index]
		while j >= 0 and key <= alist[j]:
			alist[j + 1] = alist[j]
			j -= 1
		alist[j + 1] = key
		self.insert(alist, index + 1, n)

	def insertionSort(self, alist, n):
		self.insert(alist, 1, n)
		return alist


class Solution:

	def insert(self, alist, index, n):
		self.insertionSort(alist, n)

	def insertionSort(self, alist, n):
		for index in range(1, n):
			curr = alist[index]
			pos = index
			while curr < alist[pos - 1] and pos > 0:
				alist[pos] = alist[pos - 1]
				pos = pos - 1
			alist[pos] = curr
		return


class Solution:

	def insert(self, alist, index, n):
		key = alist[index]
		i = index - 1
		while i >= 0 and alist[i] > key:
			alist[i + 1] = alist[i]
			i -= 1
		alist[i + 1] = key

	def insertionSort(self, alist, n):
		for i in range(1, n):
			self.insert(alist, i, n)


class Solution:

	def insert(self, arr, index, n):
		if index > n - 1:
			return
		temp = arr[index]
		j = index - 1
		while j >= 0 and temp < arr[j]:
			arr[j + 1] = arr[j]
			j -= 1
		arr[j + 1] = temp
		self.insert(arr, index + 1, n)

	def insertionSort(self, arr, n):
		self.insert(arr, 1, n)
		return arr


class Solution:

	def insert(self, alist, index, n):
		return alist.sort()

	def insertionSort(self, alist, n):
		return alist.sort()


class Solution:

	def insert(self, arr, index, n):
		s = arr.sort()
		return s

	def insertionSort(self, arr, n):
		k = arr.sort()
		return k


class Solution:

	def insert(self, alist, index, n):
		while index != 0:
			if alist[index] < alist[index - 1]:
				(alist[index], alist[index - 1]) = (alist[index - 1], alist[index])
			else:
				break
			index -= 1

	def insertionSort(self, arr, n):
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				self.insert(arr, i + 1, n)


class Solution:

	def insertionSort(self, arr, n):
		for i in range(n):
			current = arr[i]
			j = i - 1
			while j >= 0 and arr[j] > current:
				arr[j + 1] = arr[j]
				j = j - 1
			arr[j + 1] = current


class Solution:

	def insert(self, alist, index, n):
		pass

	def insertionSort(self, alist, n):
		arr.sort()


class Solution:

	def insertionSort(self, alist, n):
		for i in range(1, n):
			valuetosort = alist[i]
			while alist[i - 1] > valuetosort and i > 0:
				(alist[i], alist[i - 1]) = (alist[i - 1], alist[i])
				i -= 1
		return arr


class Solution:

	def insert(self, l, i, n):
		for j in range(i, 0, -1):
			if l[j] < l[j - 1]:
				(l[j], l[j - 1]) = (l[j - 1], l[j])
			else:
				break

	def insertionSort(self, l, n):
		for i in range(1, n):
			x = self.insert(l, i, n)


class Solution:

	def insertionSort(self, a, n):
		for i in range(1, n):
			x = a[i]
			j = i - 1
			while j >= 0 and a[j + 1] < a[j]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
				j = j - 1


class Solution:

	def insert(self, alist, index, n):
		pass

	def insertionSort(self, alist, n):
		a = alist.sort()
		return a


class Solution:

	def insert(self, alist, index, n):
		return

	def insertionSort(self, alist, n):
		for i in range(1, len(alist)):
			a = i
			while a > 0 and alist[a - 1] > alist[a]:
				(alist[a - 1], alist[a]) = (alist[a], alist[a - 1])
				a -= 1
		return alist


class Solution:

	def insert(self, alist, index, n):
		currentvalue = alist[index]
		position = index
		while position > 0 and alist[position - 1] > currentvalue:
			alist[position] = alist[position - 1]
			position = position - 1
		alist[position] = currentvalue

	def insertionSort(self, alist, n):
		for index in range(1, n):
			self.insert(arr, index, n)


class Solution:

	def insert(self, a, n, i):
		if i == n:
			return
		temp = a[i]
		j = i - 1
		while j >= 0 and a[j] > temp:
			a[j + 1] = a[j]
			j -= 1
		a[j + 1] = temp
		self.insert(a, n, i + 1)

	def insertionSort(self, alist, n):
		self.insert(alist, n, 1)


class Solution:

	def insert(self, alist, i, n):
		while i and alist[i] < alist[i - 1]:
			(alist[i], alist[i - 1]) = (alist[i - 1], alist[i])
			i -= 1

	def insertionSort(self, alist, n):
		if n <= 1:
			return
		for i in range(1, n):
			self.insert(alist, i, n)


class Solution:

	def insert(self, alist, index, n):
		current_value = alist[index]
		while index > 0 and alist[index - 1] > current_value:
			alist[index] = alist[index - 1]
			index -= 1
		alist[index] = current_value

	def insertionSort(self, alist, n):
		for index in range(1, n):
			self.insert(alist, index, n)


class Solution:

	def insertionSort(self, alist, n):
		if n <= 1:
			return
		Solution().insertionSort(alist, n - 1)
		last = arr[n - 1]
		j = n - 2
		while j >= 0 and alist[j] > last:
			alist[j + 1] = alist[j]
			j -= 1
		alist[j + 1] = last


class Solution:

	def insert(self, alist, index, n):
		for i in range(index):
			if alist[i] > alist[index]:
				(alist[i], alist[index]) = (alist[index], alist[i])

	def insertionSort(self, alist, n):
		for i in range(1, n):
			self.insert(alist, i, n)


class Solution:

	def insert(self, alist, index, n):
		pass

	def insertionSort(self, arr, n):
		n = len(arr)
		for i in range(n):
			index = i
			swap = 0
			while index > 0 and arr[index] <= arr[index - 1]:
				(arr[index], arr[index - 1]) = (arr[index - 1], arr[index])
				index -= 1


class Solution:

	def insertionSort(self, alist, n):
		for i in range(1, n):
			prev_range = range(i - 1, -1, -1)
			val = alist[i]
			for j in prev_range:
				if val > alist[j]:
					alist[j + 1] = val
					break
				alist[j + 1] = alist[j]
			else:
				alist[j] = val


class Solution:

	def insertionSort(self, a, n):
		for i in range(1, n):
			k = a[i]
			j = i - 1
			while j >= 0 and k < a[j]:
				a[j + 1] = a[j]
				j = j - 1
			a[j + 1] = k
		return a


def insert(arr, n):
	for i in range(n, 0, -1):
		if arr[i - 1] > arr[i]:
			(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
		else:
			return

class Solution:

	def insertionSort(self, arr, n):
		for i in range(1, n):
			if arr[i - 1] > arr[i]:
				insert(arr, i)
		return arr