i am getting wrong answer
but it runs fine in my netbeans compiler …
import java.util.Scanner;
class tsort {
private int[] numbers;
private int number;
public void sort(int[] values) {
// Check for empty or null array
if (values ==null || values.length==0){
return;
}
this.numbers = values;
number = values.length;
quicksort(0, number - 1);
for(int k = 0;k<numbers.length;k++)
{
System.out.println(numbers[k]);
}
}
private void quicksort(int low, int high) {
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = numbers[low + (high-low)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (numbers[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (numbers[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursion
if (low < j)
{
quicksort(low, j);
}
if (i < high)
{
quicksort(i, high);
}
}
private void exchange(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
class test3
{
public static void main(String[] args) {
int number[]= null;
int i ;
try
{
Scanner sc = new Scanner(System.in);
int l = sc.nextInt();
for( i=0;i<l;i++)
{
number[i]=sc.nextInt();
}
tsort t = new tsort();
t.sort(number);
}
catch(Exception e)
{
}
}
}
your code does not give ne o/p…as you had not created the array…this leads to an exception and you are jumping out of your try block…see this link for the corrected code!!!
@zargus Since @kunal361 answered array part, I will answer TLE part. In this problem value of T that is number of elements can go upto 10^6, so definitely a O(T*logT) approach(Quicksort) will timeout.
What you need is a better complexity algorithm. Can we do it in O(T)? Think Think…
Certianly we can. See max value of an element that is N can be 10^6. So we can create hash table of 10^6 elements (initialized to zero). As we input new element i we increment value at index i. At last we iterate from index 0 to index 10^6 and print each element number of times it has occured.
Example:
Since 10^6 is a large value I will consider 10 instead.
Create hast table:
int[] hash = new int[10+1];
Arrays.fill(hash,0);
Now consider input (3, 1, 10, 8, 4, 2, 2, 4)
Next step is to increment value of index i for input i:
yeah O(nlogn) complexity works in c…I used Heap Sort …But @argonaut nicely explained…Learned a implementation of hashtable!!Never thought of O(n) complexity in sorting…Will use this technique in compititions…
After reading your comment i have implemented this logic to solve Turbo Sort but in C my program took 1.27 sec to execute while First submission took 0.09 sec. Why is it so?
My code is:
#include<stdio.h>
#define gc getchar_unlocked
#define size 1000001
inline int sscan()
{int n=0,c=gc();
while(c<'0'||c>'9')
c=gc();
while(c<='9'&&c>='0')
{
n=n*10+c-'0';
c=gc();
}
return n;
}
static int hash[1000001]={0};
int main()
{
int i,t;
t=sscan();
while(t--)
{
int input;
input=sscan();
hash[input]++;
}
int j,x;
for(i=0;i<size;i++)
{
x=hash[i];
if(hash[i]!=0)
{
for(j=0;j<x;j++)
printf("%d\n",i);
}
}
return 0;
}
@argonaut >> could you please provide the full code of sorting through hash. i tried to implement but it is giving runtime error. coding language is java
For Java, you should always use the BufferedReader class as it is much,much faster than scanner.learn the syntax somewhere, it is pretty straightforward.For obtaining integers that are space separated,(BufferedReader only takes an entire line at a time),use the split(" ") function of the string class and then parse the string array elements one by one.Much better than scanner.You can also see some of my codes for more info.
@argonaut…that is true…but i have submitted this 1 without using hash tables…just by using normal sort…the only diff is slow nature of ip in java…i used C++ and it was AC with a time of 1 or 2 secs…NlogN will also pass…
Yes, a good approach in terms of time complexity. But, isn’t this a pretty inefficient use of memory? The range of numbers is up to 10^6. so we need to make an array of 10^6. now there will be a LOT of memory wastage in some cases, specially when there are same numbers repeating. example, let t=100, all 100 numbers are say 399(obviously might not be an actual input but, repetitions of numbers is what i am pointing at) . we have made an array of 10^6. but used only 1 means wastage of(10^6 - 1) locations!
@sunny_patel>>that is true…but the time taken is way less than what it is taken by sorting…see the very 1st submission on the problem page…he has used this method with fast output, by printing all the numbers at once!!!
@kunal361 , i did mention about it being good in terms of time! but then an algorithm must be judged on the basis of both time and space complexity, isn’t it? and the memory wastage here is real lot. If it would have been a little lesser i wouldn’t emphasize and argue on this point so much, but the difference can be considerable, is what i think! i never said this approach isn’t good But it may happen that in a competitive problem or in some real world application, this sorting array may actually take up more space than the actual logic! “fast” algo at the cost of memory is my only point
