Sort an array which contain 1 to n values

Read

Discuss(30+)

You have given an array which contain 1 to n element, your task is to sort this array in an efficient way and without replace with 1 to n numbers.
Examples :

Input : arr[] = {10, 7, 9, 2, 8, 3, 5, 4, 6, 1};
Output : 1 2 3 4 5 6 7 8 9 10

Native approach :
Sort this array with the use of any type of sorting method. it takes O(nlogn) minimum time.

Efficient Approach (Using Cyclic Sort):

Idea:

The given array contains number in the range [1 to n] so we can use cyclic sort

Follow the steps mentioned below to solve the problem

Traverse the array
- Check if the array is at correct position
- Else swap the element to the element at its correct position

Below is the code implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std; 
 
// Function to sort the array 
void sort(int arr[], int n) 
{ 
  int i = 0; 
  while (i < n) { 
 
    // Finding the correct index 
    int correct = arr[i] - 1; 
 
    // Element index and value not match 
    // then swapping 
    if (arr[correct] != arr[i]) { 
 
      // Calling swap function 
      swap(arr[i], arr[correct]); 
    } 
    else { 
      i++; 
    } 
  } 
} 
 
// Function to swap values 
void swap(int& a, int& b) 
{ 
  int temp = a; 
  a = b; 
  b = temp; 
} 
 
// Driver Code 
int main() 
{ 
  int arr[] = {3, 2, 5, 6, 1, 4}; 
  int n = sizeof(arr) / sizeof(arr[0]); 
 
  // Function call 
  sort(arr, n); 
 
  // Printing the answer 
  for (int i = 0; i < n; i++) 
    cout << arr[i] << " "; 
  return 0; 
}
// This code contributed by Srj_27

Java

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.Arrays;
class GFG {
 
      // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 3, 2, 5, 6, 1, 4 };
         
          // Function call
          sort(arr);
 
        // Printing the answer
        System.out.println(Arrays.toString(arr));
    }
    static void sort(int[] arr)
    {
        int i = 0;
        while (i < arr.length) {
 
            // Finding the correct index
            int correct = arr[i] - 1;
 
            // Element index and value not match
            // then swapping
            if (arr[correct] != arr[i]) {
 
                // Calling swap function
                swap(arr, i, correct);
            }
            else {
                i++;
            }
        }
    }
 
    // Function to swap values
    static void swap(int[] arr, int first, int second)
    {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}
// This code is contributed by Karan Hora

Python3

# Function to sort the array
def sort(arr, n):
    i = 0
    while(i < n):
        # finding the corrent index
        correct = arr[i]-1
 
        # Element index and value not match
        # then swapping
        if arr[correct] != arr[i]:
            # calling swap function
            swap(arr, i, correct)
        else:
            i = i + 1
 
# function to swap values
def swap(arr, first, second):
    temp = arr[first]
    arr[first] = arr[second]
    arr[second] = temp
 
# Driver Code
arr = [3, 2, 5, 6, 1, 4]
n = len(arr)
 
# function call
sort(arr, n)
 
# printing the answer
for i in range(0, n):
    print(arr[i], end=" ")
 
# This code is contributed by Yash Agarwal(yashagarwal2852002)

Javascript

// Function to sort the array
     function sort(arr, n) {
       var i = 0;
       while (i < n) {
         // Finding the correct index
         var correct = arr[i] - 1;
 
         // Element index and value not match
         // then swapping
         if (arr[correct] != arr[i]) {
           // Calling swap function
           swap(arr, i, correct);
         } else {
           i++;
         }
       }
     }
 
     // Function to swap values
     function swap(arr, i, correct) {
       var temp = arr[i];
       arr[i] = arr[correct];
       arr[correct] = temp;
     }
 
     // Driver Code
 
     var arr = [3, 2, 5, 6, 1, 4];
     var n = 6;
 
     // Function call
     sort(arr, n);
 
     // Printing the answer
     for (var i = 0; i < n; i++) {
       console.log(arr[i]);
     }

C#

// C# code of the above approach
using System;
 
class MainClass
{
    // Function to sort the array
    static void sort(int[] arr, int n)
    {
        int i = 0;
       
        while (i < n)
        {
             // Finding the correct index
             int correct = arr[i] - 1;
 
             // Element index and value not match 
             // then swapping
             if (arr[correct] != arr[i])
             {
                // Calling swap function
                 swap(ref arr[i], ref arr[correct]);
             }
             else
             {
                 i++;
             }
        }
    }
 
    // Function to swap values
    static void swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 3, 2, 5, 6, 1, 4 };
        int n = arr.Length;
 
        // Function call
        sort(arr, n);
 
        // Printing the answer
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}
 
// This code is contributed by nikhilsainiofficial546

Output

[1, 2, 3, 4, 5, 6]

Time Complexity: O(n)
Auxiliary Space: O(1)

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 geeks!