쉘 정렬

JAVA로 작성되었습니다.

쉘 정렬

• 삽입 정렬을 개산한 알고리즘, 바탕은 삽입정렬을 기본으로 진행한다.
• 가까운 위치에 삽입되는 (어느정도 정렬이 되어있는) 삽입정렬이 빠른 것을 이용하여 삽입정렬을 하기 전 배열을 어느정도 정렬한 상태에서 삽입정렬을 진행하는정렬 방식이다.
• 이때 gap이라는 것이 존재하는데 gap만큼 배열을 띄엄띄엄 정렬하는데 사용한다.

 

1. 갭을 설정한다. 갭의 값은 이전 갭의 절반으로 설정한다.
   (초기 값은 배열의 크기 / 2 로 설정한다)
   (홀수를 권장하므로 2로 나누었을 때 짝수가 나온다면 +1을 하여 홀수로 정한다.)
2. 원본 배열에서 다음 요소와 인덱스의 차이가 gap만큼 있는 부분 배열들을 생성한다.
   (리스트의 길이가 11(0~10)이고 갭이 5라면
   (0, 5, 10), (1, 6), (2, 7), (3, 8), (4, 9))
3. 부분 배열들을 각각 삽입정렬해준다.
4. 각각의 부분들의 정렬이 완료되면 다음 갭 (나누기 2)으로 부분 삽입정렬을 다시 실행한다.
5. 갭이 1이 될 때까지 정렬을 진행한다. ( = 어느정도 정렬된 배열의 삽입정렬)

정렬 시각화

- 1

6	2	4	0	2	5	1	8	7	4	10
6					5					10
	2					1
		4					8
			0					7

->

5	1	4	0	2	6	2	8	7	4	10
5					6					10
	1					2
		4					8
			0					7
				2					4

- 2

5	1	4	0	2	6	2	8	7	4	10
5			0			2			4
	1			2			8			10
		4			6			7

->

0	1	4	2	2	6	4	8	7	5	10
0			2			4			5
	1			2			8			10
		4			6			7

- 3

0	1	4	2	2	6	4	8	7	5	10
0	1	4	2	2	6	4	8	7	5	10

->

0	1	2	2	4	4	5	6	7	8	10

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class ShellSort {
    public int[] array_selection(int[] arr, int gap, int start_index) {
        for (int i = start_index + gap; i < arr.length; i += gap) {
            int j, value = arr[i];
            for (j = i - gap; j >= start_index && arr[j] > value; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = value;
        }

        return arr;
    }

    public int[] array_shell(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            if (gap % 2 == 0) { gap++; }

            for (int i = 0; i < gap; i++) {
                ShellSort shellSort = new ShellSort();
                arr = shellSort.array_selection(arr, gap, i);
            }
        }

        return arr;
    }

    public List<Integer> list_shell(List<Integer> list, int prev_gap) {
        // 이전 gap의 절반을 gap으로 설정, 짝수가 나오면 +1을 하여 홀수로 설정
        int gap = (prev_gap  % 2 == 0) ? prev_gap / 2 + 1 : prev_gap / 2;
        // 0부터 +gap 한 애들 삽입정렬
        // 그렇다면 갭의 크기만큼 반복문이 있겠지?
        for (int i = 0; i < gap; i++) {
            // 리스트의 길이가 10(0~9)이고 갭이 5라면
            // (0, 5), (1, 6), (2, 7), (3, 8), (4, 9) 다섯번 반복하는 삽입정렬
            // ex) 0과 5를 삽입정렬 -> 1과 6을 삽입정렬 -> ...
           for (int j = i + gap; j < list.size(); j += gap) {
               int k, value = list.get(j);
               for (k = j - gap; k >= i && list.get(k) > value; k -= gap) {
                   list.set(k + gap, list.get(k));
               }
               list.set(k + gap, value);
           }
        }
        if (gap != 1) {
            list = list_shell(list, gap);
        }
        return list;
    }
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        Random random = new Random();
        ShellSort shellSort = new ShellSort();
        ListAccuracy listAccuracy = new ListAccuracy();

        int[] arr = new int[10];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10);
        }
        System.out.print("before: ");
        listAccuracy.array_print(arr);

        shellSort.array_shell(arr);
        System.out.print("after: ");
        listAccuracy.array_print(arr);

        for (int i = 0; i < 10; i++) {
            list.add(random.nextInt(10));
        }
        List<Integer> origin_copy = new ArrayList<Integer>(list);
        System.out.println("before: " + list);

        list = shellSort.list_shell(list, list.size());
        System.out.println("after: " + list);

        // 윈본과 일치율을 확인하는 코드가 작성되어있다.
        // 합병정렬에서 구현한 코드와 동일하다.
        listAccuracy.accuracy_test(origin_copy, list);
    }
}