Data Structure/Algorithm Challenger IV

@pradeep-agrawal-rhdX5z • Oct 15, 2024

Oct 15, 2024

2.6K

This is a simple but trick one.

Consider an array of size ‘n’. Array containing all numbers from 1 to n exactly once but distributed randomly across the array.

Write a function to sort the array. Try to provide a optimized solution so that the order of the algorithm used is small.

For example, consider that array is of size 10. So it will containing values from 1 to 10 exactly once. Lets say that the values from 1 to 10 are are randomly distributed as
2 5 9 1 4 7 3 6 10 8
Then sorting the array should give
1 2 3 4 5 6 7 8 9 10

-Pradeep

Like 0 Replies 8

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

CrazyEngineers powered by Jatra Community Platform

shalini_goel14

@shalini-goel14-ASmC2J • May 19, 2009

Assuming it is not asked in C/C++ 😐,my program is in Java . As far as I know, its complexity is O(n log n). Correct me if any wrong concepts.

I would go for following approach in modern and advanced scenario.

/*
 * ArraySorting.java
 */
package myjava;
 
import java.util.Arrays;
/**
 *
 * @author shalinig
 */
public class ArraySorting {
 
    public static void main(String[] args){
        Integer[] integerArray= {23, 34, 345, 843, 12, 234, 567 };
 
        System.out.print("Array before sorting [ ");
        for(Integer i:integerArray){
            System.out.print(i+" ");
        }
 
        System.out.println("]");
        Arrays.sort(integerArray);
        System.out.print("Array after sorting [ ");
        for(Integer j:integerArray){
            System.out.print(j+" ");
        }
        System.out.println("]\n");
    }
 
 
}

Output:

Array before sorting [ 23 34 345 843 12 234 567 ]
Array after sorting [ 12 23 34 234 345 567 843 ]

Thanks !

pradeep_agrawal

@pradeep-agrawal-rhdX5z • May 19, 2009

shalini_goel14
Assuming it is not asked in C/C++ 😐,my program is in Java . As far as I know, its complexity is O(n log n). Correct me if any wrong concepts.
Yes, you can write a java code also.

The code that you have given do sorting of the array using the Java API which might be implementing some algorithm of complexity O(n log n).

My problem statement was actually a bit different then just sorting of some data.

I mean to say that user has array of size n which contains value from 1 to n exactly once but is distributed randomly across the array. And this data need to be sorted.

Probably i was not clear in defining the problem statement at first step. My apologies for that. I have updated the problem statement.

Let see how much optimal solution CE can give for it.

-Pradeep
silverscorpion

@silverscorpion-iJKtdQ • May 20, 2009
well, for this you don't need a program at all. If I'm not wrong, we need to sort an array with n elements, ranging from 1 to n. All elements from 1 till n are present in the array. So, if you sort the array, whichever algorithm you use, the resulting sorted array is gonna have all elements from 1 to n.

So, you just hat the size of the array as the input and fill the numbers yourself. Something like this would do the job.
```
#include<stdio.h>
main()
{
int a[50],i,n;
printf("How many elements in the array?(<50)");
scanf("%d",&n);
printf("Enter the numbers");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
a[i]=i+1;
printf("The sorted array is\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
```
As I type this, I myself feel so foolish and idiotic.But still, I think this is the best solution for the above problem. ie,. All I'm saying is, this doesn't require any real sorting. Hope I'm clear, and hope I'm correct!!
pradeep_agrawal

@pradeep-agrawal-rhdX5z • May 20, 2009

silverscorpion
I think this is the best solution for the above problem. ie,. All I'm saying is, this doesn't require any real sorting. Hope I'm clear, and hope I'm correct!!
Yes you are correct and this is the solution i was expecting.

The trick here was to to just assign value from 1 to n sequentially instead of doing a sorting. That complexity here is of order (n).

-Pradeep
shalini_goel14

@shalini-goel14-ASmC2J • May 20, 2009

Well done Scorpion, but can anyone tell me in what scenarios do anyone ned to use such approach? I mean when he knows how many elements(eg. 50 here) then why he is placing them randomly and then foolishly updating. He could simply create a sorted array in the beginning only right?
Corpse-Thrust

@corpse-thrust-NpL92W • May 20, 2009

shalini_goel14
Well done Scorpion, but can anyone tell me in what scenarios do anyone ned to use such approach? I mean when he knows how many elements(eg. 50 here) then why he is placing them randomly and then foolishly updating. He could simply create a sorted array in the beginning only right?
Hello 😁

From what I decipher, this example is just a special case of a general algorithm, nothing else. If we know we're gonna get an input of 1 to n numbers in an array of n elements, without any break or missing numbers, this method could be used. Otherwise I doubt it has any utility at all, as it won't be able to sort a more general array...
pradeep_agrawal

@pradeep-agrawal-rhdX5z • May 21, 2009

Yes, this does not have a utility. I posted this question to see how many people read question carefully and give it a thought before jumping to solution.

When i ask these questions in interview, the first answer of many people is that they will use quick sort algorithm to sort such array for an optimized solution.

-Pradeep
silverscorpion

@silverscorpion-iJKtdQ • May 21, 2009

Oh, so I answered an interview question correctly.. wow!!