# TSORT: Getting wa

So, I used a quick sort to implement the problem in Java. It works fine for the given input set but gives wrong answer. Can someone help me please???

``````import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintStream;

public class Main {

public static int partition(int arr[], int left, int right){
int pivot=arr[(left+right)/2];
int i=left;
int j=right;
int temp;
while(i<=j){
while(arr[i]<pivot)i++;
while(arr[j]>pivot)j--;
if(i<=j){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
i++;
j--;}}
return i;}

public static void QuickSort(int arr[], int left, int right){
int index=partition(arr,left,right);
if(left<index-1)QuickSort(arr,left,index-1);
if(index<right)QuickSort(arr,index,right);}

public static void main(String[] args) throws IOException {
PrintStream ps = new PrintStream(System.out);
StringBuilder sb = new StringBuilder("");
int [] turbo=new int[t];
QuickSort(turbo,0,t-1);
for(int i=0;i<t;i++){
if(i==t-1)sb.append(turbo[i]).append("\n");
else{
if(turbo[i]!=turbo[i+1])
sb.append(turbo[i]).append("\n");}}
ps.println(sb);}
}``````
2 Likes

Try the input

``````4
1
1
2
2
``````

``````1
1
2
2
``````

you propably misunderstood `non decreasing order`, read more on wikipedia.

Two hints to you:

1. you don’t need to implement sort in Java, there are Collections.sort() and Arrays.sort() methods
2. quick sort in worst case has complexity O(n^2), so someone can challenge your solution in contests where it is possible to challenge (hack) solution.
3 Likes

You Picked the question in the wrong way.
The question is straight forward -You just have to sort the given data-set in ascending order.

But after analyzing your code ,i think you misunderstood that only one copy of the repeated members is to be printed .

No ,that’s not the case .

And here is the proof ,For the test case

``````10
5
3
5
6
7
1
9
7
3
2
``````

your code was generating the following output

``````1
2
3
5
6
7
9
``````

Clearly you were avoiding the printing of repeated members.

In order to fix it :

Just comment the three lines in printing steps as shown :

``````		QuickSort(turbo,0,t-1);
for(int i=0;i<t;i++){
//if(i==t-1)sb.append(turbo[i]).append("\n");//No need of it
//  else{
sb.append(turbo[i]).append("\n");
// }
}
ps.println(sb);}
}``````
5 Likes

@avengee - “print given numbers in non decreasing order.”. u considered it as strictly non decreasing order I guess.
@ritesh_gupta is correct , that’s the only bug ,your quick sort looks absolutely fine .

2 Likes

@ritesh_gupta: Thank you so much for the help. I didn’t submit yet because I have a small question.

So, in non-decreasing order an element can be either equal or greater than the previous element?

My question is with the example input and output set in the problem statement:

Example

Input:
5
5
3
6
7
1
Output:
1
3
5
6
7

This example has avoided repeated numbers. What is it? Or am I still mistaken about the definition of non-descending numbers?

@avengee: first number is not from the sequence, it is the sequence length

@belista: Thank you for your valuable tips. As I previously stated in the comment for above post, I’m confused with the example. Any help is greatly appreciated:).

Above or below is relative, answers are ordered by decreasing number of up votes and despite of that I answered first and ritesh_gupta copied answer 3 hours later he got more up votes…

@avengee :Read the problem statement once again,especially “Input t – the number of numbers in list, then t lines follow [t <= 10^6].Each line contains one integer: N [0 <= N <= 10^6]”.

So the First line 5 means there are 5 elements in the data set and these 5 elements are 5 3 6 7 1 .So our task is to sort the numbers 5 3 6 7 1

Thanks all:). I’m a new coder and sometimes I get so confused:). Thank you again for taking your valuable time to help me out for this simple question:).

Anyways, thank you again:)

pleasure:)

#include <stdio.h>

int v[1000001]={0};

int main()

{

int n,i,a;

scanf("%d",&n);

for (i=0;i<n; i++){ scanf("%d",&a); v[a]++; }

for (n=0;n<=1000000; n++) for (i=0;i<v[n];i++) printf("%dn",n);

return 0;

}

i am getting wrong answer on this code.