기초 정렬 알고리즘

기본 정렬 알고리즘

종류 예시

- Bubble sort        ┒

- Insertion sort      ├  simple, slow

- Selection sort      ┘

- Quick sort        ┒

- Merge sort       ├  fast

- Heap sort         ┘

- Radix sort = O(N)

Selection Sort

- 각 루프마다

1) 최대 원소를 찾는다.

2) 최대 원소와 맨 오른쪽 원소를 교환한다.

3) 맨 오른쪽 원소를 제외한다.

- 하나의 원소만 남을 때까지 위 루프를 반복한다.

- 선택 정렬의 진행 과정

- 슈도 코드

selectionSort (A[], n) {

for last <- n downto 2 {//for루프는 n - 1번 반복한다.

A[1 ~ last] 중 가장 큰 수  a[k]를 찾음; //가장 큰 수를 찾기 위한 비교횟수 : n-1, n-2, ..., 2. 1번 순서로 줄어든다.

A[k]와 A[last]의 값을 서로 교환; //작업시간이 상수 시간으로 소요된다.}

}

- 시간 복잡도

k와 last간의 교환은 상수시간으로써 시간복잡도를 찾고자 하는 계산에 영향을 미치지 않고 결국 가장 큰 수를 찾기 위한 비교횟수에 따라 시간 복잡도가 갈리게 된다.

T(n) = (n - 1) + (n - 2) + ... + 2 + 1 = $\frac {n (n - 1)}{2} $ = O($n^2$)

- 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class SelectionSort {
    static BufferedWriter bw;
    
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write("선택 정렬을 수행할 정수들을 입력해주세요 : ");
        bw.flush();
        int index = 0;
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        int[] array = new int[st.countTokens()];
        int N = array.length - 1;
        
        while (st.hasMoreTokens())
            array[index++] = Integer.parseInt(st.nextToken());
        
        function(array, N);
        bw.write("정렬 결과는 " + Arrays.toString(array) + "입니다.");
        bw.close(); 
    }
    
    static void function (int[] array, int N) throws Exception {
        int max = array[0], save;
        
        for (int i = N; i >= 1; i--) {
            save = 0;
            
            bw.write(Arrays.toString(array) + "\n");
            bw.flush();
            
            for (int j = 0; j < i; j++) {
                if (max < array[j]) {
                    max = array[j];
                    save = j;
                }
            }
            
            if (save != i)
                exchange(array, save, N);
            
            N--;
            max = array[0];
        }
    }
    
    static void exchange (int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
}

Bubble Sort

- 정렬할 데이터 중 가장 큰 수를 찾아 가장 뒤에 옮기는 작업을 반복하는 알고리즘이나, Selection sort와는 다르게 마치 물방울이 수면 위로 올라오듯이 정렬을 수행한다.

- 버블 정렬의 진행 과정

- 슈도 코드

bubbleSort (A[], n) {

for last <- n downto 2

for i <- 1 to last - 1

if (A[i] > A[i + 1]) 

then A[i] <-> A[i + 1];

}

- 시간 복잡도

Selection과 수행 시간이 같아 시간 복잡도도 동일하다.

T(n) = (n - 1) + (n - 2) + ... + 2 + 1 = O($n^2$)

- 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BubbleSort {
    private static BufferedWriter bw;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write("버블 정렬을 수행할 정수들을 입력해주세요 : ");
        bw.flush();
        int index = 0;
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        int[] array = new int[st.countTokens()];
        int N = array.length - 1;
        while (st.hasMoreTokens())
            array[index++] = Integer.parseInt(st.nextToken());
        function(array, N);
        bw.write("정렬 결과는 " + Arrays.toString(array) + "입니다.");
        bw.close();
    }
 
    static void function(int[] array, int N) throws Exception {
        for (int i = N; i >= 1; i--) {
            bw.write(Arrays.toString(array) + "\n");
            bw.flush();
            for (int j = 0; j < N; j++) {
                if (array[j] > array[j + 1])
                    exchange(array, j, j + 1);
            }
            N--;
        }
    }
 
    static void exchange(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
}

Insertion Sort

- 최악의 경우 시간 복잡도는 Selection과 Bubble Sort와 별반 다르지 않으나, 평균적인 경우에는 대략 절반의 시간만 필요로 하여 앞의 두 정렬보다 효율적이라 할 수 있는 정렬법이다. 

- 삽입 정렬의 진행 과정

- 수 하나를 정렬하는 과정

- 슈도 코드

insertionSort (A[], n) {

for i <- 2 to n

A[1 ~ i]의 맞는 자리에 A[i]를 삽입;

}

- 시간 복잡도

for 루프는 n - 1번 반복한다.

A[i]를 삽입하는 절차는 최악의 경우 i - 1번 반복하게 된다.

최악의 경우 T(n) = (n - 1) + (n - 2) + ... + 2 + 1 = O($n^2$)

- 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class InsertionSort {
    static BufferedWriter bw;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write("삽입 정렬을 수행할 정수들을 입력해주세요 : ");
        bw.flush();
        int index = 0;
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        int[] array = new int[st.countTokens()];
        int N = array.length - 1;
        while (st.hasMoreTokens())
            array[index++] = Integer.parseInt(st.nextToken());
        function(array, N);
        bw.write("정렬 결과는 " + Arrays.toString(array) + "입니다.");
        bw.close();
    }
 
    static void function(int[] array, int N) throws Exception {
        int save;
        for (int i = 1; i <= N; i++) {
            bw.write(Arrays.toString(array) + "\n");
            bw.flush();
            save = array[i];
            for (int j = i - 1; j >= 0; j--) {
                if (save < array[j])
                    array[j + 1] = array[j];
                else if (save > array[j]) {
                    array[j + 1] = save;
                    break;
                }
                if (j == 0)
                    array[j] = save;
            }
        }
    }
}