Data Structure/Algorithm Challenger IV

Replies

• 

  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.
  
  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

  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

  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
  main()
  {
  int a[50],i,n;
  printf("How many elements in the array?(<50)");
  scanf("%d",&n);
  printf("Enter the numbers");
  for(i=0;iAs 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

  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

  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

  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

  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

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