Sort an array which contain 1 to n values
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(or use inbuilt sorting method) it takes O(nlogn) minimum time.
Below is the code implementation of the above approach
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// Input array containing elements from 1 to n
vector<int> arr = { 3, 1, 4, 2, 5 };
sort(arr.begin(), arr.end());
cout << "Sorted array is : ";
for (int num : arr) {
cout << num << " ";
}
return 0;
}
import java.util.Arrays;
public class Main {
public static void main(String[] args)
{
// Input array containing elements from 1 to n
int[] arr = { 3, 1, 4, 2, 5 };
Arrays.sort(arr);
System.out.print("Sorted array is : ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
# Input list containing elements from 1 to n
arr = [3, 1, 4, 2, 5]
arr.sort()
print("Sorted array is :", *arr)
# This code is contributed by Ayush Mishra
// Function to sort an array
function main() {
// Input array containing elements from 1 to n
let arr = [3, 1, 4, 2, 5];
// Sorting the array
arr.sort((a, b) => a - b);
// Print the sorted array
process.stdout.write("Sorted array is : ");
arr.forEach(num => process.stdout.write(num + " "));
}
// Execute the main function
main();
Output
Sorted array is : 1 2 3 4 5
Time Complexity: O(n log n)
Auxiliary Space: O(1)
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:
#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
/*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
# 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)
// 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
// 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]);
}
Output
1 2 3 4 5 6
Time Complexity: O(n)
Auxiliary Space: O(1)
Contact Us