01204212/integer sorting

This is part of 01204212.

You are given N integers (whose values are between -1,000,000,000 to 1,000,000,000). You want to sort them ascendingly.

Input/Output

Input

• First line: an integer N (1<=N<=100,000)
• The next N lines: each line contains one integer

Output

Output N lines of N integers in sorted order from the smallest to the largest.

Example

Input

5
10
2
300
25
7

Output

2
7
10
25
300

Test data

Download them at: http://theory.cpe.ku.ac.th/~jittat/courses/01204212/tasks/sortint/

Correct answer for n10.in

22
172
189
245
266
332
399
597
858
984

Correct answer for n1000.in (first 10 lines):

38
58
213
220
298
320
440
462
526
576

Correct answer for n10000.in (first 10 lines) (notes: if you use recursion, you might not be able to run on this big input):

71
83
131
188
261
265
368
399
464
495

Code

In this task, you can use Java Collections. Read about LinkedList, Iterator, ListIterator.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {

    LinkedList<Integer> inList;
    LinkedList<Integer> outList;
    int n;
    
    public static void main(String[] args) {
        Main m = new Main();
        
        m.readInput();
        m.process();
        m.output();
    }

    private void process() {
        outList = new LinkedList<Integer>();
    
        sortList(inList, outList);
    }

    private void output() {
        for(Iterator<Integer> i = outList.iterator(); i.hasNext();) {
            System.out.println(i.next());
        }
    }
    
    private void sortList(LinkedList<Integer> inList, LinkedList<Integer> outList) {
        // ... put your code here
    }

    private void readInput() {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        try {
            n = Integer.parseInt(reader.readLine());
            inList = new LinkedList<Integer>();
            
            for(int i=0; i<n; i++) {
                int x = Integer.parseInt(reader.readLine());
                inList.add(x);
            }
        } catch(Exception e) {
            System.out.println("Input error");
            n = 0;
            inList = null;
        }
    }
}

More codes

This section of codes are for Quicksort and Mergesort implementations.

Main template

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    int n;
    int[] x;
 
    public static void main(String[] args) {
        Main m = new Main();
 
        m.readInput();
        m.process();
        m.output();
    }
 
    private void process() {
    	sortArray(x);
    }
 
    private void output() {
    	for(int i=0; i<n; i++) {
    	    System.out.println(x[i]);
    	}
    }
 
    private void sortArray(int[] x) {
        // ... put your code here
    }
 
    private void readInput() {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );
 
        try {
            n = Integer.parseInt(reader.readLine());
            x = new int[n];

            for(int i=0; i<n; i++) {
                x[i] = Integer.parseInt(reader.readLine());
            }
        } catch(Exception e) {
            System.out.println("Input error");
            n = 0;
            x = null;
        }
    }
}

Merge procedure

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    int n;
    int[] x;
    int[] y;
    int[] z;
    
    public static void main(String[] args) {
        Main m = new Main();
 
        m.readInput();
        m.process();
        m.output();
    }
 
    private void process() {
        merge(x,y,z);
    }
 
    private void output() {
    	for(int i=0; i<n; i++) {
    	    System.out.println(x[i]);
    	}
    }
 
    private void merge(int[] x, int[] y, int[] z) {
    	// your code here
    }
 
    private void readInput() {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );
 
        try {
            n = Integer.parseInt(reader.readLine());
            x = new int[n];
            y = new int[n];
            z = new int[2*n];

            for(int i=0; i<n; i++) {
                x[i] = Integer.parseInt(reader.readLine());
            }
            for(int i=0; i<n; i++) {
                y[i] = Integer.parseInt(reader.readLine());
            }
        } catch(Exception e) {
            System.out.println("Input error");
            n = 0;
            x = null;
            y = null;
        }
    }
}