Given an array A of non-negative integers. Sort the array in ascending order such that element at the Kth position in unsorted array stays unmoved and all other elements are sorted. 
Example 1:
Input:
N = 5, K = 2
arr[] = {3 12 30 79 2}
Output: 2 12 3 30 79
Explanation: The element at the 2nd 
position (12) remains at its own place 
while others are sorted.
Ã¢â¬â¹Example 2:
Input: 
N = 10, K = 5
arr[] = {16 16 18 10 9 22 11 5 35 22}
Output: 5 10 11 16 9 16 18 22 22 35
Explanation: The element at the 5th 
position (9) remains at its own place
while others are sorted.
Your Task:
You don't need to read input or print anything. Your task is to complete the function strangeSort() which takes the array A[], its size N and an integer K (1-based) as inputs and modifies the array such that all the elements except the one at the K-th position are sorted in non-decreasing order. The K-th position remains unchanged.
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(1).
Constraints:
2<=N<=5*10^{5}
1<=K<=N

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def strangeSort (self,arr, n, k):
        # your code here

Solutions:
class Solution:

	def strangeSort(self, arr, n, k):
		i = 0
		arr1 = [0] * n
		while i < n:
			if i < k - 1:
				arr1[i + 1] = arr[i]
				i = i + 1
				continue
			if i > k - 1:
				arr1[i] = arr[i]
				i = i + 1
				continue
			else:
				i = i + 1
				continue
		arr1.sort()
		j = 0
		while j < n:
			if j < k - 1:
				arr[j] = arr1[j + 1]
				j = j + 1
				continue
			if j > k - 1:
				arr[j] = arr1[j]
				j = j + 1
				continue
			else:
				j = j + 1
				continue


class Solution:

	def strangeSort(self, arr, n, k):
		work = sorted(arr)
		x = work.pop(work.index(arr[k - 1]))
		work.insert(k - 1, x)
		for i in range(n):
			arr[i] = work[i]


class Solution:

	def strangeSort(self, arr, n, k):
		c = arr[k - 1]
		arr.pop(k - 1)
		arr.sort()
		arr.insert(k - 1, c)
		return


class Solution:

	def strangeSort(self, arr, n, k):
		s = arr[k - 1]
		arr.sort()
		arr.remove(s)
		arr.insert(k - 1, s)
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		a = arr.pop(k - 1)
		arr.sort()
		arr.insert(k - 1, a)


class Solution:

	def strangeSort(self, arr, n, k):
		val = arr[k - 1]
		li = arr[:k - 1] + arr[k:]
		li.sort()
		arr[:] = li[:]
		arr.insert(k - 1, val)
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		li = []
		t = arr[k - 1]
		for i in range(n):
			if i + 1 != k:
				li.append(arr[i])
		li = sorted(li)
		li.insert(k - 1, t)
		return li


class Solution:

	def strangeSort(self, arr, n, k):
		anchor = arr[k - 1]
		del arr[k - 1]
		arr.sort()
		result = arr[0:k - 1] + [anchor] + arr[k - 1:]
		arr.clear()
		for x in range(n):
			arr.append(result[x])


class Solution:

	def strangeSort(self, arr, n, k):
		temp = arr[k - 1]
		del arr[k - 1]
		arr.sort()
		arr.insert(k - 1, temp)


class Solution:

	def strangeSort(self, arr, n, k):
		w = []
		s = 0
		for i in range(n):
			if i == k - 1:
				s += arr[i]
			else:
				w.append(arr[i])
		w.sort()
		w.insert(k - 1, s)
		arr.clear()
		arr += w
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		num = arr[k - 1]
		arr.sort()
		for i in range(n):
			if arr[i] == num:
				new_idx = i
				break
		if new_idx < k:
			for i in range(new_idx, k - 1, 1):
				arr[i] = arr[i + 1]
			arr[k - 1] = num
		else:
			for i in range(new_idx, k - 1, -1):
				arr[i] = arr[i - 1]
			arr[k - 1] = num


class Solution:

	def strangeSort(self, arr, n, k):
		val = arr[k - 1]
		l = arr[:k - 1] + arr[k:]
		l.sort()
		arr[:] = l[:]
		arr.insert(k - 1, val)


