[Algorithm] 정렬(Sorting)

Jay Lee·2023년 1월 1일

Sorting의 종류

선택 정렬 (Selection Sort)
버블 정렬 (Bubble Sort)
삽입 정렬 (Insertion Sort)
퀵 정렬 (Quick Sort)
합병 정렬 (Merge Sort)
힙 정렬 (Heap Sort)

선택 정렬 (Selection Sort)

정의
0번째 인덱스부터 마지막 인덱스까지 순회하면서 가장 작은 값을 해당 위치로 옮기는 것을 반복한다.

구현

public void bubbleSort(int[] arr) {
        for (int i=0; i < arr.length; i++) {		// n
            int min = arr[i];
            int minIdx = i;
            for (int j=i; j < arr.length; j++) {	// n
                if (min > arr[j]) {
                    min = arr[j];
                    minIdx = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }

시간복잡도

\displaystyle 시간복잡도 \displaystyle = n \ +\ (n-1)\ +\ (n-2)\ +\ .....\ +\ 2

\displaystyle = {(n-1)(n+2) \over 2}

\displaystyle = O(n^2)

항상 n개의 index에 따라 배열의 길이 - index의 개수만큼의 원소를 확인해야하기 때문에 항상 O(n2)의 시간복잡도를 가진다.

버블 정렬 (Bubble Sort)

정의
0번째 인덱스부터 n-1인덱스까지 돌면서 바로 오른쪽 원소와 비교하여 더 작은 값을 왼쪽으로 옮긴다. 이를 n번만큼 반복하여 정렬한다.

구현

public void bubbleSort(int[] arr) {
    for (int i=0; i < arr.length; i++) {		// n 
        for (int j=0; j<arr.length-1; j++) {	// n 
            if (arr[j+1] < arr[j]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}