Algorithm Study #5 (Sort)

jakeseo_me·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)
          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
    	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라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.

0개의 댓글