Sort

N^2 : bubble, selection, insertion

NlogN : quick, merge, heap

 

quick

  평균적으로 nlogn을 보장하지만 최악의 경우 n^2이다.

  pivot을 2로 잡고 왼쪽에는 2보다 작은 것들을 오른쪽에는 큰 것들을 위치시키다.

  높이가 NlogN이고 길이가 N이라서 NlogN 이 된다. pivot을 2로 잡으 왼쪽이 짧아지고 오른쪽이 길어져 valance가 깨지게 된다. valance가 나쁠수록 높이가 길어진다. 따라서 pivot을 잘 정해야한다. 

 

merge

  nlogn을 보장

 무조건 반씩 자른다.

 

heap

  최소 정렬하고 빼오고 rearrange 하여 또 빼오고 하는 과정이 있다.

import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        int[] a = new int[100];
//        Arrays.sort(a); -> quick sort -> worst case O(n^2)
        // quick sort가 싫다면 Wrapper Class 이용
        Integer[] wrapA = new Integer[100];
//        Arrays.sort(a); -> merge sort
//        Collections.sort(list); -> Collection을 Array로 변환해서 merge sort

    }
}

Library Sort 사용해보기

Library Sort 는 자바의 'Collections.sort()' 메서드를 사용하여 정렬하는 방법이다. 이 메서드는 기본적으로 객체의 natural ordering을 사용하여 정렬한다. 

- Natural Ordering(자연적 순서)는 자바에서 정렬을 할 때 기본적으로 사용되는 순서를 의미한다.

  자바에서 정렬을 위해 'Collection.sort()'나 'Arrays.sort()'를 호출할 때, 기본적으로 객체의 'Comparable' 인터페이스를 구현한 클래스의 'compareTo()' 메서드를 사용하여 정렬 순서를 결정한다. 'Comparable'인터페이스는 정렬에 필요한 기준을 정의하고 있으며, 객체가 이 인터페이스를 구현하면 해당 객체들을 natural ordering으로 정렬할 수 있다.

 

import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;

public class Main {
    static class Info{
        int num1;
        int num2;

        public Info(int num1, int num2) {
            this.num1 = num1;
            this.num2 = num2;
        }
    }

    static class CustomComparator implements Comparator{

        @Override
        public int compare(Object o1, Object o2) {
            return 0;
        }
    }

    public static void main(String[] args) throws IOException {
        Info[] a = new Info[6];
        a[0] = new Info(10, 3);
        a[1] = new Info(1, 30);
        a[2] = new Info(2, 3);
        a[3] = new Info(1, 13);
        a[4] = new Info(20, 3);
        a[5] = new Info(12, 3);

        // 1. Comparator : 연산자
        // 2. Comparable : 비교가능한 데이터로 만드는 것

        Arrays.sort(a, new Comparator<Info>() {
            @Override
            public int compare(Info o1, Info o2) {
                if (o1.num1 > o2.num2){
                    return 1;
                } else if(o1.num1 < o2.num2){
                    return -1;
                } else {
                    if(o1.num2 > o2.num2){
                        return 1;
                    } else if(o1.num2 < o2.num2){
                        return -1;
                    }
                }
                return 0;
            }
        });

        TreeSet<Info> set = new TreeSet<>(new Comparator<Info>() {
            @Override
            public int compare(Info o1, Info o2) {
                return 0;
            }
        });
        System.out.println(Arrays.toString(a));
    }
}

 

import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    static class Info implements Comparable<Info> {
        int num1;
        int num2;

        public Info(int num1, int num2) {
            this.num1 = num1;
            this.num2 = num2;
        }

        @Override
        public int compareTo(Info other) {
            // num1을 기준으로 비교하고, num1이 같을 경우 num2를 기준으로 비교한다.
            if (this.num1 > other.num1) {
                return 1;
            } else if (this.num1 < other.num1) {
                return -1;
            } else {
                if (this.num2 > other.num2) {
                    return 1;
                } else if (this.num2 < other.num2) {
                    return -1;
                }
            }
            return 0;
        }
    }

    public static void main(String[] args) throws IOException {
        Info[] a = new Info[6];
        a[0] = new Info(10, 3);
        a[1] = new Info(1, 30);
        a[2] = new Info(2, 3);
        a[3] = new Info(1, 13);
        a[4] = new Info(20, 3);
        a[5] = new Info(12, 3);

        Arrays.sort(a);

        System.out.println(Arrays.toString(a));
    }
}