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<2*n; i++) {
    	    System.out.println(z[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;
        }
    }
}

Test data

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

output for n10.in

9518
9773
13550
16202
19018
21364
23100
41323
50386
52901
54817
59660
60935
72203
76136
81658
82595
96681
98951
99783

output for n1000.in (first 20 lines)

544
254319
390209
450482
524808
538705
540179
587455
593714
732355
833118
917092
937963
953946
972253
1007653
1135211
1162167
1196548
1229227

Quick sort

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() {
    	quickSort(x, 0, n-1);
    }

    private void swap(int i, int j) {
    	int tmp = x[i];
    	x[i] = x[j];
    	x[j] = tmp;
    }
    
    private void quickSort(int[] x, int left, int right) {
    	if(left >= right) {
    		return;
    	}
    	int pivot = x[right];

    	int mid = partition(x, left, right-1, pivot);
    	swap(mid, right);
    	
    	quickSort(x, left, mid-1);
    	quickSort(x, mid+1, right);
    }

    private int partition(int[] x, int a, int b, int pivot) {
    	// your code here...
    	return 0;
    }
    
    private void output() {
    	for(int i=0; i<n; i++) {
    		System.out.println(x[i]);
    	}
    }
 
    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;
        }
    }
}