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.
C++
// C++ code for the approach#include <bits/stdc++.h>using namespace std;// Function to sort an array in ascending order// except for the element at index kvoid sortExceptK(int arr[], int n, int k) { int temp[n - 1], index = 0; // Copy all elements except k-th to temp array for (int i = 0; i < n; i++) { if (i != k) { temp[index++] = arr[i]; } } // Sort the temp array sort(temp, temp + n - 1); // Copy the sorted array back to original array index = 0; for (int i = 0; i < n; i++) { if (i != k) { arr[i] = temp[index++]; } }}// Driver codeint main() { int arr[] = { 10, 4, 11, 7, 6, 20 }; int k = 2; int n = sizeof(arr) / sizeof(arr[0]); // Function Call sortExceptK(arr, n, k); // Print final array for (int i = 0; i < n; i++) { cout << arr[i] << " "; } return 0;} |
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.
C++
// CPP program to sort all elements except// element at index k.#include <bits/stdc++.h>using namespace std;int sortExceptK(int arr[], int k, int n){ // Move k-th element to end swap(arr[k], arr[n-1]); // Sort all elements except last sort(arr, arr + 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;}// Driver codeint main(){ int a[] = {10, 4, 11, 7, 6, 20 }; int k = 2; int n = sizeof(a) / sizeof(a[0]); sortExceptK(a, k, n); for (int i = 0; i < n; i++) cout << a[i] << " ";} |
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!
