[알고리즘/JAVA] 정렬 알고리즘 (선택/삽입/합병/퀵) & 구현

1. 선택 정렬 (Selection Sort)

선택 정렬은 가장 간단 하면서 비효율적인 정렬 알고리즘이다.

 

1. 배열에서 최소값(또는 최대값)을 찾는다.

2. 최소값(또는 최대값)을 배열의 맨 앞의 원소와 교환한다.

3. 정렬된 부분의 배열을 제외하고 나머지 배열에서 위 과정을 반복한다.

 

자바로 구현하기

import java.util.Scanner;

public class SelectionSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = Integer.parseInt(scanner.nextLine());
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = scanner.nextInt();
        }

        print(arr);
        sort(arr);
        print(arr);
    }

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

    private static void print(int[] arr) {
        System.out.print(">>");
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}

시간복잡도 

외부 루프는 n번 반복하고, 내부 루프는 각 외부 루프에 대해 n-i번 반복한다.

따라서 비교 횟수는 (n-1) + (n-2) + ... + 1 = n(n-1)/2 이고

시간복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)이다.

 

 

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬되지 않은 부분과 정렬된 부분으로 나누어 진행하는 알고리즘이다.

 

1. 배열의 첫 번째 원소를 정렬된 부분으로 간주한다.

2. 정렬되지 않은 부분에서 하나의 원소를 선택하여 정렬된 부분의 올바른 위치에 삽입한다.

3. 이를 배열의 끝까지 반복하여 정령을 완성한다.

 

자바로 구현하기

import java.util.Scanner;

public class InsertionSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = Integer.parseInt(scanner.nextLine());
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = scanner.nextInt();
        }

        print(arr);
        sort(arr);
    }

    public static void sort(int[] arr){
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int select = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > select) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = select;
            print(arr);
        }
    }

    public static void print(int[] arr){
        System.out.print(">>");
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}

 

실행 결과

 

시간복잡도

최선의 경우 (정렬된 배열이 주어질 때) : O(n)

최악의 경우 (역으로 정렬된 배열이 주어질 때) : O(n^2)

평균 : O(n^2)

 

 

3. 버블 정렬 ( Bubble Sort)

1.  배열의 첫 번째 원소부터 마지막 원소까지 반복하면서 인접한 두 원소를 비교한다.

2. 만약 현재 원소가 다음 원소보다 크다면, 두 원소의 위치를 서로 교환한다.

3. 한 번의 반복이 끝나면 가장 큰 원소가 배열의 마지막으로 이동한다.

4. 위의 과정을 반복한다.

자바로 구현하기

import java.util.Scanner;

public class BubbleSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = Integer.parseInt(scanner.nextLine());
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = scanner.nextInt();
        }
        sort(arr);
    }

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

    public static void print(int[] arr, int ord){
        System.out.print(ord + "번째 루프 >>");
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}

 

실행 결과

 

시간복잡도

최선의 경우 (이미 정렬된 배열의 경우) : O(n)

최악 및 평균의 경우 : O(n^2)

 

 

4. 합병 정렬 (Merge Sort)

합병 정렬은 분할 정복(divide and conquer) 알고리즘 중 하나이다.

배열을 반으로 나눈 후 각각의 배열을 재귀적으로 정렬한 후, 정렬된 부분 배열을 합쳐 전체 배열을 정렬하는 방식을 사용한다.

 

1. 분할(Divide) : 정렬되지 않은 배열을 반으로 나눈다.

2. 정복(Conquer) : 각각의 하위 배열에 대해 재귀적으로 합병 정렬을 수행한다.

3. 합병(Merge) : 정렬된 두 하위 배열을 합병하여 하나의 정렬된 배열로 만든다.

자바로 구현하기

import java.util.Arrays;
import java.util.Scanner;

