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;
}
}
}
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
