# Algorithm Study #5 (Sort)

jakeseo_me·2019년 3월 8일
0

목록 보기
13/18

## 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.BufferedReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
public static void main(String[] args) throws IOException {
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
	import java.io.BufferedReader;
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 {
Point points[] = new Point[n];

for(int i=0; i<n; i++) {
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.BufferedReader;
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 {
Members members[] = new Members[n];

for(int i=0; i<n; i++) {
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 {
Student[] students = new Student[n];

for(int i=0; i<n; i++){
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);
}
} 대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.