Algorithm Study #5 (Sort)

Jake Seo·2019년 3월 8일
0

java algorithm study

목록 보기
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[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);
            }
        }
profile
풀스택 웹개발자로 일하고 있는 Jake Seo입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. 프론트엔드: Javascript, React 백엔드: Spring Framework에 관심이 있습니다.

0개의 댓글