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 ...
I would like you thank you for reminding me that i had codechef account which i had dumped long back.Here is the solution i did at that time it took me .20 seconds to run The code is little bit big Hope you find this useful thanks..
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.lang.reflect.Field;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
class Reader
{
private static final int BUFSIZE = 0x10000;
private final byte[] buffer = new byte[BUFSIZE];
private final ByteBuffer bb = ByteBuffer.wrap(buffer);
private final FileChannel channel;
int bufSize = -1; // non empty buffer
int bufOffset = 0; // non valid buffer
private FileInputStream getFileInputStream(InputStream in)
{
try
{
if (in instanceof BufferedInputStream)
{
Field field = in.getClass().getSuperclass().getDeclaredField("in");
field.setAccessible(true);
return (FileInputStream) field.get(in);
}
}
catch (Throwable e)
{
e.printStackTrace();
}
return (FileInputStream) in;
}
Reader(InputStream in) throws IOException
{
this.channel = this.getFileInputStream(in).getChannel();
}
void fetchBuffer() throws IOException
{
bb.clear();
bufSize = channel.read(bb);
bufOffset = 0;
}
boolean isFinished()
{
return bufSize <= 0;
}
private int peek() throws IOException
{
if (bufOffset < bufSize)
return buffer[bufOffset];
fetchBuffer();
if (bufSize > 0)
return buffer[0];
return -1;
}
private void skipSpace() throws IOException
{
int v = peek();
while (v <= ' ' && v != -1)
{
bufOffset++;
v = peek();
}
}
void nextLine() throws IOException
{
int v = peek();
while (v != -1 && v != '\n' && v != '\r')
{
bufOffset++;
v = peek();
}
if (v == '\r')
{
bufOffset++;
v = peek();
if (v == '\n')
bufOffset++;
}
else if (v == '\n')
{
bufOffset++;
v = peek();
if (v == '\r')
bufOffset++;
}
}
int readInt() throws IOException
{
skipSpace();
int result = 0;
int v = peek();
while (v > ' ')
{
result = result * 10 + v - '0';
bufOffset++;
v = peek();
}
return result;
}
}
class Writer
{
private static final int BUFSIZE = 0x10000;
private final FileOutputStream fos;
private final byte[] buffer = new byte[BUFSIZE];
private int offset = 0;
private FileOutputStream getFileOutputStream(PrintStream out)
{
try
{
Field field = out.getClass().getSuperclass().getDeclaredField("out");
field.setAccessible(true);
OutputStream os = (OutputStream) field.get(out);
if (os instanceof BufferedOutputStream)
{
BufferedOutputStream bos = (BufferedOutputStream) os;
field = bos.getClass().getSuperclass().getDeclaredField("out");
field.setAccessible(true);
return (FileOutputStream) field.get(bos);
}
return (FileOutputStream) field.get(out);
}
catch (Throwable e)
{
e.printStackTrace();
}
return null;
}
Writer(PrintStream out) throws IOException
{
fos = getFileOutputStream(out);
}
private static final int[] boundaries = new int[]
{
9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999
};
private static final int[] divs = new int[]
{
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000
};
private static final byte[] numbers = "0123456789".getBytes();
void writeln(int number) throws IOException
{
if (offset > BUFSIZE - 100)
flush();
int index;
for (index = 0; index < boundaries.length; index++)
if (number <= boundaries[index])
break;
for (; index >= 0; index--)
{
int mult = number / divs[index];
buffer[offset++] = numbers[mult];
number -= mult * divs[index];
}
buffer[offset++] = '\n';
}
void flush() throws IOException
{
if (offset > 0)
{
fos.write(buffer, 0, offset);
offset = 0;
}
}
}
class Solution {
public static void main(String[] args) throws java.lang.Exception {
Reader r=new Reader(System.in);
Writer w=new Writer(System.out);
int x,k;
int[] arr2 = new int[1000000];
x = r.readInt();
for (int i = 0; i < x; i++) {
arr2[r.readInt()]++;
}
for (int i = 0; i < 1000000; i++) {
k= arr2[i];
while(k-- > 0){
w.writeln(i);
}
}
w.flush();
}
}