버블 / 선택 / 삽입 / 퀵 / 병합 / 기수 정렬

1. 버블 정렬

: 데이터의 인접 요소끼리 비교하고, swap 연산을 수행해 정렬

: O(n^2)으로 다른 정렬 알고리즘보다는 속도가 느린 편

 

-> 첫번째 루프 결과 맨 끝의 1개 '60'은 정렬이 되었다고 볼 수 있음

-> 두번째 루프 결과 맨 끝의 2개 '42', '60'은 정렬이 되었다고 볼 수 있음

-> 루프 한번에 한개의 숫자가 정렬되므로 시간 복잡도는 N * N이 됨

 

 

백준 온라인 저지 2750번

import java.util.Scanner;

public class P2750_수정렬하기 {
    public static void start() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int arr[] = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = sc.nextInt();
        }

        // 버블 정렬 수행
        for(int i=0; i<N-1; i++) {
            for(int j=0; j<N-1-i; j++) { // N-1-i 중요 : 정렬되지 않은 영역 내에서만 루프 실행
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        for(int i=0; i<N; i++) {
            System.out.println(arr[i]);
        }
    }

}

* 자바에서 기본으로 제공하는 sort()의 시간 복잡도 : O(nlongn)

 

---

2. 선택 정렬

: 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하며 정렬

: 구현 방법이 복잡하고 시간복잡도가 O(n^2)로 높은 편이라 코테에서는 많이 사용하지 않음

: 최솟값이나 최댓값을 찾고, 남은 정렬 부분의 제일 앞의 데이터와 swap

 

 

백준 온라인 저지 1427번

import java.util.Scanner;

public class P1427_내림차순정렬 {
    public static void start() {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] arr = new int[str.length()];

        for(int i=0; i<str.length(); i++) {
            arr[i] = str.charAt(i) - '0';
        }

        for(int i=0; i<str.length(); i++) {
            int max = i; // 가장 앞의 값을 max라 설정
            for(int j=i+1; j<str.length(); j++) {
                if(arr[j] > arr[max]) {
                    max = j; // 탐색 중 max 보다 큰 값을 찾으면 max를 바꿔줌
                }
            }

            // 현재 i값 보다 max값이 더 크면 swap
            if(arr[i] < arr[max]) {
                int temp = arr[i];
                arr[i] = arr[max];
                arr[max] = temp;
            }
        }

        for(int i=0; i<arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

 

---

3. 삽입 정렬

: 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬

: 시간복잡도는 O(n^2)으로 느린편이지만 구현하기 쉬움

 

 

백준 온라인 저지 11399번

import java.util.Scanner;

public class P11399_ATM {
    public static void start() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int arr[] = new int[N];
        int sumArr[] = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = sc.nextInt();
        }

        // 삽입 정렬 수행
        for(int i=1; i<N; i++) {
            int insertPoint = i;
            int insertValue = arr[i];

            for(int j=i-1; j>=0; j--) {
                // 현재 i의 바로 앞칸부터 0까지 탐색
                if(arr[j] < arr[i]) {
                    insertPoint = j+1; // 자신보다 작은 값 한칸 뒤에 삽입해야 하므로 +1
                    break;
                }

                if(j==0) {
                    // 현재 값이 제일 작은 값일 경우 맨 앞에 삽입
                    insertPoint = 0;
                }
            }

            for(int j=i; j>insertPoint; j--) {
                // 삽입 위치에서 i까지 한칸씩 뒤로 밀기
                arr[j] = arr[j-1];
            }
            arr[insertPoint] = insertValue;
        }

        // 합배열 구하기
        sumArr[0] = arr[0];
        for(int i=1; i<N; i++) {
            sumArr[i] = sumArr[i-1] + arr[i];
        }

        int sum = 0;
        for(int i=0; i<N; i++) {
            sum += sumArr[i];
        }
        System.out.println(sum);
    }
}

 

---

4. 퀵 정렬

: 기준값 = pivot 을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬

: O(nlogn)

: 기준값 선정에 따라 시간복잡도에 큰 영향을 미침

 

 

---

5. 병합 정렬(중요)

: 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합치는 알고리즘

: O(nlogn)

: 여러 문제에서 응용됨

 

 

* 부분집합을 병합하며 정렬

 

 

* 2개의 부분집합을 병합하는 과정(투포인터 사용) : 중요!

-> 더 작은 포인터의 값을 배열에 저장하고 한칸 오른쪽으로 이동

 

 

