[정렬]셸정렬

셸정렬

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘.
안정적인 알고리즘은 아니며 퀵 전까지는 가장 빠른 알고리즘 이었다.
시간복잡도 = O(n^(1.3,1.5))

 

1. 개념

✔️ 퀵 정렬이 고안되기 전까지는 가장 빠른 알고리즘으로 알려져 있었다.
✔️ 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행한다.
✔️ 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄인다.

그림출처:https://www.notion.so/f5146c2b256a46f7b060dca6c0c2aae3

1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류
2. 연속적이지 않은 여러 개의 부분 리스트를 생성
3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬
4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복
5. 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복

그림을 보면, 다음과 같이 정렬한다.
1) 4-정렬 : 4만큼 떨어진 두 요소를 비교하여 정렬
2) 2-정렬 : 2만큼 떨어진 두 요소를 비교하여 정렬
3) 1-정렬 : 1만큼 떨어진 두 요소를 비교하여 정렬

 

 

2. 셸 정렬 코드

package com.study.Algorithm;
import java.util.Scanner;
// 셸 정렬(버전 1)

class ShellSort {
	//셸 정렬
	static void shellSort(int[] arr, int n) {
		for (int h = n / 2; h > 0; h /= 2)
			for (int i = h; i < n; i++) {
				int j;
				int temp = arr[i];
				for (j = i - h; j >= 0 && arr[j] > temp; j -= h)
					arr[j + h] = arr[j];
				arr[j + h] = temp;
			}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.println("셸 정렬(버전 1)");
		System.out.print("요솟수：");
		int nx = sc.nextInt();
		int[] arr = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.print("arr[" + i + "]：");
			arr[i] = sc.nextInt();
		}

		shellSort(arr, nx);			// 배열 arr를 셸 정렬

		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < nx; i++)
			System.out.println("arr[" + i + "]＝" + arr[i]);
	}
}

▶︎ 손으로 따라가 본 코드(자세한 코드는 첨부파일 참고)

코드 따라가기.pdf

0.06MB

 

 

3. 증분값(h값)

1) 증분값(h값)의 선택

• 간격(gap)이라고도 한다
• 증분값을 선택하는 이유는 그룹으로 나누기 위해서이다
• 이때 나눠진 그룹의 수는 증분값(간격)과 같다
• 증분값을 선택하기 위해서는 h값이 서로 배수가 되지 않도록 해야한다
  → 그룹이 섞이면서 요소들이 서로 다른 위치의 값과 비교될 수 있다

2) 증분값(간격)에 사용되는 수열을 추가하여 셸 정렬하기

• 셸 정렬에 사용되는 수열의 규칙 : (x-1)/3
• 증분값의 초기값이 너무 크면 효과가 없기 때문에, 배열의 요솟수를 9로 나눈 값을 넘지 않도록 조정해준다.

package com.study.Algorithm;
import java.util.Scanner;
// 셸 정렬(버전2, h의 값은 …, 40, 13, 4, 1）

class ShellSort2 {
	// 셸정렬
	static void shellSort(int[] arr, int n) {
		int h;
		for (h = 1; h < n / 9; h = h * 3 + 1) {
			;
		}

		for ( ; h > 0; h /= 3) {
			for (int i = h; i < n; i++) {
				int j;
				int temp = arr[i];
				for (j = i - h; j >= 0 && arr[j] > temp; j -= h)
					arr[j + h] = arr[j];
				arr[j + h] = temp;
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.println("셸 정렬(버전 2)");
		System.out.print("요솟수：");
		int nx = sc.nextInt();
		int[] arr = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.print("arr[" + i + "]：");
			arr[i] = sc.nextInt();
		}

		shellSort(arr, nx);			// 배열 x를 셸 정렬
		
		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < nx; i++)
			System.out.println("arr[" + i + "]＝" + arr[i]);
	}
}

 

1. shellSort 메소드의 첫 for문은 h의 초기값을 구한다.
2. → 1부터 시작하여 값을 3배하고 1을 더하면서 n / 9 를 넘지 않는 가장 큰 값을 h에 대입
3. h값은 반복하여 마지막에 1이 된다.
4. 그러나 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지는 않다.

 

자료출처: www.notion.so/f5146c2b256a46f7b060dca6c0c2aae3