Given the list of numbers, you are to sort them in non decreasing order. 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] Output
Output given numbers in non decreasing order. Example
Input: 5 5 3 6 7 1 Output: 1 3 5 6 7
First implementation using literal int values and using the Arrays.sort() function that sorts the literals using the Quicksort Algo ( worst case n^2 , average case - nlogn )
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
int num = in.nextInt();
int[] n = new int[num];
for (int i = 0; i < n.length; i++) {
n[i] = in.nextInt();
}
Arrays.sort(n);
for (int i = 0; i < n.length; i++) out.println(n[i]);
out.close();
}
}
class InputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
The next implementation is storing and sorting the int literals as Integer objects and using the Arrays.sort() method that now sorts the Integer objects using the MergeSort algo that guarantees nlogn performance
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
import java.io.InputStream;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
int T = in.nextInt();
Integer[] ARR = new Integer[T];
for (int i = 0; i < T; i++) ARR[i] = in.nextInt();
Arrays.sort(ARR);
for (int i : ARR) out.println(i);
out.close();
}
}
class InputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
However the issue now is that as per logic, the mergesort algo ( i.e the Integer object sorting implementation ) should take less or equal time with respect to the Quicksort algo ) i.e the int literal sorting implementation is taking lesser time ...
Integer Object sorting implementation - 0.94sec int literal sorting implementation - 0.53sec
Am i missing something ? what is the reason for this excess time ? is it because of autoboxing and autounboxing ?!is that the reason for this excess time ...
