package sort.manysort;

import sort.test.Command;

public class ShellSort implements Command {

	@Override
	public void sorting(Integer[] S) {
		int gap, n = S.length;
		int key, index;

		// gapÀÇ »çÀÌÁî´Â???
		for (gap = n / 2; gap > 0; gap /= 2) {
			// ÁÁÁö ¾ÊÀº ¹æ¹ý
			// for (int k = gap_max; k > 0; k--) {
			// gap = ((int) Math.pow(2, k)) - 1;

			// gapÀÇ Å©±â¸¸Å­ Áõ°¨ÇÏ´Â À妽º (»ðÀÔÁ¤·Ä)
			for (int i = 0; i < gap; i++) {
				for (int j = i + gap; j < n; j += gap) {
					key = S[j];
					index = j - gap;
					while ((index >= 0) && (S[index] > key)) {
						S[index + gap] = S[index];
						index -= gap;
					}
					S[index + gap] = key;
				}
			}
		}
	}

	@Override
	public String getName() {
		return "Shell";
	}
}