Given an unsorted array of size N, use selection sort to sort arr[] in increasing order.
Example 1:
Input:
N = 5
arr[] = {4, 1, 3, 9, 7}
Output:
1 3 4 7 9
Explanation:
Maintain sorted (in bold) and unsorted subarrays.
Select 1. Array becomes 1 4 3 9 7.
Select 3. Array becomes 1 3 4 9 7.
Select 4. Array becomes 1 3 4 9 7.
Select 7. Array becomes 1 3 4 7 9.
Select 9. Array becomes 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 dont need to read input or print anything. Complete the functions select() and selectionSort() ,where select() takes arr[] and starting point of unsorted array i as input parameters and returns the selected element for each iteration in selection sort, and selectionSort() takes the array and it's size and sorts the array.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^3

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #User function Template for python3

class Solution: 
    def select(self, arr, i):
        # code here 
    
    def selectionSort(self, arr,n):
        #code here

Solutions:
class Solution:

	def selectionSort(self, arr, n):
		temp = 0
		for x in range(0, len(arr) - 1):
			min_index = x
			for j in range(x + 1, n):
				if arr[j] < arr[min_index]:
					min_index = j
			(arr[x], arr[min_index]) = (arr[min_index], arr[x])
		return arr


class Solution:

	def select(self, arr, i):
		max = i
		for j in range(0, i):
			if arr[max] < arr[j]:
				max = j
		return max

	def swap(self, ind1, ind2, arr):
		(arr[ind1], arr[ind2]) = (arr[ind2], arr[ind1])

	def selectionSort(self, arr, n):
		for i in range(0, n):
			last = n - i - 1
			max_ind = self.select(arr, last)
			self.swap(last, max_ind, arr)
		return arr


class Solution:

	def select(self, arr, i):
		pass

	def selectionSort(self, arr, n):
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] > arr[j]:
					(arr[i], arr[j]) = (arr[j], arr[i])


class Solution:

	def select(self, arr, i):
		min_id = i
		for j in range(i + 1, len(arr)):
			if arr[min_id] > arr[j]:
				min_id = j
		return min_id

	def selectionSort(self, arr, n):
		for i in range(n):
			min_id = self.select(arr, i)
			(arr[i], arr[min_id]) = (arr[min_id], arr[i])
		return arr


class Solution:

	def selectionSort(self, arr, n):
		for i in range(n - 1):
			for j in range(i + 1, n):
				if arr[j] < arr[i]:
					temp = arr[i]
					arr[i] = arr[j]
					arr[j] = temp


class Solution:

	def select(self, arr, i):
		return i + arr[i:len(arr)].index(min(arr[i:len(arr)]))

	def selectionSort(self, arr, n):
		for i in range(0, n - 1):
			mini = self.select(arr, i)
			(arr[i], arr[mini]) = (arr[mini], arr[i])
		return arr


class Solution:

	def selectionSort(self, arr, n):
		for i in range(n):
			min_index = i
			for j in range(i + 1, n):
				if arr[min_index] > arr[j]:
					min_index = j
			(arr[i], arr[min_index]) = (arr[min_index], arr[i])
		return arr


class Solution:

	def select(self, arr, i):
		min = arr[i]
		ind = 0
		for j in range(i + 1, len(arr)):
			if min > arr[j]:
				ind = j
				min = arr[ind]
		if min != arr[i]:
			temp = arr[i]
			arr[i] = arr[ind]
			arr[ind] = temp
		return arr

	def selectionSort(self, arr, n):
		for i in range(0, n):
			self.select(arr, i)
		return arr


class Solution:

	def select(self, arr, i):
		index = i
		for j in range(i, n):
			if arr[j] < arr[index]:
				index = j
		return index

	def selectionSort(self, arr, n):
		for i in range(n):
			index = self.select(arr, i)
			(arr[i], arr[index]) = (arr[index], arr[i])


class Solution:

	def select(self, arr, i):
		min_index = i
		for indx in range(i + 1, len(arr)):
			if arr[min_index] > arr[indx]:
				min_index = indx
		return min_index

	def selectionSort(self, arr, n):
		for i in range(n):
			indx = self.select(arr, i)
			(arr[i], arr[indx]) = (arr[indx], arr[i])
		return arr


class Solution:

	def select(self, arr, i):
		minp = i
		for j in range(i, len(arr)):
			if arr[minp] > arr[j]:
				minp = j
		return minp

	def selectionSort(self, arr, n):
		for i in range(n):
			pos = self.select(arr, i)
			(arr[pos], arr[i]) = (arr[i], arr[pos])


