{"id":"22dde912-a0e2-480d-8c45-734196273918","name":"Sort K-sorted Array","description":"1. You are given a number n, representing the size of array a.\r\n2. You are given n numbers, representing elements of array a.\r\n3. The array is nearly sorted. Every element is at-max displaced k spots left or right to it's position in the sorted array. Hence it is being called k-sorted array.\r\n4. You are required to sort and print the sorted array.\r\n\r\nNote -> You can use at-max k extra space and nlogk time complexity.","inputFormat":"Input is managed for you","outputFormat":"Print the elements of sorted array in separate lines.","constraints":"1 &lt;= n &lt;= 30\r\n0 &lt;= n1, n2, .. n elements &lt;= 100\r\n0 &lt; k &lt;= n","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\n \nint sortK(int arr[], int n, int k){\n\n//write your code here\n\n\n}\n\nint main()\n{\n int n;\n cin>>n;\n int arr[n];\n for(int i = 0 ; i<n ; i++){\n int data;\n cin>>data;\n arr[i]=data;\n }\n int k;\n cin>>k;\n sortK(arr, n, k);\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] arr = new int[n];\r\n\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(br.readLine());\r\n }\r\n\r\n int k = Integer.parseInt(br.readLine());\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"from heapq import heapify,heappush,heappop\ndef sort(l,n,k):\n #write your code here\n\ndef main():\n ints = []\n n = int(input())\n for i in range(0,n):\n ele=int(input())\n ints.append(ele)\n size = len(ints)\n\n k=int(input())\n sort(ints, size, k)\n \nif __name__ == '__main__':\n main()"}},"points":10,"difficulty":"easy","sampleInput":"9\r\n3\r\n2\r\n4\r\n1\r\n6\r\n5\r\n7\r\n9\r\n8\r\n3","sampleOutput":"1\r\n2\r\n3\r\n4\r\n5\r\n6\r\n7\r\n8\r\n9","questionVideo":"https://www.youtube.com/embed/1I2uRpdbiK0","hints":[],"associated":[{"id":"0217d274-f808-4da0-935f-96d44c37dfbb","name":"How many elements we are adding to the priority queue? (Sort k sorted Array)","slug":"how-many-elements-we-are-adding-to-the-priority-queue-sort-k-sorted-array","type":4},{"id":"1bf35453-1134-40ed-8b63-455042bbce0a","name":"Is Array completely sorted in \"Sort k sorted Array\" problem?","slug":"is-array-completely-sorted-in-sort-k-sorted-array-problem","type":4},{"id":"a5bb9c75-78de-4080-8a67-588a13357388","name":"Which type of Queue we are using? (Sort k sorted Array)","slug":"which-type-of-queue-we-are-using-sort-k-sorted-array","type":4},{"id":"d5c99373-5ed9-4649-8adc-cb547b835907","name":"where does the sorted element move? (Sort k sorted Array)","slug":"where-does-the-sorted-element-move-sort-k-sorted-array","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1254d21e-2209-40bc-9e24-00d135ace68d","name":"Hashmap And Heap For Beginners","slug":"hashmap-and-heap-for-beginners","type":0},{"id":"759d9c3f-4686-4333-a147-dcf56743f94e","name":"Sort K-sorted Array","slug":"sort-k-sorted-array","type":1}],"next":{"id":"23f88451-cdac-4b06-8967-d849053c7d54","name":"Sort K-sorted Array","type":3,"slug":"sort-k-sorted-array"},"prev":{"id":"cc5dd04d-e1b1-4bc7-a175-2dbea9d39014","name":"K Largest Elements","type":3,"slug":"k-largest-elements"}}}

Sort K-sorted Array

1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing elements of array a. 3. The array is nearly sorted. Every element is at-max displaced k spots left or right to it's position in the sorted array. Hence it is being called k-sorted array. 4. You are required to sort and print the sorted array. Note -> You can use at-max k extra space and nlogk time complexity.

{"id":"22dde912-a0e2-480d-8c45-734196273918","name":"Sort K-sorted Array","description":"1. You are given a number n, representing the size of array a.\r\n2. You are given n numbers, representing elements of array a.\r\n3. The array is nearly sorted. Every element is at-max displaced k spots left or right to it's position in the sorted array. Hence it is being called k-sorted array.\r\n4. You are required to sort and print the sorted array.\r\n\r\nNote -> You can use at-max k extra space and nlogk time complexity.","inputFormat":"Input is managed for you","outputFormat":"Print the elements of sorted array in separate lines.","constraints":"1 &lt;= n &lt;= 30\r\n0 &lt;= n1, n2, .. n elements &lt;= 100\r\n0 &lt; k &lt;= n","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\n \nint sortK(int arr[], int n, int k){\n\n//write your code here\n\n\n}\n\nint main()\n{\n int n;\n cin>>n;\n int arr[n];\n for(int i = 0 ; i<n ; i++){\n int data;\n cin>>data;\n arr[i]=data;\n }\n int k;\n cin>>k;\n sortK(arr, n, k);\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] arr = new int[n];\r\n\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(br.readLine());\r\n }\r\n\r\n int k = Integer.parseInt(br.readLine());\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"from heapq import heapify,heappush,heappop\ndef sort(l,n,k):\n #write your code here\n\ndef main():\n ints = []\n n = int(input())\n for i in range(0,n):\n ele=int(input())\n ints.append(ele)\n size = len(ints)\n\n k=int(input())\n sort(ints, size, k)\n \nif __name__ == '__main__':\n main()"}},"points":10,"difficulty":"easy","sampleInput":"9\r\n3\r\n2\r\n4\r\n1\r\n6\r\n5\r\n7\r\n9\r\n8\r\n3","sampleOutput":"1\r\n2\r\n3\r\n4\r\n5\r\n6\r\n7\r\n8\r\n9","questionVideo":"https://www.youtube.com/embed/1I2uRpdbiK0","hints":[],"associated":[{"id":"0217d274-f808-4da0-935f-96d44c37dfbb","name":"How many elements we are adding to the priority queue? (Sort k sorted Array)","slug":"how-many-elements-we-are-adding-to-the-priority-queue-sort-k-sorted-array","type":4},{"id":"1bf35453-1134-40ed-8b63-455042bbce0a","name":"Is Array completely sorted in \"Sort k sorted Array\" problem?","slug":"is-array-completely-sorted-in-sort-k-sorted-array-problem","type":4},{"id":"a5bb9c75-78de-4080-8a67-588a13357388","name":"Which type of Queue we are using? (Sort k sorted Array)","slug":"which-type-of-queue-we-are-using-sort-k-sorted-array","type":4},{"id":"d5c99373-5ed9-4649-8adc-cb547b835907","name":"where does the sorted element move? (Sort k sorted Array)","slug":"where-does-the-sorted-element-move-sort-k-sorted-array","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1254d21e-2209-40bc-9e24-00d135ace68d","name":"Hashmap And Heap For Beginners","slug":"hashmap-and-heap-for-beginners","type":0},{"id":"759d9c3f-4686-4333-a147-dcf56743f94e","name":"Sort K-sorted Array","slug":"sort-k-sorted-array","type":1}],"next":{"id":"23f88451-cdac-4b06-8967-d849053c7d54","name":"Sort K-sorted Array","type":3,"slug":"sort-k-sorted-array"},"prev":{"id":"cc5dd04d-e1b1-4bc7-a175-2dbea9d39014","name":"K Largest Elements","type":3,"slug":"k-largest-elements"}}}
plane

Editor

Loading...

Sort K-sorted Array

easy

1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing elements of array a. 3. The array is nearly sorted. Every element is at-max displaced k spots left or right to it's position in the sorted array. Hence it is being called k-sorted array. 4. You are required to sort and print the sorted array. Note -> You can use at-max k extra space and nlogk time complexity.

Constraints

1 <= n <= 30 0 <= n1, n2, .. n elements <= 100 0 < k <= n

Format

Input

Input is managed for you

Output

Print the elements of sorted array in separate lines.

Example

Sample Input

9 3 2 4 1 6 5 7 9 8 3

Sample Output

1 2 3 4 5 6 7 8 9

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode