Given an array A of positive integers, sort the array in ascending order such that element at index K in unsorted array stays unmoved and all other elements are sorted.
 
Example 1:
Ã¢â¬â¹Input : arr[ ] = {10, 4, 11, 7, 6, 20} 
        and K = 2
Output : 4 6 11 7 10 20
Explanation:
Sort an array except an index 2 So, 
4 6 11 7 10 20 
Ã¢â¬â¹Example 2:
Input : arr[ ] = {30, 20, 10} and K = 0
Output :  30 10 20 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function sortExceptK() that takes an array (arr), sizeOfArray (n), an integer K and return he sorted array except for the element at index K. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{5}

Difficulty: EASY
Tags: Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



def sortExceptK (arr, n, k) : 

    #Complete the function



Solutions:
def sortExceptK(arr, n, k):
	result = arr[k]
	arr.sort()
	arr.remove(result)
	arr.insert(k, result)
	lst = list(map(str, arr))
	join = ' '.join(lst)
	return join


def sortExceptK(arr, n, k):
	num = arr[k]
	arr.sort()
	arr.remove(num)
	arr.insert(k, num)
	s = list(map(str, arr))
	s = ' '.join(s)
	return s


def sortExceptK(arr, n, k):
	num = arr[k]
	arr.sort()
	arr.remove(num)
	arr.insert(k, num)
	string = ''
	for i in arr:
		string += str(i) + ' '
	return string


def sortExceptK(arr, n, k):
	e = arr[k]
	p = []
	p[:] = arr[:]
	p.pop(k)
	p.sort()
	arr[:] = p[:k] + [e] + p[k:]
	st = ''
	for i in range(n):
		if i == n - 1:
			st = st + str(arr[i])
		else:
			st = st + str(arr[i]) + ' '
	return st


def sortExceptK(arr, n, k):
	num = arr[k]
	arr.pop(k)
	arr.sort()
	arr.insert(k, num)
	return ' '.join(list(map(str, arr)))


def sortExceptK(arr, n, k):
	a = arr[k]
	arr.remove(a)
	arr = sorted(arr)
	arr.insert(k, a)
	for i in arr:
		print(i, end=' ')
	return ''


def sortExceptK(arr, n, k):
	temp = arr[k]
	arr.remove(temp)
	arr.sort()
	arr.insert(k, temp)
	return ' '.join(map(str, arr))


def sortExceptK(arr, n, k):
	elem = arr.pop(k)
	arr.sort()
	arr.insert(k, elem)
	return ' '.join([str(x) for x in arr])


def sortExceptK(arr, n, k):
	item = arr[k]
	arr.pop(k)
	arr.sort()
	arr.insert(k, item)
	output = ''
	for item in arr:
		output += str(item) + ' '
	return output


def sortExceptK(arr, n, k):
	t = arr[:k] + arr[k + 1:]
	t.sort()
	j = 0
	s = ''
	for i in range(n):
		if i != k:
			s += str(t[j]) + ' '
			j += 1
		else:
			s += str(arr[k]) + ' '
	return s


def sortExceptK(arr, n, k):
	val = arr[k]
	l = arr[:k] + arr[k + 1:]
	l.sort()
	arr[:] = l[:]
	arr.insert(k, val)
	return ' '.join(list(map(str, arr)))


def sortExceptK(arr, n, k):
	t = arr.pop(k)
	arr.sort()
	arr.insert(k, t)
	arr = [str(i) for i in arr]
	return ' '.join(arr)


def sortExceptK(arr, n, k):
	if sorted(arr) == arr:
		s = ''
		for i in arr:
			s += str(i)
			s += ' '
		return s
	if k > n:
		arr.sort()
		s = ''
		for i in arr:
			s += str(i)
			s += ' '
		return s
	tmp = []
	tmp = [] + arr
	tmp.sort()
	tmp.remove(arr[k])
	i = 0
	j = 0
	while i < n:
		if i != k:
			arr[i] = tmp[j]
			j += 1
		i += 1
	s = ''
	for i in arr:
		s += str(i)
		s += ' '
	return s