class Solution:

	def select(self, arr, i):
		minpos = i
		for j in range(i, len(arr)):
			if arr[j] < arr[minpos]:
				minpos = j
		return minpos

	def selectionSort(self, arr, n):
		for i in range(len(arr)):
			minnp = self.select(arr, i)
			(arr[minnp], arr[i]) = (arr[i], arr[minnp])


class Solution:

	def select(self, arr, i):
		mini = float('inf')
		idx = -1
		for j in range(i, len(arr)):
			if arr[j] < mini:
				mini = arr[j]
				idx = j
		return idx

	def selectionSort(self, arr, n):
		for k in range(len(arr)):
			idx = self.select(arr, k)
			(arr[k], arr[idx]) = (arr[idx], arr[k])
		return arr


class Solution:

	def select(self, arr, i):
		mini = i
		for j in range(i + 1, n):
			if arr[mini] > arr[j]:
				mini = j
		return mini

	def selectionSort(self, arr, n):
		for i in range(0, n - 1):
			mini = self.select(arr, i)
			(arr[i], arr[mini]) = (arr[mini], arr[i])
		return arr


class Solution:

	def select(self, arr, i):
		minimum = i
		for i in range(i, len(arr)):
			if arr[i] < arr[minimum]:
				minimum = i
		return minimum

	def selectionSort(self, arr, n):
		for i in range(n):
			minimum = self.select(arr, i)
			(arr[i], arr[minimum]) = (arr[minimum], arr[i])


class Solution:

	def select(self, arr, i):
		for y in range(i):
			print(y)

	def selectionSort(self, arr, n):
		for step in range(n):
			min_idx = step
			for i in range(step, n):
				if arr[i] < arr[min_idx]:
					min_idx = i
			(arr[step], arr[min_idx]) = (arr[min_idx], arr[step])
		return arr


class Solution:

	def select(self, arr, i):
		mini = i
		for i in range(i, len(arr)):
			mini = mini if arr[mini] <= arr[i] else i
		return mini

	def selectionSort(self, arr, n):
		for i in range(n):
			k = self.select(arr, i)
			(arr[k], arr[i]) = (arr[i], arr[k])


class Solution:

	def select(self, arr, i):
		pass

	def selectionSort(self, arr, n):
		arr.sort()
		return arr


class Solution:

	def select(self, arr, i, n):
		min_index = i
		for j in range(i + 1, n):
			if arr[min_index] > arr[j]:
				min_index = j
		return min_index

	def selectionSort(self, arr, n):
		for i in range(0, n):
			index = Solution().select(arr, i, n)
			temp = arr[i]
			arr[i] = arr[index]
			arr[index] = temp


class Solution:

	def select(self, arr, i):
		s = arr.sort()
		return s

	def selectionSort(self, arr, n):
		a = arr.sort()
		return a


class Solution:

	def select(self, arr, i):
		m = i
		for j in range(i + 1, len(arr)):
			if arr[j] < arr[m]:
				m = j
		return m

	def selectionSort(self, arr, n):
		for i in range(0, n - 1):
			minimum = self.select(arr, i)
			temp = arr[i]
			arr[i] = arr[minimum]
			arr[minimum] = temp


class Solution:

	def selectionSort(self, arr, n):
		for i in range(len(arr)):
			min = i
			for j in range(i + 1, len(arr)):
				if arr[min] > arr[j]:
					min = j
			(arr[i], arr[min]) = (arr[min], arr[i])
		return arr


class Solution:

	def selectionSort(self, arr, n):
		for i in range(n):
			minval = 9999999999
			ind = -1
			for j in range(i + 1, n):
				if arr[j] < minval:
					ind = j
					minval = arr[j]
			if arr[i] > arr[ind]:
				(arr[i], arr[ind]) = (arr[ind], arr[i])


class Solution:

	def select(self, arr, i):
		minIdx = i
		for idx in range(i + 1, len(arr)):
			if arr[minIdx] > arr[idx]:
				minIdx = idx
		return minIdx

	def selectionSort(self, arr, n):
		for i in range(n):
			idx = self.select(arr, i)
			(arr[i], arr[idx]) = (arr[idx], arr[i])
		return arr


class Solution:

	def selectionSort(self, arr, n):
		arr.sort()


