배열 요소를 기준으로 회전 정렬하기

06 Nov 2023

javascript

배열 요소를 회전하여 정렬하는 알고리즘에 대해 알아보겠습니다. 회전 정렬은 배열을 한 요소씩 회전시켜 최소값이 앞으로 오도록 정렬하는 방법입니다. 이는 주어진 배열을 이용해 원형 큐 형태로 회전하면서 최소값을 찾아 앞으로 이동시키는 방식으로 구현할 수 있습니다.

알고리즘

주어진 배열을 정렬할 배열로 복사합니다.
회전 정렬을 위해 원형 큐 형태로 배열의 요소를 회전시킵니다.
회전한 배열에서 최소값을 찾아 해당 요소를 배열의 맨 앞으로 이동시킵니다.
위의 과정을 반복하여 오름차순으로 정렬합니다.

다음은 JavaScript로 구현한 회전 정렬의 예시 코드입니다.

function rotateSort(arr) {
    var sortedArr = [...arr]; // 정렬할 배열 복사
    
    for (let i = 0; i < sortedArr.length; i++) {
        let minValue = sortedArr[i];
        let minIndex = i;
        
        for (let j = i + 1; j < sortedArr.length; j++) {
            if (sortedArr[j] < minValue) {
                minValue = sortedArr[j];
                minIndex = j;
            }
        }
        
        // 최소값을 배열 맨 앞으로 이동
        sortedArr.splice(minIndex, 1);
        sortedArr.unshift(minValue);
    }
    
    return sortedArr;
}

// 예시 실행
var arr = [4, 2, 9, 5, 1];
var sortedArr = rotateSort(arr);
console.log(sortedArr); // [1, 2, 4, 5, 9]

위의 코드에서는 선택 정렬 알고리즘을 사용하여 회전 정렬을 구현하였습니다. 배열을 복사하여 정렬할 배열로 사용하며, 회전 정렬을 위해 가장 작은 값을 찾아 해당 요소를 맨 앞으로 이동시킵니다. 이를 반복하여 배열을 오름차순으로 정렬합니다.

결론

회전 정렬은 배열의 요소를 한 개씩 회전시키는 방식을 이용하여 정렬하는 알고리즘입니다. 위의 예시 코드를 참고하여 회전 정렬을 구현해보면, 주어진 배열의 요소를 오름차순으로 정렬할 수 있습니다.

#자바스크립트 #회전정렬