# Sort an array that contains 1 to N elements

C++ implementation to sort an array that contains 1 to N elements.
Submitted by Vikneshwar GK, on January 20, 2022

Consider an array of size n and it contains values only from 1 to N. For example, if N=5, the array contains elements 1, 2, 3, 4, and 5. The task at hand is to sort this array in a time-efficient manner.

Example:

```Input:
test1[] = {8, 5, 4, 9, 3, 7, 6, 1, 2, 10}

Output:
test1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
```

Solution 1: Sorting the Array

This is a usual approach to solve this problem, i.e., sorting the given array using an O(nlog(n)) algorithm.

C++ Implementation:

```#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}

// Main function
int main()
{
int array[100], N;
cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}

// sorting the array
sort(array, array + N);

cout << "Sorted Array" << endl;
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 5
Enter element 1:4
Enter element 2:3
Enter element 3:2
Enter element 4:1
Enter element 5:5
Sorted Array
1 2 3 4 5
```

Solution 2: Index Replacement

This is a simple yet efficient approach for the given problem statement as it just takes a time complexity of O(n). The approach is to iterate through the array and replace every element with its index position (index+1), in such a way that the array will be automatically sorted at the end of the iteration.

C++ Implementation:

```#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void indexReplacement(int array[], int length)
{
// iterating through the array
for (int i = 0; i < length; i++) {
// replacing the element with index
array[i] = i + 1;
}
}

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}

// Main function
int main()
{
int array[100], length;
cout << "Enter Number of elements: ";
cin >> length;

for (int i = 0; i < length; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}

// sorting the array
indexReplacement(array, length);

cout << "Sorted Array" << endl;
printArray(array, length);

return 0;
}
```

Output:

```Enter Number of elements: 10
Enter element 1:8
Enter element 2:5
Enter element 3:2
Enter element 4:3
Enter element 5:6
Enter element 6:9
Enter element 7:7
Enter element 8:4
Enter element 9:1
Enter element 10:10
Sorted Array
1 2 3 4 5 6 7 8 9 10
```