class Solution:

	def strangeSort(self, arr, n, k):
		e = arr[k - 1]
		arr.sort()
		arr.remove(e)
		arr.insert(k - 1, e)


class Solution:

	def strangeSort(self, arr, n, k):
		item = arr[k - 1]
		del arr[k - 1]
		arr.sort()
		arr.insert(k - 1, item)
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		d = arr[k - 1]
		arr.pop(k - 1)
		arr.sort()
		arr[:] = arr[:k - 1] + [d] + arr[k - 1:]


class Solution:

	def strangeSort(self, arr, n, k):
		p = arr[k - 1]
		aa = arr.remove(arr[k - 1])
		arr[:] = sorted(arr)
		arr.insert(k - 1, p)


class Solution:

	def strangeSort(self, arr, n, k):
		l = arr[k - 1]
		l1 = sorted(arr[:k - 1] + arr[k:])
		arr[:] = l1[:]
		arr.insert(k - 1, l)
		return arr


class Solution:

	def quicksort(self, arr, low, high):
		if low < high:
			p = self.partition(arr, low, high)
			self.quicksort(arr, low, p - 1)
			self.quicksort(arr, p + 1, high)

	def partition(self, arr, low, high):
		pivot = arr[high]
		i = low - 1
		for j in range(low, high):
			if arr[j] < pivot:
				i += 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
		return i + 1

	def strangeSort(self, arr, n, k):
		kth = arr.pop(k - 1)
		a = arr
		a.sort()
		a.insert(k - 1, kth)
		arr = a
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		k -= 1
		co = arr.copy()
		ele = co[k]
		del co[k]
		co.sort()
		co.insert(k, ele)
		arr.clear()
		arr.extend(co)


class Solution:

	def strangeSort(self, arr, n, k):
		p = arr[k - 1]
		arr.sort()
		ind = arr.index(p)
		if ind < k - 1:
			for i in range(ind, k - 1):
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		elif ind > k - 1:
			for i in range(ind, k - 1, -1):
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])


class Solution:

	def strangeSort(self, arr, n, k):
		for i in range(len(arr)):
			if i == k - 1:
				c = arr[i]
		arr.remove(c)
		arr.sort()
		arr.insert(k - 1, c)
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		x = arr.copy()
		arr.remove(arr[k - 1])
		a = arr.copy()
		a.sort()
		a.insert(k - 1, x[k - 1])
		arr.clear()
		return arr.extend(a)


class Solution:

	def strangeSort(self, arr, n, k):
		temp = arr[k - 1]
		arr[k - 1] = 1000000
		arr.sort()
		i = n - 1
		while i >= k:
			arr[i] = arr[i - 1]
			i -= 1
		arr[i] = temp


class Solution:

	def strangeSort(self, arr, n, k):
		k1 = arr[k - 1]
		arr.sort()
		arr.remove(k1)
		arr.append(0)
		for i in range(n - 1, k - 1, -1):
			arr[i] = arr[i - 1]
		arr[k - 1] = k1
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		v = arr[k - 1]
		l = arr[:k - 1] + arr[k:]
		l.sort()
		arr[:] = l[:]
		arr.insert(k - 1, v)
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		key = arr[k - 1]
		arr.sort()
		for i in range(n):
			if arr[i] == key:
				break
		if i > k - 1:
			while i > k - 1:
				arr[i] = arr[i - 1]
				i -= 1
			arr[k - 1] = key
		elif i < k - 1:
			while i < k - 1:
				arr[i] = arr[i + 1]
				i += 1
			if i + 2 < n:
				arr[i] = arr[i + 2]
			arr[k - 1] = key


class Solution:

	def strangeSort(self, arr, n, k):
		l = []
		l[:] = arr[:]
		del l[k - 1]
		l.sort()
		first = k - 1
		r = arr[k - 1]
		for i in range(first):
			arr[i] = l[i]
		arr[first] = r
		for i in range(k, n):
			arr[i] = l[first]
			first += 1