public class MergeSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = Integer.parseInt(scanner.nextLine());
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = scanner.nextInt();
        }
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int start, int end) {
        if (start == end) {
            return;
        }
        sort(arr, start, (start + end) / 2);
        sort(arr, (start + end) / 2 + 1, end);
        merge(arr, start, end);
    }

    private static void merge(int[] arr, int start, int end) {
        int[] front = Arrays.copyOfRange(arr, start, (start + end) / 2 + 1);
        int[] back = Arrays.copyOfRange(arr, (start + end) / 2 + 1, end + 1);

        print(front, 0, front.length - 1, "front");
        print(back, 0, back.length -1, "back");

        int frontIndex = 0;
        int backIndex = 0;
        int sortArrIndex = start;
        while (frontIndex < front.length && backIndex < back.length) {
            if (front[frontIndex] < back[backIndex]) {
                arr[sortArrIndex++] = front[frontIndex++];
            } else {
                arr[sortArrIndex++] = back[backIndex++];
            }
        }
        while(frontIndex < front.length){
            arr[sortArrIndex++] = front[frontIndex++];
        }
        while(backIndex < back.length){
            arr[sortArrIndex++] = back[backIndex++];
        }
        print(arr, start, end, "merge");
    }

    public static void print(int[] arr, int start, int end, String str){
        System.out.print(str + " >>");
        while (start <= end) {
            System.out.print(" " + arr[start++]);
        }
        System.out.println();
    }
}

 

실행 결과

 

시간복잡도

합병 정렬의 시간 복잡도는 최선, 최악의 경우 모두 O(n logn)이다.

- 분할 하는 과정에서는 상수 시간이 소요되므로 O(1)

- 두 하위 배열을 합병하는 과정에서 O(n)

재귀 호출을 통해 배열을 계속해서 반으로 나누게 되므로, log n단계 만큼 수행하게 되고 총 시간 복잡도는 O(n log n)이 계산된다.

 

5. 퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복(divide and conquer) 알고리즘 중 하나이다.

평균적으로 매우 빠른 정렬 알고리즘이다.

특정 원소를 기준(pivot)으로 선택하고, 피봇 보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 분할하여 정렬하는 방식을 사용한다.

 

1. 피봇 선택 : 배열에서 임의의 원소를 선택하거나, 중간 원소를 선택하는 등의 방법으로 피봇을 선택한다.

2. 파티션 : 피봇을 기준으로 배열을 두 그룹으로 분할한다. 피봇보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 이동시킨다.

3. 재귀 호출 : 분할된 두 그룹에 대해 재귀적으로 퀵 정렬을 수행한다.

5. 정렬 완료 : 각 재귀 호출이 완료되면 전체 배열이 정렬된다.

자바로 구현하기

import java.util.Scanner;

public class QuickSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = Integer.parseInt(scanner.nextLine());
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = scanner.nextInt();
        }
        sort(arr, 0, arr.length - 1);
        print(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int start, int end){
        if(start >= end){
            return;
        }
        int pivotIndex = partition(arr, start, end);
        sort(arr, start, pivotIndex -1);
        sort(arr, pivotIndex + 1, end);
    }

    private static int partition(int[] arr, int start, int end) {
        int pivotIndex = end;
        int index = start;
        print(arr, start, end);
        for (int i = 0; i < end - start; i++) {
            if (arr[index] > arr[pivotIndex]) {
                int temp = arr[pivotIndex];
                arr[pivotIndex] = arr[index];
                arr[index] = arr[pivotIndex - 1];
                arr[pivotIndex - 1] = temp;
                pivotIndex--;
            } else {
                index++;
            }
        }
        return pivotIndex;
    }

    private static void print(int[] arr, int start, int end){
        System.out.print(">> ");
        for (int i = start; i <= end; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

 

시간복잡도

최선의 경우(피봇이 항상 중간값을 선택하는 경우) : O(n logn)

최악의 경우(이미 정렬된 배열에서 첫 번째 원소를 피봇으로 선택하는 경우) : O(n^2)

평균적인 경우 : O(n logn)

 

 

Java에서의 정렬

Java에서 정렬과 관련된 메서드는 무엇이 있을까?

배열 정렬 → Arrays.sort()

Dual-Pivot Quicksort 알고리즘을 통해 정렬한다.

One-Pivot Quicksort보다 빠르기 때문에 최악의 경우에도 O(n logn)의 시간복잡도를 가진다.

시간 복잡도 : O(n logn)

최악의 경우 : O(n logn)

리스트 정렬 → Collections.sort()

Tim sort 알고리즘을 통해 정렬한다.

시간 복잡도 : O(n logn)

최악의 경우 : O(n logn)

 

정렬 기준 → Comparator 인터페이스

객체의 정렬 기준을 제공하기 위한 함수형 인터페이스이다.

추상메서드인 int compare(T o1, T o2)를 오버라이딩 해서 Arrays.sort()와 Collections.sort()에 파라미터로 넘겨주면 

정렬 기준을 사용자화 할 수 있다.

Arrays.sort(arr, (o1, o2) -> Integer.compare(o1, o2));