Sort

• there are a lot of sort algorithms

• selection, bubble, insertion, quick, heap and merge sort ...

• use sort algorithm which has time complexity of O(NlgN)

• it's better to use sort in STL than making myself

• sort(begin, end)

• it sorts between begin and right before the end
• function that sorts begin, end
• it is usually used for sorting before solving problems

• implementation code in C++

int n = 10;
int a = {};
sort(a, a+n);

vector<int> a;
sort(a.begin(), a.end());

Sort Numbers 2

• boj.kr/2751

• sorting the number of N

• sort in Java (using built-in sort algorithm)

import java.io.IOException;
import java.util.Arrays;

public class Main {
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];

for(int i=0; i<n; i++){
}

Arrays.sort(arr);
StringBuilder sb = new StringBuilder();

for(int i=0; i<n; i++){
sb.append(arr[i] + "\n");
}

System.out.print(sb);
}
}

Sort Coordinates

• boj.kr/11650

• solution in Java
```java

import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

class Point implements Comparable<Point> {
int x, y;

Point(int x, int y) {
this.x = x;
this.y = y;
}

public String toString() {
return this.x + " " + this.y;
}

public int compareTo(Point that) {
if (this.x < that.x) {
return -1;
} else if (this.x == that.x) {
if (this.y < that.y) {
return -1;
} else if (this.y == that.y) {
return 0;
} else {
return 1;
}
} else {
return 1;
}
}
}

public class Main {
public static void main(String args[]) throws IOException {
int n = Integer.parseInt(br.readLine());
Point points[] = new Point[n];

for(int i=0; i<n; i++) {
String xy = br.readLine();
StringTokenizer st = new StringTokenizer(xy, " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
points[i] = new Point(x, y);
}

Arrays.sort(points);

StringBuilder sb = new StringBuilder();

for( Point p : points ){
sb.append(p.toString() + "\n");
}

System.out.println(sb.toString().trim());
}
}
```

Sort coordinates 2

• boj.kr/11651
• solution is almost the same as above one

Stable Sorting

• When there are some cards like this
• 7♠, 5♥, 2♥, 5♠
♦ ♣
• When cards are sorted in the order in which numbers are increasing
• how would be the order of 5♥ and 5♠
• it can be like
• 2♥, 5♥, 5♠, 7♠
• it retains the order of input (Stable)
• 2♥, 5♠, 5♥, 7♠
• it doesn't retain the order of input (Unstable)
• we couldn't expect what would be the first between heart and spade
• An alignment algorithm that retains the order before sorting when there is the same thing is called a Stable Sorting algorithm.
• Stable Sort Algorithm
• Merge Sort
• STL stable_sort

Order by age

• boj.kr/10814

• code in Java

import java.io.IOException;
import java.util.Arrays;

class Members implements Comparable<Members>{

int age;
int order;
String name;

Members(int age, String name, int order){
this.age = age;
this.name = name;
this.order = order;
}

@Override
public int compareTo(Members that) {
if(this.age < that.age){
return -1;
}else if(this.age == that.age){
if(this.order < that.order){
return -1;
}
else if(this.order > that.order){
return 1;
}
else{
return 0;
}
}
else if(this.age > that.age){
return 1;
}

return 0;
}

@Override
public String toString(){
return this.age + " " + this.name + "\n";
}
}

public class Main {
public static void main(String args[]) throws IOException {
int n = Integer.parseInt(br.readLine());
Members members[] = new Members[n];

for(int i=0; i<n; i++) {
String[] info = br.readLine().split(" ");
int age = Integer.parseInt(info);
String name = info;
members[i] = new Members(age, name, i);
}

Arrays.sort(members);

StringBuilder sb = new StringBuilder();

for( Members m : members ){
sb.append(m.toString());
}

System.out.print(sb);
}
}
• java doesn't have basic stable sort. so i just added order to class

• in C++, we can use tuple and make this with only one line of code

Korean English Mathematics

• sort but more complicated conditions

• code in java

import javax.print.DocFlavor;
import java.io.IOException;
import java.util.Arrays;

public class Main {

static class Student implements Comparable<Student>{
String name;
int korean;
int english;
int mathematics;

Student(String name, int korean, int english, int mathematics){
this.name = name;
this.korean = korean;
this.english = english;
this.mathematics = mathematics;
}

@Override
public int compareTo(Student that) {
if(this.korean == that.korean && this.english == that.english && this.mathematics == that.mathematics)
return this.name.compareTo(that.name);
else if(this.korean == that.korean && this.english == that.english)
return Integer.compare(that.mathematics, this.mathematics);
else if(this.korean == that.korean)
return Integer.compare(this.english, that.english);
else
return Integer.compare(that.korean, this.korean);
}
}

public static void main(String args[]) throws IOException {
int n = Integer.parseInt(br.readLine());
Student[] students = new Student[n];

for(int i=0; i<n; i++){
String[] info = br.readLine().split(" ");
students[i] = new Student(info, Integer.parseInt(info), Integer.parseInt(info), Integer.parseInt(info));
}

Arrays.sort(students);
StringBuffer sb = new StringBuffer();

for(int i=0; i<n; i++){
sb.append(students[i].name + "\n");
}

System.out.print(sb);
}
}