[Java/알고리즘] 정렬 - 1

정렬 알고리즘은 알고리즘 과목 중 제일 기초가 되는 부분이다.
다양한 정렬 알고리즘이 있는데 해당 페이지에서는 시간복잡도 O(n^2)의
알고리즘을 알아보려고 한다.

O(n^2)의 시간복잡도

O(n^2)의 시간복잡도를 가진 정렬은 선택정렬, 버블정렬, 삽입정렬 3가지가 존재한다.

모두가 중첩 반복문을 통해 정렬된다는 공통점을 가지고 있다.

---

1.1 선택정렬 - 원리

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여
가장 작은 값을 찾아 첫 번째에 놓고,두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

	public static void main(String[] args) {
        int[] input = {13, 5, 11, 7, 23, 15};

        System.out.println(Arrays.toString(selection_sort(input)));
    }

    public static int[] selection_sort(int[] is){
        // 두개의 자료를 비교할때 작은 값의 index
        int idx = 0;
        // 스왑할때 필요한 변수
        int temp = 0;
        
        for(int i=0;i<is.length;i++){
            idx = i;
            for(int j = i+1; j<is.length; j++){
                if(is[idx]>is[j]) idx = j;
            }
            temp = is[i];
            is[i] = is[idx];
            is[idx] =  temp;
        }
        return is;
    }
    
    // is = [5, 7, 11, 13, 15, 23]

1.2 선택정렬 - 장점

• 자료 이동 횟수가 미리 결정된다.
• 알고리즘이 단순하고 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간이 필요하지 않는다.

1.3 선택정렬 - 단점

• 불안정 정렬이다.
• 시간 복잡도가 O(n^2)이다.

---

2.1 버블정렬 - 원리

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

	public static void main(String[] args) {
        int[] input = {13, 5, 11, 7, 23, 15};
        System.out.println(Arrays.toString(bubble_sort(input)));
    }

    public static int[] bubble_sort(int[] s){
        // 스왑할때 사용할 변수
        int temp = 0;
        
        // 
        for(int i=0; i<s.length-1;i++){
            for(int j=0;j<s.length-1-i;j++){
                // 제일 큰값을 마지막부터 채워가는 로직
                if(s[j]>s[j+1]){
                    temp = s[j];
                    s[j] = s[j+1];
                    s[j+1] =  temp;
                }
            }
        }

        return s;
    }
    
    // s = [5, 7, 11, 13, 15, 23]

2.2 버블정렬 - 장점

• 구현이 매우 간단하다.
• 이미 정렬된 데이터를 정렬할 때 빠르다.
• 안정정렬이다.

2.3 버블정렬 - 단점

• 역순 배열을 정렬할 때, 가장 느리다.
• 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
• 시간 복잡도가 O(n^2)이다.
• 다른 정렬에 비해 속도가 느리고 교환 횟수가 많다.

---

3.1 삽입정렬 - 원리

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

public static void main(String[] args) {
        int[] input = {11, 7, 5, 6, 10, 9};
        System.out.println(Arrays.toString(insertion_sort(input)));
    }
    
public static int[] insertion_sort(int[] s){
        // 삽입되는 값을 저장하는 변수
        int temp = 0;
        int j = 0;

        // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
        for(int i=1; i<s.length;i++){
            temp = s[i];
            // temp 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
            for(j=i-1; j>=0; j--){
                if(s[j]>temp){
                    s[j+1] = s[j];
                } else{
                    break;
                }
            }
            s[j+1] = temp;
        }


        return s;
    }
    
    // s = 

3.2 삽입정렬 - 장점

• 안정한 정렬 방법이다.
• 대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
• 최선의 경우 시간 복잡도가 O(n)까지도 나와서 선택이나 버블 정렬에 비하면 빠를 수 있다.

3.3 삽입정렬 - 단점

• 비교적 많은 레코드들의 이동을 포함한다.
• 비교할 수가 많고 크기가 클 경우에 적합하지 않다.
• 시간 복잡도가 O(n^2)이다.