def sortExceptK(arr, n, k):
	a = arr[k]
	arr.remove(arr[k])
	arr.sort()
	arr.insert(k, a)
	return ' '.join(list(map(str, arr)))


from array import array

def sortExceptK(arr, n, k):
	x = arr[k]
	del arr[k]
	y = sorted(arr)
	y.insert(k, x)
	return ' '.join(map(str, y))


def sortExceptK(arr, n, k):
	l = arr.pop(k)
	arr.sort()
	arr.insert(k, l)
	res = str(arr[0])
	for i in range(1, n):
		res += ' ' + str(arr[i])
	return res


def sortExceptK(arr, n, k):
	ele = arr[k]
	del arr[k]
	arr.sort()
	arr.insert(k, ele)
	print(*arr, end='')
	return ''


def sortExceptK(arr, n, k):
	d = arr[k]
	arr.pop(k)
	arr.sort()
	a = list(map(str, arr[0:k] + [d] + arr[k:]))
	return ' '.join(a)


def sortExceptK(arr, n, k):
	e = arr.pop(k)
	arr.sort()
	arr.insert(k, e)
	arr = str(arr).replace(',', '')
	arr = str(arr).replace('[', '')
	arr = str(arr).replace(']', '')
	return arr


def sortExceptK(arr, n, k):
	val = arr.pop(k)
	arr.sort()
	arr.insert(k, val)
	s = ''
	for i in arr:
		s += str(i)
		s += ' '
	n = len(s)
	return s[:n - 1]


def sortExceptK(arr, n, k):
	key = arr[k]
	arr.sort()
	ind = arr.index(key)
	while ind > k:
		(arr[ind], arr[ind - 1]) = (arr[ind - 1], arr[ind])
		ind -= 1
	while ind < k:
		(arr[ind], arr[ind + 1]) = (arr[ind + 1], arr[ind])
		ind += 1
	st = ''
	for i in range(n - 1):
		st += str(arr[i]) + ' '
	st += str(arr[-1])
	return st


def sortExceptK(arr, n, k):
	index = k
	value = arr[k]
	arr.remove(value)
	arr.sort()
	arr.insert(index, value)
	value = [str(x) for x in arr]
	return ' '.join(value)