class Solution:

	def strangeSort(self, arr, n, k):
		c = arr[k - 1]
		arr.sort()
		arr.remove(c)
		arr.insert(k - 1, c)
		return sorted(arr)


class Solution:

	def strangeSort(self, arr, n, k):
		a = arr[k - 1]
		x = arr[:k - 1]
		y = arr[k:]
		z = sorted(x + y)
		z.insert(k - 1, a)
		for i in range(n):
			if arr[i] != z[i]:
				arr[i] = z[i]


class Solution:

	def strangeSort(self, arr, n, k):
		num = arr.pop(k - 1)
		new = []
		for (i, x) in enumerate(sorted(arr)):
			if i == k - 1:
				new.append(num)
			new.append(x)
		if k == n:
			new.append(num)
		arr[:] = new


class Solution:

	def strangeSort(self, arr, n, k):
		l = arr.copy()
		a = l.pop(k - 1)
		arr.clear()
		b = 0
		l.sort()
		for i in range(len(l)):
			if i == k - 1:
				b = i
				break
			else:
				arr.append(l[i])
		arr.append(a)
		arr += l[b:]
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		a = arr.copy()
		temp = arr[k - 1]
		del a[k - 1]
		a.sort()
		arr[:k - 1] = a[:k - 1]
		arr[k - 1] = temp
		arr[k:] = a[k - 1:n - 1]


class Solution:

	def strangeSort(self, arr, n, k):
		j = arr[:k - 1] + arr[k:]
		num = arr[k - 1]
		j.sort()
		arr[:] = j
		arr.insert(k - 1, num)


class Solution:

	def strangeSort(self, arr, n, k):
		x = []
		for i in range(n):
			if i + 1 == k:
				pass
			else:
				x.append(arr[i])
		x.sort()
		x.insert(k - 1, arr[k - 1])
		for i in range(n):
			arr[i] = x[i]


class Solution:

	def strangeSort(self, arr, n, k):
		temp = arr[k - 1]
		arr[k - 1] = +999999
		arr.sort()
		arr.pop()
		arr.insert(k - 1, temp)
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		a = arr.pop(k - 1)
		arr.sort()
		arr.insert(k - 1, a)
		return arr
t = int(input())
for tc in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ob = Solution()
	ob.strangeSort(arr, n, k)
	for i in range(n):
		print(arr[i], end=' ')
	print()


class Solution:

	def strangeSort(self, arr, n, k):
		st = arr[k - 1]
		arr.remove(st)
		arr.sort()
		arr.insert(k - 1, st)
t = int(input())
for tc in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ob = Solution()
	ob.strangeSort(arr, n, k)
	for i in range(n):
		print(arr[i], end=' ')
	print()


class Solution:

	def strangeSort(self, arr, n, k):
		b = []
		for i in range(n):
			if i + 1 != k:
				b.append(arr[i])
		b.sort()
		m = 0
		for i in range(n):
			if i + 1 != k:
				arr[i] = b[m]
				m += 1
t = int(input())
for tc in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ob = Solution()
	ob.strangeSort(arr, n, k)
	for i in range(n):
		print(arr[i], end=' ')
	print()


class Solution:

	def strangeSort(self, arr, n, k):
		x = arr[k - 1]
		arr[k - 1] = float('inf')
		arr.sort()
		i = n - 1
		while i > k - 1:
			arr[i] = arr[i - 1]
			i -= 1
		arr[k - 1] = x
t = int(input())
for tc in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ob = Solution()
	ob.strangeSort(arr, n, k)
	for i in range(n):
		print(arr[i], end=' ')
	print()


class Solution:

	def strangeSort(self, arr, n, k):
		x = arr[k - 1]
		arr[k - 1] = 999999
		arr.sort()
		temp = arr[k - 1]
		for i in range(k, n):
			z = arr[i]
			arr[i] = arr[k - 1]
			arr[k - 1] = z
		arr[k - 1] = x
		return arr


class Solution:

	def strangeSort(self, arr, n, k):
		x = arr[k - 1]
		arr[k - 1] = 100000000
		arr.sort()
		for i in range(n - 1, k - 1, -1):
			arr[i] = arr[i - 1]
		arr[k - 1] = x
		return arr