삽입, 선택, 버블 정렬

삽입 정렬(Insertion Sort)

- 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬한다.

- 두 번째 키와 첫 번째 키를 비교해 순서대로 나열하고 이어서 세번째 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 방식이다.

- 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.

데이터 : 8 5 6 2 4

1회차 :  5 8 6 2 4

2회차 :  5 6 8 2 4

3회차 :  2 5 6 8 4

4회차 :  2 4 5 6 8

public class SortExample
{
    public static void main(String [] args)
    {
        String strQuestion = "85624";
        System.out.println("결과 : " + insertionSort(strQuestion));
    }

    private static String insertionSort(String question)
    {
        char [] arrCh = question.toCharArray();

        char select;
        for(int i = 1; i < arrCh.length; i++)
        {
            System.out.print(i+"회차 : ");
            System.out.println(arrCh);
            select = arrCh[i];
            int j = i;
            while (j > 0 && select < arrCh[j-1])
            {
                arrCh[j] = arrCh[j-1]; // <<왼쪽으로 밀기
                j--;
            }
            arrCh[j] = select; // 값 체인지
        }
        return new String(arrCh);
    }
}

선택 정렬(Selection Sort)

- 선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번재 레코드 위치에 놓고, 나머지(n - 1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식이다.

- 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.

데이터 : 8 5 6 2 4

1회차 :  2 5 6 8 4

2회차 :  2 4 6 8 5

3회차 :  2 4 5 8 6

4회차 :  2 4 5 6 8

public class SortExample
{
    public static void main(String [] args)
    {
        String strQuestion = "85624";
        System.out.println("결과 : " + selectionSort(strQuestion));
    }

    private static String selectionSort(String question)
    {
        char [] arrCh = question.toCharArray();
        char select;
        char min;
        int minPos;
        for (int i = 0; i<arrCh.length; i++)
        {
            System.out.print((i+1)+"회차 : ");
            System.out.println(arrCh);

            min = 0;
            minPos = -1;
            select = arrCh[i];
            for (int j = i; j < arrCh.length; j++)
            {
                if (j == i)
                {
                    min = arrCh[j];
                    minPos = j;
                } else {
                    if (min > arrCh[j])
                    {
                        min = arrCh[j];
                        minPos = j;
                    }
                }
            }
            if (select > min)
            {
                arrCh[minPos] = select;
                arrCh[i] = min;
            }
        }

        return new String(arrCh);
    }
}

버블 정렬(Bubble Sort)

- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 방식이다.

- 계속 정렬 여부를 플래그 비트로 결정한다.

- 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.

 

데이터 : 8 5 6 2 4

1회차 :  8 5 6 2 4 - 5 8 6 2 4 - 5 6 8 2 4 - 5 6 2 8 4 - 5 6 2 4 8

2회차 :  5 6 2 4 8 - 5 6 2 4 8 - 5 2 6 4 8 - 5 2 4 6 8

3회차 :  5 2 4 6 8 - 2 5 4 6 8 - 2 4 5 6 8

4회차 :  2 4 5 6 8 - 2 4 5 6 8

public class SortExample 
{
    public static void main(String[] args) 
    {
        String strQuestion = "85624";
        System.out.println("결과 : " + bubbleSort(strQuestion));
    }

    private static String bubbleSort(String question)
    {
        char [] arrCh = question.toCharArray();
        int count = 1;
        int i = arrCh.length-1;
        while(i > 0)
        {
            System.out.print(count+"회차 : ");
            System.out.println(arrCh);
            for (int j = 0; j < i; j++)
            {
                char select = arrCh[j];
                if (select > arrCh[j+1])
                {
                    arrCh[j] = arrCh[j+1];
                    arrCh[j+1] = select;
                }
            }
            i--;
            count++;
        }

        return new String(arrCh);
    }
}

 

전체 코드 : https://github.com/hinos-repo/Algorithm/blob/master/Java/Algorithm/src/sort/SortExample.java