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)

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