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.InputStreamReader;
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 {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		PrintStream ps = new PrintStream(System.out);
		StringBuilder sb = new StringBuilder("");
		int t=Integer.parseInt(f.readLine());
		int [] turbo=new int[t];
		for(int i=0;i<t;i++)turbo[i]=Integer.parseInt(f.readLine());
		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);}
}
1 Like

Try the input

4
1
1
2
2

the correct answer is

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{
				//if(turbo[i]!=turbo[i+1])//Wrong Answer due to this
				sb.append(turbo[i]).append("\n");
			   // }
			   }
		 ps.println(sb);}
}
4 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 :wink:

@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:).

I replied in ritesh_gupta’s answer.

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.
please someone help.