Home » Data Structure » Array Data Structure

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