[알고리즘] JAVA 정렬

정렬

효율을 위해 필요하다!!

선택 정렬

• 가장 작은 데이터를 선택해 맨 앞으로 보내고 이를 반복.
• 가장 작은 데이터를 앞으로 보내는 과정을 n-1번 반복.
• O(n^2)으로 데이터 10,000개 이상은 느려짐.

삽입 정렬

• 첫 번째 자리는 정렬되어 있다고 판단하고 두 번째 자리부터 시작.
• 두 번째 데이터가 어떤 위치로 들어갈지 판단하고 첫 번째 보다 작은지 큰지 비교해 왼쪽 혹은 오른쪽에 삽입.
• 자신의 위치에서 한칸씩 아래로 내려가며 크기를 비교 후 삽입.
• O(n^2)으로 리스트가 정렬되어 있는 상태에서 선택 정렬보다 빠르게 동작하여 최선의 경우 O(n)까지 가능.

퀵 정렬

• 가장 많이 사용되는 알고리즘.
• 기준(Pivot) 데이터를 설정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈.
• 호어 분할 방식: 피벗을 첫 번째 데이터로 정함.
• 피벗을 설정한 뒤 왼쪽에서부터 피벗보다 큰 데이터를 찾고 오른쪽에서는 피벗보다 작은 데이터를 찾음.
• 두 데이터의 위치를 교환. 왼쪽과 오른쪽이 교차되는 순간 작은 데이터와 피벗의 위치를 변경함.
• 평균 O(NlogN)으로 위 정렬들 보다 데이터 개수가 많아질 수록 속도가 빨라짐.

자바 객체 정렬

1. Student 객체를 만들고 이름으로 정렬할 경우

• compareTo 함수에서 return 값이 마이너스가 나오면 other 객체보다 앞으로 정렬되고 플러스가 나오면 뒤로 정렬됨.

  class Student implements Comparable<Student>{
    public String name;
    public int score;
    public Student(String name, int score){
        this.name = name;
        this.score = score;
    }
    @Override
    public int compareTo(Student other) {
        return this.name.compareTo(o.name); // 오름차순. ㄱ ㄴ ㄷ 
        //return o.name.compareTo(this.name); // 내림차순. ㄷ ㄴ ㄱ
    }
  }

  2. 점수로 정렬할 경우

• 점수는 높은 점수일 수록 앞에 정렬한다고 하면 내림차순으로 정렬해야함.

    @Override
    public int compareTo(Student o) {
        return this.score - o.score; // 오름차순. 1 2 3
        //return o.score - this.score; // 내림차순. 3 2 1 
    }