[알고리즘] 다양한 정렬 알고리즘

배열을 특정 기준으로 정렬해야 할 때 사용할 수 있는 정렬 알고리즘에 대한 정리 

모든 예시는 오름차순 기준으로 작성하였습니다. 

 

삽입정렬 

이중 반복문을 사용하여 기준점에서 배열의 앞쪽으로 가며 비교한다.

기준점 데이터와 비교하여 교환대상이면 앞의 인덱스와 데이터와 교환하며 반복문이 진행된다.

기준점의 위치는 기준점보다 큰 수가 없을 때까지 진행한다. 

public static int[] solution(int n, int[] arr) {
    for (int i = 0; i < n; i++) {
        int tmp = arr[i], j;
        for (j = i - 1; j >= 0; j--) { // 기준점의 한칸뒤에서 부터 시작 
            if (arr[j] > tmp) arr[j + 1] = arr[j]; 앞의 값이 더 크면 교환 
            else break; // 아니면 뒤에는 이미 정리되었기때문에 멈춰준다.
        }
        arr[j + 1] = tmp; // 멈춘 지점의 앞자리에 tmp 데이터를 넣어준다. 
    }
    return arr;
}

버블정렬

이중 반복문을 사용, 0번째 인덱스부터 시작하여 마지막 인덱스 전까지 실행한다. 

앞의 인덱스와 비교하여 교환대상이면 교환한다. 안쪽 반복문이 종료되면 정렬 대상이 맨 뒤로 빠졌으니 한 칸씩 범위를 줄여준다. 

public static int[] solution(int n, int[] arr) {
    for (int i = 0; i < n-1; i++) { // 마지막 인덱스 제외 
        for (int j = 0; j < n-i-1 ; j++) { // 실행 때 마다 한 칸씩 줄인다.
            if(arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j+1] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
    return arr;
}

선택정렬

이중 반복문을 사용하여 모든 데이터를 하나하나 비교하여 기준 데이터보다 작은 데이터의 인덱스를 갱신한다. 

반복문 종료 후 기준 인덱스와 비교 결과의 인덱스의 데이터를 교환한다. 

public static int[] solution(int n, int[] arr) {
    for (int i = 0; i < n-1; i++) {
        int idx = i;
        for (int j = i; j < n; j++) {
            if (arr[idx] > arr[j]) {
                idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = temp;
    }
    return arr;
}