[알고리즘] 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬의 구현과 차이

선택 정렬

원소를 돌면서 작은 값은 선택하여 앞으로 보낸다.

선택 정렬의 과정은 다음과 같다.

예를 들어 숫자 5, 3, 8, 7, 9, 4, 6, 1, 2, 10으로 이루어져 있다고 가정하면

1) 원소들 중에 작은 값을 먼저 찾아 앞으로 보낸다.
5, 3, 8, 7, 9, 4, 6, 1, 2, 10 -> 1, 5, 3, 8, 7, 9, 4, 6, 2, 10

2) 다음 원소는 남은 숫자들 중 제일 값이 작은 것을 찾아 원소의 자리를 바꾼다.
1, 5, 3, 8, 7, 9, 4, 6, 2, 10 - > 1, 2, 3, 8, 7, 9, 4, 6, 5, 10

이렇게 반복하다 보면 결괏값은
1, 2, 3, 4, 5, 6, 7, 8, 9, 10으로 되었을 것이다.

- 소스코드

public class Main {
    public static void main(String[] args) {
        int min, index = 0, temp;
        int[] arr = {5, 3, 8, 7, 9, 4, 6, 1, 2, 10};

        for (int i = 0; i < arr.length; i++) {
            min = 999; //초기에 큰 값으로 설정해준다.

            for (int j = i; j < arr.length; j++) {
                //원소를 돌면서 작은 값을 찾아낸다.
                if (min > arr[j]) {
                    min = arr[j];
                    index = j;
                }
            }
            //찾아낸 작은 값을 temp에 저장
            temp = arr[i];
            //앞에서부터 작은 값을 채운다.
            arr[i] = arr[index];
            //치환된 큰 값을 기존에 있던 작은 값 인덱스에 넣는다.
            arr[index] = temp;
        }

	//1, 2, 3, 4, 5, 6, 7, 8, 9, 10
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

- 시간 복잡도
for 문을 중첩으로 두 번 돌렸기 때문에 O(n^2)이다.
비효율적이다.

버블 정렬

옆에 있는 값과 비교해서 큰 값을 뒤로 보낸다.

버블 정렬의 과정은 다음과 같다.

예를 들어 숫자 5, 3, 8, 7, 9, 4, 6, 1, 2, 10으로 이루어져 있다고 가정하면

1) 큰 값을 기준으로 옆에 있는 원소와 비교하여 작은 값을 앞으로 보내고 큰 값은 뒤로 간다.
5, 3, 8, 7, 9, 4, 6, 1, 2, 10 -> 3, 5, 8, 7, 9, 4, 6, 1, 2, 10

2) 위 과정을 반복한다.
3, 5, 8, 7, 9, 4, 6, 1, 2, 10 -> 3, 5, 7, 8, 9, 4, 6, 1, 2, 10

3, 5, 7, 8, 9, 4, 6, 1, 2, 10 - > 3, 5, 7, 8, 4, 9, 6, 1, 2, 10 - > 3, 5, 7, 8, 4, 9, 6, 1, 2, 10 - > 3, 5, 7, 8, 4, 6, 9, 1, 2, 10
...
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

과정을 보면 큰 값이 뒤로 가기 때문에 큰 값부터 정렬이 된다.

- 소스 코드

