[ JAVA ] 정렬알고리즘

버블정렬, 선택정렬, 삽입정렬, 병합정렬, 퀵정렬

빅오표기법

• 알고리즘 성능을 판단하는 지표로써, 알고리즘의 수행 속도를 의미하는 시간 복잡도를 나타낸다.
• O(n) 의미 : 이 함수는 n만큼의 데이터가 주어졌을 때, “최악”의 경우 n만큼의 리소스를 소모한다

기본정렬

버블정렬 BobbleSort

• 정렬들 중 가장 비효율적인 정렬이지만 이미 정렬된 자료에서는 1번만 순회하면 되기 때문에 최선의 성능을 보여주는 알고리즘이다.

🔽 코드

---

삽입정렬 InsertionSort

• 주어진 자료의 모든 요소를, 앞에서부터 차례대로 / 정렬된 자료 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬이다.
• key 기준에서 <- 방향으로 비교 교환하는 것이 삽입정렬의 특징이라고 생각한다.
• O(n^2), 최선의 경우 전체 자료를 한번만 순회하면 되기에 O(n)의 시간 복잡도를 가진다.

🔽 코드

public class InsertionSort {
	
    public int[] sort(int[] arr) {
    
        // arr[1] 부터 key로 잡아서 뒤에서 앞으로 근접한 수를 하나씩 비교하면서 교환한다.  
        for (int i = 1; i < arr.length; i++) { // 바깥 for문은 내부 for문의 비교/교환 변수에 참견하지 않고
            for (int j = i; j > 0; j--) { // 배열의 -> 방향으로 차례대로 key 설정만 한다.  
                if (arr[j] < arr[j-1]) {
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                } 
                
            }
        }
        return arr;
    }

    public static void main(String[] args) {

        InsertionSort is = new InsertionSort();

        int[] arr = {8, 5, 6, 2, 4};

        System.out.println(Arrays.toString((is.sort(arr))));

    }

}