알고리즘 복습) 버블 정렬, 삽입 정렬, 선택 정렬

◇ 버블 정렬

앞에서부터 값의 크기를 비교하여

1. 오름차순일 경우에는 뒤에 가장 큰 값을 배치하고,

2. 내림차순일 경우에는 뒤에 가장 작은 값을 배치하는

정렬 알고리즘.

버블 정렬 알고리즘 시간 복잡도

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int[] arr1 = {3, 5, 2, 7, 1, 4};
        buffleSort1(arr1);
        System.out.println("[버블 정렬] 방식1 = " + Arrays.toString(arr1));

        int[] arr2 = {3, 5, 2, 7, 1, 4};
        buffleSort2(arr2);
        System.out.println("[버블 정렬] 방식2 = " + Arrays.toString(arr2));
    }

    static public void buffleSort1(int[] arr){
        for(int i=1; i<arr.length-1; i++){
            for(int j=0; j<arr.length-i; j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    static public void buffleSort2(int[] arr){
        for(int i=arr.length-1; i>0; i--){
            for(int j=0; j<i; j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

출력 결과

내림차순으로 정렬하기 원한다면 대소 비교를 바꿔주기만 하면 된다.

static public void buffleSortDescending(int[] arr){
    for(int i=arr.length-1; i>0; i--){
        for(int j=0; j<i; j++){
            if(arr[j]<arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

내림차순 출력

---

◇ 삽입 정렬

앞에 위치한 값은 이미 정렬이 되어있다고 가정하고, 이전 인덱스의 값과 비교하여 

1. 오름차순 기준 값이 작은 경우

2. 내림차순 기준 값이 큰 경우

스왑하는 형태의  알고리즘.

삽입 정렬 알고리즘 시간복잡도

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 7, 1, 4};
        insertionSort(arr);
        System.out.println("[삽입 정렬] 오름차순 = " + Arrays.toString(arr));

        insertionSortDescending(arr);
        System.out.println("[삽입 정렬] 내림차순 = " + Arrays.toString(arr));
    }

    static public void insertionSort(int[] arr){
        for(int i=1; i<arr.length; i++){
            for(int j= i; j>0; j--){
                if(arr[j]<arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
                else{
                    break;
                }
            }
        }
    }

    static public void insertionSortDescending(int[] arr){
        for(int i=1; i<arr.length; i++){
            for(int j= i; j>0; j--){
                if(arr[j]>arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
                else{
                    break;
                }
            }
        }
    }
}

출력 결과

---

◇ 선택 정렬

현재 정렬 대상 중 오름차순 기준 가장 작은 값, 내림차순 기준 가장 큰 값을 찾아 앞으로 스왑하는 형태의 알고리즘.

 

선택 정렬 알고리즘 시간복잡도

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 7, 1, 4};
        selectionSort(arr);
        System.out.println("[선택 정렬] 오름차순 = " + Arrays.toString(arr));

        selectionSortDescending(arr);
        System.out.println("[선택 정렬] 내림차순 = " + Arrays.toString(arr));
    }

    static public void selectionSort(int[] arr){
        for(int i=0; i<arr.length-1; i++){
            int min = i;
            for(int j = i+1; j<arr.length; j++){
                if(arr[j] < arr[min])
                    min = j;
            }

            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

    static public void selectionSortDescending(int[] arr){
        for(int i=0; i<arr.length-1; i++){
            int max = i;
            for(int j = i+1; j<arr.length; j++){
                if(arr[j] > arr[max])
                    max = j;
            }

            int temp = arr[i];
            arr[i] = arr[max];
            arr[max] = temp;
        }
    }
}