def sortExceptK(arr, n, k):
	val = arr[k]
	arr.sort()
	i = n - 1
	while i >= 0:
		if arr[i] == val:
			break
		i -= 1
	if i == k:
		return ' '.join(map(str, arr))
	if i > k:
		while i > k:
			(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
			i -= 1
		return ' '.join(map(str, arr))
	while i < k:
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		i += 1
	return ' '.join(map(str, arr))


def sortExceptK(arr, n, k):
	temp = arr[k]
	arr.sort()
	arr.remove(temp)
	arr.insert(k, temp)
	res = ' '.join((str(i) for i in arr))
	return res


def sortExceptK(arr, n, k):
	l = []
	l1 = []
	a1 = arr[k]
	l.append(a1)
	a2 = arr[0:k]
	a3 = arr[k + 1:]
	a4 = a2 + a3
	a4.sort()
	m = a4[0:k]
	m1 = a4[k:]
	s = ''
	last = m + l + m1
	for i in last:
		s = s + str(i) + ' '
	return s


def sortExceptK(arr, n, k):
	brr = sorted(arr[:k] + arr[k + 1:])
	brr.insert(k, arr[k])
	brr = [str(i) for i in brr]
	return ' '.join(brr)


def sortExceptK(arr, n, k):
	ele = arr[k]
	temp = arr[:k] + arr[k + 1:]
	temp.sort()
	ans = ''
	j = 0
	for i in range(n):
		if i == k:
			ans += str(ele) + ' '
		else:
			ans += str(temp[j]) + ' '
			j += 1
	return ans


def sortExceptK(arr, n, k):
	b = []
	for i in range(n):
		if i != k:
			b.append(arr[i])
	b.sort()
	m = 0
	t = ''
	for i in range(n):
		if i != k:
			arr[i] = b[m]
			m += 1
		t += str(arr[i]) + ' '
	return t


def sortExceptK(arr, n, k):
	t = arr.copy()
	t.remove(t[k])
	t.sort()
	t.insert(k, arr[k])
	return ' '.join(list(map(str, t)))


def sortExceptK(arr, n, k):
	y = arr[k]
	arr.sort()
	x = arr.index(y)
	arr.pop(x)
	arr.insert(k, y)
	return ' '.join(map(str, arr))


def sortExceptK(arr, n, k):
	el = [arr.pop(k)]
	arr.sort()
	arr[:] = arr[:k] + el + arr[k:]
	res = map(str, arr)
	return ' '.join(res)


def sortExceptK(a, n, k):
	e = a[k]
	a.remove(a[k])
	a.sort()
	a.insert(k, e)
	s = ''
	for i in range(n):
		s += str(a[i]) + ' '
	return s
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	k = int(input())
	ans = sortExceptK(arr, n, k)
	print(ans)


def sortExceptK(arr, n, k):
	m = arr[k]
	arr.sort()
	arr.remove(m)
	arr.insert(k, m)
	for i in range(n - 1):
		print(arr[i], end=' ')
	return arr[n - 1]
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	k = int(input())
	ans = sortExceptK(arr, n, k)
	print(ans)


def sortExceptK(arr, n, k):
	y = arr[k]
	arr.sort()
	x = arr.index(y)
	arr.pop(x)
	arr.insert(k, y)
	return ' '.join(map(str, arr))
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	k = int(input())
	ans = sortExceptK(arr, n, k)
	print(ans)


def sortExceptK(arr, n, k):
	l = arr[:k]
	r = arr[k + 1:]
	m = arr[k]
	f = l + r
	f.sort()
	f.insert(k, m)
	return ' '.join(map(str, f))


def sortExceptK(a, n, k):
	t = a.pop(k)
	a.sort()
	a.insert(k, t)
	return ' '.join(map(str, a))


def sortExceptK(arr, n, k):
	temp = arr[k]
	arr.remove(arr[k])
	arr.sort()
	arr.insert(k, temp)
	for i in range(n):
		arr[i] = str(arr[i])
	trr = ' '.join(arr)
	return trr


def sortExceptK(arr, n, k):
	res = arr.copy()
	removed = res.pop(k)
	res.sort()
	res.insert(k, removed)
	s = [str(i) for i in res]
	return ' '.join(s)


def sortExceptK(arr, n, k):
	ans = []
	for i in range(n):
		if i != k:
			ans.append(arr[i])
	ans.sort()
	ans.insert(k, arr[k])
	return ' '.join(map(str, ans))


def sortExceptK(arr, n, k):
	z = arr[k]
	arr.remove(z)
	x = sorted(arr)
	x.insert(k, z)
	res = ''
	for i in x:
		res = res + str(i) + ' '
	return res


def sortExceptK(arr, n, k):
	x = arr.pop(k)
	arr.sort()
	arr.insert(k, x)
	j = ''
	for i in range(0, len(arr)):
		if i != 0:
			j = j + ' ' + str(arr[i])
		else:
			j = j + str(arr[i])
	return j


def sortExceptK(arr, n, k):
	temp = arr[k]
	arr.remove(temp)
	arr.sort()
	arr.insert(k, temp)
	s = ''
	for x in arr:
		s += str(x) + ' '
	return s


def sortExceptK(arr, n, k):
	element = arr.pop(k)
	arr.sort()
	arr.insert(k, element)
	res = ''
	for i in arr:
		res = res + str(i) + ' '
	return res


def sortExceptK(arr, n, k):
	li = arr.copy()
	li.append(arr[k])
	li.remove(arr[k])
	a = li[:len(li) - 1]
	a.sort()
	l1 = a[:k]
	l2 = a[k:]
	l3 = [arr[k]]
	ans = l1 + l3 + l2
	res = ''
	for i in ans:
		res = res + str(i) + ' '
	return res


def sortExceptK(arr, n, k):
	a = arr[k]
	arr.remove(a)
	l = sorted(arr)
	l.insert(k, a)
	s = ''
	for i in l:
		s = s + str(i)
		s = s + ' '
	return s


def sortExceptK(arr, n, k):
	t = arr[k]
	arr.pop(k)
	arr.sort()
	arr = arr[:k] + [t] + arr[k:]
	res = ''
	for i in arr:
		res += str(i)
		res += ' '
	return res


def sortExceptK(arr, n, k):
	arr1 = arr[:k]
	arr2 = arr[k + 1:]
	Arr = arr1 + arr2
	Arr.sort()
	Arr1 = [0 for _ in range(n)]
	idx = 0
	for i in range(len(arr)):
		if i != k:
			Arr1[i] = Arr[idx]
			idx += 1
		else:
			Arr1[i] = arr[k]
	S = ''
	for i in range(len(Arr1)):
		S += str(Arr1[i]) + ' '
	return S


def sortExceptK(arr, n, k):
	a = arr[k]
	arr.pop(k)
	arr.sort()
	arr.insert(k, a)
	res = ''
	for ele in arr:
		res = res + str(ele) + ' '
	return res


def sortExceptK(arr, n, k):
	x = arr[k]
	arr.sort()
	y = arr.index(x)
	if k < y:
		for i in range(y, k, -1):
			arr[i] = arr[i - 1]
		arr[k] = x
		return arr
	for i in range(y, k):
		arr[i] = arr[i + 1]
	arr[k] = x
	return arr


def sortExceptK(arr, n, k):
	temp = arr[k]
	brr = sorted(arr[:k] + arr[k + 1:])
	brr.insert(k, temp)
	return ' '.join(list(map(str, brr)))


def sortExceptK(arr, n, k):
	l3 = [arr[k]]
	arr.remove(arr[k])
	arr.sort()
	l1 = arr[:k]
	l2 = arr[k:]
	ans = l1 + l3 + l2
	res = ''
	for i in ans:
		res = res + str(i) + ' '
	return res


def sortExceptK(arr, n, k):
	num = arr[k]
	arr.pop(k)
	brr = sorted(arr)
	brr.insert(k, num)
	crr = ''
	for i in brr:
		crr += str(i) + ' '
	return crr


def sortExceptK(arr, n, k):
	brr = sorted(arr)
	brr.remove(arr[k])
	brr.insert(k, arr[k])
	g = ''
	for j in brr:
		g += str(j) + ' '
	return g


def sortExceptK(arr, n, k):
	z = arr.pop(k)
	arr = sorted(arr)
	arr.insert(k, z)
	return str(arr)[1:-1].replace(',', '')


def sortExceptK(arr, n, k):
	(arr[k], arr[n - 1]) = (arr[n - 1], arr[k])
	arr = sorted(arr[:n - 1]) + [arr[n - 1]]
	arr.insert(k, arr[n - 1])
	arr.pop()
	printlistToStr = ' '.join(map(str, arr))
	return printlistToStr


def sortExceptK(arr, n, k):
	j = sorted(arr)
	j.remove(arr[k])
	j.insert(k, arr.pop(k))
	return ' '.join(map(str, j))


def sortExceptK(arr, n, k):
	s = ''
	lst = arr
	l = arr[k]
	arr = arr.pop(k)
	a = sorted(lst)
	a.insert(k, l)
	for i in a:
		s = s + str(i)
		s += ' '
	return s


def sortExceptK(arr, n, k):
	val = arr[k]
	arr[:] = arr[:k] + arr[k + 1:]
	arr.sort()
	arr[:] = arr[:k] + [val] + arr[k:]
	return ' '.join([str(el) for el in arr])


def sortExceptK(arr, n, k):
	a2 = [0] * n
	for i in range(0, n):
		a2[i] = arr[i]
	a2.pop(k)
	a2.sort()
	a2.insert(k, arr[k])
	res = ' '.join(map(str, list(a2)))
	return res


def sortExceptK(arr, n, k):
	a = arr[k]
	if k + 1 != len(arr):
		arr1 = sorted(arr[:k] + arr[k + 1:])
		arr1.insert(k, a)
	else:
		arr1 = sorted(arr[:k])
		arr1.append(a)
	s = ''
	for i in arr1:
		s += str(i) + ' '
	return s


def sortExceptK(arr, n, k):
	elem = arr.pop(k)
	arr.sort()
	arr.insert(k, elem)
	return ' '.join(map(str, arr))