Algorithm Study #5 (Sort)

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[10] = {};
	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)

  	```java
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
  
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n];
  
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(br.readLine());
            }
  
            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.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    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 {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            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.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        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 {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                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[0]);
                    String name = info[1];
                    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.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        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 {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                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[0], Integer.parseInt(info[1]), Integer.parseInt(info[2]), Integer.parseInt(info[3]));
                }

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

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

                System.out.print(sb);
            }
        }