백준 온라인 저지 2751번

import java.util.Scanner;

public class P2751_수정렬하기2 {
    static int tmp[] = null;
    static int arr[] = null;

    public static void start() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        arr = new int[N+1];
        tmp = new int[N+1];

        for(int i=1; i<=N; i++) {
            arr[i] = sc.nextInt();
        }

        // 병합 정렬
        mergeSort(1, N);

        for(int i=1; i<=N; i++) {
            System.out.println(arr[i]);
        }

    }

    private static void mergeSort(int s, int e) {
        if(e-s < 1) {
            return;
        }

        int m = s + (e - s) / 2; // 중간 인덱스

        mergeSort(s, m);
        mergeSort(m+1, e);

        for(int i=s; i<=e; i++) {
            // arr 배열을 tmp 배열로 복사해 사용
            tmp[i] = arr[i];
        }

        int k = s;
        int index1 = s;
        int index2 = m+1;

        while(index1 <= m && index2 <= e) {
            // 두 그룹을 병합
            // 양쪽 index가 가리키는 값을 비교하여 더 작은 수를 선택해 배열에 저장하고 선택된 데이터의 index를 오른쪽으로 한칸 이동

            if(tmp[index1] > tmp[index2]) {
                arr[k] = tmp[index2];
                k++;
                index2++;
            } else {
                arr[k] = tmp[index1];
                k++;
                index1++;
            }
        }

        // 한쪽 그룹이 모두 선택된 후 남아 있는 값 정리
        while(index1 <= m) {
            arr[k] = tmp[index1];
            k++;
            index1++;
        }
        while(index2 <= m) {
            arr[k] = tmp[index2];
            k++;
            index2++;
        }

    }
}

 

---

6. 기수 정렬(+ 계수 정렬)

: 값을 비교하지 않는 특이한 정렬

: O(kn), k는 데이터 자릿수를 의미

: 10개의 큐를 이용 -> 일의 자릿수 기준으로 배열 원소를 큐에 집어넣고 pop(), 십의 자릿수 기준으로 배열 원소를 큐에 집어넣고 pop().. 마지막 자릿수까지 반복

: 시간 복잡도가 가장 짧은 정렬로, 정렬 데이터 개수가 많을 때 사용

 

 

 

* 계수 정렬 조건

1. 데이터가 양수(자연수)여야 함

2. 데이터의 크기(값)이 작아야 함

 

 

백준 온라인 저지 10989번

import java.util.Scanner;

public class P10989_수정렬하기3 {
    static int output[] = null;
    static int arr[] = null;

    public static void start() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        arr = new int[N+1];
        output = new int[N+1];

        for(int i=1; i<=N; i++) {
            arr[i] = sc.nextInt();
        }

        // 1. 기수 정렬
        // radixSort(5);

        /*
        for(int i=1; i<=N; i++) {
            System.out.println(arr[i]);
        }
         */

        // 2. 계수 정렬
        // 2.1 데이터의 개수가 10000까지 이므로 100001 크기의 배열을 선언한다.
        int[] count = new int[100001];

        // 2.2 count 배열에 현재 index의 값을 1 증가시킨다.
        for(int i=1; i<=N; i++) {
            count[arr[i]]++;
        }

        // 2.3 count의 값이 1이 아닌 경우, 출력해준다.
        for(int i=0; i<count.length; i++) {
            if(count[i] != 0) {
                for(int j=0; j<count[i]; j++) {
                    System.out.println(i);
                }
            }
        }
    }

    private static void radixSort(int maxSize) {
        // maxSize : 최대 자리수
        int[] output = new int[arr.length];
        int jarisu = 1;
        int count = 0;

        while (count != maxSize) {
            int[] bucket = new int[10]; // 현재 자릿수들의 분포를 합 배열 형태로 알려주는 배열

            for (int i = 0; i < arr.length; i++) {
                bucket[(arr[i] / jarisu) % 10]++; // 일의 자릿수부터 시작
            }

            for (int i = 1; i < 10; i++) {
                bucket[i] += bucket[i - 1]; // 합 배열을 이용해 index 계산
            }

            for (int i = arr.length - 1; i >= 0; i--) {
                output[bucket[(arr[i] / jarisu % 10)] - 1] = arr[i];
                bucket[(arr[i] / jarisu) % 10]--;
            }

            for (int i = 0; i < arr.length; i++) {
                arr[i] = output[i];
            }

            jarisu = jarisu * 10; // 자릿수 증가
            count++;
        }
    }
}