I'm trying to solve the following question :
We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 1 to ‘n’ based on their creation sequence. This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’.
Write a function to sort the objects in-place on their creation sequence number in O(n)O(n) and without any extra space. For simplicity, let’s assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.
Eg :
Input : [2, 6, 4, 3, 1, 5]
Output : [1, 2, 3, 4, 5, 6]
My approach :
void sortInPlace(int *arr,int n){
for(int i=0;i<n;i++){
if(arr[i] != arr[arr[i]-1]){
swap(arr[i],arr[arr[i]-1]);
}
}
}
int main(){
int n;
cout<<"
Enter number of elements:";
cin>>n;
int arr[n];
cout<<"
Enter the elements :";
for(int i=0;i<n;i++){
cin>>arr[i];
}
sortInPlace(arr,n);
cout<<"
Sorted Array :";
for(int i = 0; i < n ; i++){
cout<<arr[i];
}
}
But, this doesn't produce the right results.
Actual solution :
The only difference I could find is the While loop that they have used.
The while loop in the solution has an extra iteration to increment the 'i' , whereas , My solution does it in a for loop without requiring additional iterations.
Example : My approach
Input : [1,5,6,4,3,2]
Output : [1,3,2,4,5,6]
Expected output : [1,2,3,4,5,6]
But, why doesn't it work ? Could someone please tell me if I am missing something ?
