[5][알고리즘 - 정렬] 셸정렬(Shell Sort)이란? javascript 구현

셸 정렬 이란?

1959년 이 방법을 발표한 

창안자 도널드 셸의 이름을 따서 

붙여진 이름인데,

리스트를 특정 매개변수 값의 길이를 갖는

부파일(subfile)로 쪼개서,

각 부파일에서 삽입 정렬을 수행하는

삽입 정렬의 단점을 보완한

정렬 알고리즘 입니다.

 

사실, 셸 정렬은

설명만 듣고는 이해가 가질 않았습니다.

 

쪼개는 것은 알겠는데, 

쪼개진 데이터들을 각각 정렬하는 것도 아닌 것이,

쪼개진 간격의 데이터끼리 하나씩 비교를 하는 느낌이었습니다.

 

출처 - https://runestone.academy/runestone/books/published/pythonds/SortSearch/TheShellSort.html

 

 

이러한 일정한 갭 간격을 설정하고 

간격의 데이터끼리 비교 정렬을 합니다.

 

그 이후, 간격을 줄이고

또 간격의 데이터끼리 비교 정렬을 합니다.

 

최종적으로 간격이 없는 상태까지 도달했을 때,

삽입 정렬을 통해 마지막으로 정렬을 합니다.

 

가장 잘 표현된 영상입니다.

 

이 내용을 토대로 javascript로 구현을 해보겠습니다.

 

// 임의 배열 생성
const makeRandomValueArr = (length) => {
    const arr = [];
    for (let i = 0; i < length; i++) {
        arr.push(i);
    }

    for (let i = 0; i < arr.length; i++) {
        const randomNum = Math.floor(Math.random() * arr.length);
        [arr[i], arr[randomNum]] = [arr[randomNum], arr[i]];
    }

    return arr;
}

// 쉘 정렬
const shellSort = (arr) =>{
	let length = arr.length; // 전체 길이

    // 전체 길이의 1/2로 줄여가며 Gap 간격으로 설정
	for (let gap = Math.floor(length/2); gap > 0; gap = Math.floor(gap/2))	{
		for (let i = gap; i < length; i++) {
			let temp = arr[i];
			
			let j = i;
            while(j >= gap && arr[j-gap] > temp) {
                arr[j] = arr[j-gap];
                j-=gap;
            }

			arr[j] = temp;
		}
	}
	return arr;
}

    const arr = makeRandomValueArr(10);

    console.log('arr==', arr);
    // [9, 6, 0, 2, 1, 8, 7, 3, 5, 4]
    console.time('shell');
    const result = shellSort(arr);
    console.timeEnd('shell');
    console.log('result==', result);
    // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

이미 알아본 삽입, 버블, 선택 정렬에 비해

시간이 대폭 감소되었습니다.

하지만 그만큼 복잡해지고 있네요.

지속적으로 생각을 하며 원리를 이해해야 할 것 같습니다.