Sorting all array elements except one

Sample Example

Input: arr[] = {11, 5, 90, 33, 3, 1, 6}

            i=3

Output: {1, 3, 90, 5, 6, 11, 33}

Input: arr[] = {70, 40, 11, 5, 90}

           i = 0

Output: {70, 5, 11, 40, 90}

Input:  arr[] = {12, 34, 90}

             i=2

Output: {12, 34, 90}

Approach

We create a new array and then copy the elements of the original array to the new array except for the element that we do not want to sort. After that, we sort the new array and copy the elements from the new sorted array to the original array skipping the element that we do not want to sort. This effectively will sort all array elements except one.

Pseudocode

• First, we initialize the array.
• Then we create a new array of the size n-1. Where n is the size of the original array.
• Then we copy the elements of the original array to the new array except the element that we want to  split the array from.
• Then we sort the new array and copy the elements of the new array to the original array skipping the element that we want to split the array from.
• Return the array.

Implementation

In Java

// Java program to sort all array elements except one at index k.
import java.util.Arrays;
public class CN
{
	//function to sort all array elements except one
	static int sortExceptK(int arr[], int k, int n)
	{
		//initializing the new array
		int[] newArr = new int[n - 1];
		int j = 0;
		//copying the elements of the original array to the new array
		for (int i = 0; i < n; i++)
		{
			//skipping the element where we want to split the array
			if (i == k){
				continue;
			}
		newArr[j++] = arr[i];
		}
	//sorting the new array
	Arrays.sort(newArr);
	j = 0;
	//copying the elements of the sorted new array to the original array
	for (int i = 0; i < n; i++)
	{
		//skipping the element where we want to split the array
		if (i == k){
			continue;
		}
		arr[i] = newArr[j++];
	}
	return 0;
}

//Driver code for sort all array elements except one
public static void main (String[] args)
{
	int arr[] = {1, 40, 13, 17, 16, 0};
	int k = 4;
	int n = arr.length;
	
	sortExceptK(arr, k, n);

	for (int i = 0; i < n; i++)
		System.out.print(arr[i] + " ");
	}
}

Output

0 1 13 17 16 40 

Complexity analysis

Time complexity:

O(n*log(n)). Here, n is the length of the array. The complexity is of the order of nlog(n) because we have to sort all array elements except one. Sorting takes a time complexity of O(n*log(n)).  

Space complexity: 

O(n) as a new array is created.

Read More - Time Complexity of Sorting Algorithms and Rabin Karp Algorithm.

Optimized approach

In this approach, we swap the element that we do not want to sort with the last element. Let the position of this element be k. Then we sort the whole array except the last element. We then shift all the elements after the kth element to one place and put the kth element back to its position.

Also Read - Selection Sort in C

Pseudocode

• Swap the K_th element with the last element.

swap(arr[k], arr[n-1]);

• Sort all the elements except the last element.

sort(arr, arr + n - 1);

• Store the last element in a temporary variable

int last = arr[n-1];

• Move all the elements from k+1 to the last element to one position ahead

for (int i=n-1; i>k; i--)

arr[i] = arr[i-1];

• Restore the K_th element back to its original position

 arr[k] = last;

Implementation

In CPP

// CPP program to sort all array elements except one 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 code to sort all array elements except one
int main()
{
	int arr[] = {1, 40, 13, 17, 26, 29 };
	int k = 4;
	int sizeofarray = sizeof(arr) / sizeof(arr[0]);
	sortExceptK(arr, k, sizeofarray);
	for (int i = 0; i < sizeofarray; i++)
		cout << arr[i] << " ";
	return 0;
}

Output

1 13 17 29 26 40

Complexity analysis

Time complexity:

O(n*log(n)). Here, n is the length of the array. The complexity is of the order of nlog(n) because we have to sort all array elements except one. Sorting takes a time complexity of O(n*log(n)).  

Space complexity: 

O(1) as no extra space is used.

Frequently Asked Questions

What sorting algorithm does sort function in C++ use? 

A hybrid algorithm called introsort is used by the C++ sort function.

What is the time complexity of Sort()?

The time complexity of Sort() is O(NlogN), where N is the number of elements in the array.

What are some of the popular sorting methods in C++?

Some of the popular sorting methods in C++are Bubble Sort, Insertion Sort, Selection Sort, Quick Sort., and Merge Sort.

Conclusion

This blog discussed the solution to a famous sorting problem in which we sort all the elements of the array except the given element.

Recommended problems -

• Beautiful Array
• Product Array Puzzle

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. You must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!