Given an array, a positive integer, sort the array in ascending order such that the element at index K in the unsorted array stays unmoved and all other elements are sorted.
Examples:
Input : arr[] = {10, 4, 11, 7, 6, 20}
k = 2;
Output : arr[] = {4, 6, 11, 7, 10, 20}
Input : arr[] = {30, 20, 10}
k = 0
Output : arr[] = {30, 10, 20}
A simple solution is to copy all elements except k-th of a given array to another array. Then sort the other array using a sorting algorithm. Finally, again copy the sorted array to the original array. While copying, skip k-th element.
Java
// Java code for the approachimport java.util.Arrays;public class GFG { // Driver code public static void main(String[] args) { int[] arr = {10, 4, 11, 7, 6, 20 }; int k = 2; int n = arr.length; // Function Call sortExceptK(arr, k); // Print final array for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); } // Function to sort an array in ascending order // except for the element at index k public static void sortExceptK(int[] arr, int k) { int[] temp = new int[arr.length - 1]; int index = 0; // Copy all elements except k-th to temp array for (int i = 0; i < arr.length; i++) { if (i != k) { temp[index++] = arr[i]; } } // Sort the temp array Arrays.sort(temp); // Copy the sorted array back to original array index = 0; for (int i = 0; i < arr.length; i++) { if (i != k) { arr[i] = temp[index++]; } } }} |
Output
4 6 11 7 10 20
Time Complexity: O(n*log2n) as sorting takes n*log2n time.
Space Complexity: O(n) as temp array has been created.
Below is an efficient solution.
- Swap k-th element with the last element.
- Sort all elements except the last.
- For every element from (k+1)-th to last, move them one position ahead.1
- Copy k-th element back to position k.
Java
// Java program to sort all elements except// element at index k.import java.util.Arrays;class GFG { static int sortExceptK(int arr[], int k, int n) { // Move k-th element to end int temp = arr[k]; arr[k] = arr[n-1]; arr[n-1] = temp; // Sort all elements except last Arrays.sort(arr, 0, n-1); // Store last element (originally k-th) int last = arr[n-1]; // Move all elements from k-th to one // position ahead. for (int i = n-1; i > k; i--) arr[i] = arr[i-1]; // Restore k-th element arr[k] = last; return 0; } //Driver code public static void main (String[] args) { int a[] = {10, 4, 11, 7, 6, 20 }; int k = 2; int n = a.length; sortExceptK(a, k, n); for (int i = 0; i < n; i++) System.out.print(a[i] + " "); }}//This code is contributed by Anant Agarwal. |
Output
4 6 11 7 10 20
Time Complexity: O(n*log(n)) where n is the number of elements.
Auxiliary Space: O(1)
Please refer complete article on Sorting all array elements except one for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