public class Main {
    public static void main(String[] args) {
        int temp;
        int[] arr = {5, 3, 8, 7, 9, 4, 6, 1, 2, 10};

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

        //1, 2, 3, 4, 5, 6, 7, 8, 9, 10
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

- 시간 복잡도
for 문을 중첩으로 두 번 돌렸기 때문에 O(n^2)이다.
하지만 자리를 교체해주는 과정이 있기 때문에 선택 정렬보다 비효율적이다.

삽입 정렬

원소가 앞의 원소와 비교하여 사이에 들어갈 때만 위치를 바꾼다. 즉, 선택 정렬과 버블 정렬보다 빠르다.

삽입 정렬의 과정은 다음과 같다.

예를 들어 숫자 5, 3, 8, 7, 9, 4, 6, 1, 2, 10으로 이루어져 있다고 가정하면

1) 앞의 원소를 비교하여 사이에 들어갈 수 있으면 삽입을 한다.
5, 3, 8, 7, 9, 4, 6, 1, 2, 10 -> 3, 5, 8, 7, 9, 4, 6, 1, 2, 10

3, 5, 8, 7, 9, 4, 6, 1, 2, 10 -> 3, 5, 7, 8, 9, 4, 6, 1, 2, 10

3, 5, 7, 8, 9, 4, 6, 1, 2, 10 -> 3, 5, 7, 8, 4, 9, 6, 1, 2, 10 -> 3, 5, 7, 4, 8, 9, 6, 1, 2, 10 -> 3, 5, 4, 7, 8, 9, 6, 1, 2, 10 -> 3, 5, 4, 7, 8, 9, 6, 1, 2, 10 -> 3, 4, 5, 7, 8, 9, 6, 1, 2, 10
...
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

- 소스 코드

public class Main {
    public static void main(String[] args) {
        int j, temp;
        int[] arr = {5, 3, 8, 7, 9, 4, 6, 1, 2, 10};

        for (int i = 0; i < arr.length - 1; i++) {
            j = i;
            while (j >= 0 && arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                j--;
            }
        }

        //1, 2, 3, 4, 5, 6, 7, 8, 9, 10
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

- 시간 복잡도
for 문을 중첩으로 두 번 돌렸기 때문에 O(n^2)이다.
하지만 필요할 때만 자리를 바꿔주기 때문에 버블 정렬과 선택 정렬보다 효율적이다.
또한 거의 정렬이 되어 있는 경우 굉장히 빠르다.

퀵 정렬

빠른 알고리즘으로 Pivot 값의 기준으로 큰 값과 작은 값으로 원소들을 분할하여 빠르게 정렬한다.

퀵 정렬의 과정은 다음과 같다.

예를 들어 숫자 5, 3, 8, 7, 9, 4, 6, 1, 2, 10으로 이루어져 있다고 가정하면

1) Pivot 값(5)을 기준으로 오른쪽으로는 Pivot 값보다 큰 값을 찾고 왼쪽으로 Pivot 값보다 작은 값을 찾는다.
5, 3, 8, 7, 9, 4, 6, 1, 2, 10

2) 그리고 이 둘을 바꾼다.
5, 3, 2, 7, 9, 4, 6, 1, 8, 10

3) 위 과정을 반복하다가 엇갈림(왼쪽의 값이 오른쪽의 값보다 작은 경우)이 발생한다.
5, 3, 2, 1, 4, 9, 6, 7, 8, 10

이럴 경우 4와 5의 위치가 바뀐다. 그러면 이 상황에서는 5가 정렬이 되었다.
4, 3, 2, 1, 5, 9, 6, 7, 8, 10
위 배열을 보면 알 수 있듯이 5를 기준으로 왼쪽은 5보다 작고 오른쪽을 5보다 큰 것을 알 수 있다.
그리고 5를 기준으로 분할한다.

4) 다시 Pivot 값은 4이다. 1의 과정을 다시 반복해보면
4, 3, 2, 1, 5
오른쪽으로 4보다 큰 값(5)을 찾고 왼쪽으로 4보다 작은 값(1)을 찾는다.

그런데 다시 엇갈림이 발생하였기 때문에
4와 1을 바꿔준다.
1, 3, 2, 4, 5
...
이 과정을 거치게 되면
1, 2, 3, 4, 5, 9, 6, 7, 8, 10이 된다.

5) 이번엔 다시 5를 기준으로 분할된 오른쪽 값(5, 9, 6, 7, 8, 10)을 위와 같은 방법으로 반복한다.
5, 9, 6, 7, 8, 10을
5를 기준으로 오른쪽으로 큰 값(9)과 왼쪽으로 작은 값(8)을 서로 교환해준다.
5, 8, 6, 7, 9, 10으로 될 것이고,

다시 진행을 하면
5를 기준으로 오른쪽으로 큰 값(8)과 왼쪽으로 작은 값(7)을 서로 교환해준다.
5, 7, 6, 8, 9, 10

다시 진행해준다.
5를 기준으로 오른쪽으로 큰 값(7)과 왼쪽으로 작은 값(6)을 서로 교환해준다.
5, 6, 7, 8, 9, 10

이제 결과값을 보면
1, 2, 3, 4, 5, 6, 7, 8, 9, 10으로 정렬된 것을 볼 수 있다.

- 소스 코드

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 7, 9, 4, 6, 1, 2, 10};
        quickSort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void quickSort(int arr[], int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = left;
        int i = left + 1;
        int j = right;
        int temp;

        while (i <= j) {
            while (arr[i] <= arr[pivot]) {
                i++;
            }
            while (arr[j] >= arr[pivot] && j > left) {
                j--;
            }
            if (i > j) {
                temp = arr[j];
                arr[j] = arr[pivot];
                arr[pivot] = temp;
            } else {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        
        quickSort(arr, left, j - 1);
        quickSort(arr, j + 1, right);
    }
}

- 시간 복잡도
평균 O(n lon n)이다.
하지만 Pivot 값에 따라 최악의 경우 O(N^2)다.