class Solution:

	def select(self, arr, i):
		minIdx = i
		for j in range(i + 1, n):
			if arr[j] < arr[minIdx]:
				minIdx = j
		return minIdx

	def selectionSort(self, arr, n):
		for i in range(n):
			minIdx = self.select(arr, i)
			(arr[i], arr[minIdx]) = (arr[minIdx], arr[i])
		return arr


class Solution:

	def select(self, arr, i, n):
		min = i
		for j in range(i + 1, n):
			if arr[min] > arr[j]:
				min = j
		return min

	def selectionSort(self, arr, n):
		for i in range(n - 1):
			j = self.select(arr, i, n)
			k = arr[j]
			arr[j] = arr[i]
			arr[i] = k


class Solution:

	def selectionSort(self, arr, n):
		for i in range(0, len(arr) - 1):
			min_idx = i
			for j in range(i + 1, len(arr)):
				if arr[j] < arr[min_idx]:
					min_idx = j
			(arr[i], arr[min_idx]) = (arr[min_idx], arr[i])
		return arr


class Solution:

	def select(self, arr, i):
		mini = i
		for ind in range(i + 1, len(arr)):
			if arr[mini] > arr[ind]:
				mini = ind
		return mini

	def selectionSort(self, arr, n):
		for i in range(n):
			ind = self.select(arr, i)
			(arr[ind], arr[i]) = (arr[i], arr[ind])
		return arr


class Solution:

	def select(self, arr, i):
		p = i
		for j in range(p, len(arr)):
			if arr[j] < arr[i]:
				i = j
		return i

	def selectionSort(self, arr, n):
		for i in range(n):
			x = self.select(arr, i)
			(arr[i], arr[x]) = (arr[x], arr[i])


class Solution:

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


class Solution:

	def select(self, arr, i):
		m = i
		for i in range(i + 1, len(arr)):
			if arr[m] > arr[i]:
				m = i
		return m

	def selectionSort(self, arr, n):
		for i in range(n):
			k = self.select(arr, i)
			(arr[i], arr[k]) = (arr[k], arr[i])
		return arr


class Solution:

	def selectionSort(self, arr, n):
		for i in range(0, n - 1):
			minimum = i
			for j in range(i + 1, n):
				if arr[j] < arr[minimum]:
					minimum = j
			(arr[minimum], arr[i]) = (arr[i], arr[minimum])
		return arr


class Solution:

	def selectionSort(self, arr, n):
		for i in range(0, n - 1):
			minEle = i
			for j in range(i + 1, n):
				if arr[j] < arr[minEle]:
					minEle = j
			(arr[i], arr[minEle]) = (arr[minEle], arr[i])


class Solution:

	def swap(self, arr, i, j):
		temp = arr[i]
		arr[i] = arr[j]
		arr[j] = temp

	def select(self, arr, i):
		minIdx = i
		for j in range(i, len(arr)):
			if arr[j] < arr[minIdx]:
				minIdx = j
		self.swap(arr, i, minIdx)

	def selectionSort(self, arr, n):
		for i in range(len(arr)):
			self.select(arr, i)


class Solution:

	def selectionSort(self, arr, n):
		cur_min = 0
		sorted_till_idx = 0
		while sorted_till_idx < len(arr):
			cur_min = sorted_till_idx
			for i in range(sorted_till_idx, len(arr)):
				if arr[i] < arr[cur_min]:
					cur_min = i
			(arr[sorted_till_idx], arr[cur_min]) = (arr[cur_min], arr[sorted_till_idx])
			sorted_till_idx += 1


class Solution:

	def select(self, arr, i):
		min = i
		for j in range(i + 1, len(arr)):
			if arr[j] < arr[min]:
				min = j
		return min

	def selectionSort(self, arr, n):
		for i in range(n):
			min = self.select(arr, i)
			(arr[i], arr[min]) = (arr[min], arr[i])
		return arr
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ob.selectionSort(arr, n)
		for i in arr:
			print(i, end=' ')
		print()


class Solution:

	def select(self, arr, i):
		min = i
		n = len(arr)
		while i < n:
			if arr[i] < arr[min]:
				min = i
			i += 1
		return min

	def selectionSort(self, arr, n):
		for i in range(n):
			index = self.select(arr, i)
			(arr[index], arr[i]) = (arr[i], arr[index])


class Solution:

	def select(self, arr, i):
		Min = 10 ** 9
		Index = -1
		for x in range(i, len(arr)):
			if arr[x] < Min:
				Min = arr[x]
				Index = x
		(arr[i], arr[Index]) = (arr[Index], arr[i])
		return

	def selectionSort(self, arr, n):
		for x in range(n):
			self.select(arr, x)
		return