분류 javascript

Heap 정렬을 사용하여 요소 목록을 정렬하는 JavaScript 프로그램 작성

컨텐츠 정보

  • 조회 912 (작성일 )

본문

설명 : 

컴퓨터 과학에서 heapsort (1964 년 J. W. J. Williams가 발명)는 비교 기반 정렬 알고리즘입니다. Heapsort는 개선 된 선택 정렬로 생각할 수 있습니다. 알고리즘처럼 입력을 정렬 된 영역과 정렬되지 않은 영역으로 나누고 최대 요소를 추출하여 정렬 된 영역으로 이동하여 정렬되지 않은 영역을 대화식으로 축소합니다. 개선 사항은 최대 값을 찾기 위해 선형 시간 검색이 아닌 힙 데이터 구조의 사용으로 구성됩니다. Heapsort는 내부 알고리즘이므로 안정적인 정렬이 아닙니다.


코드 :

var array_length;
/* to create MAX  array */  
function heap_root(input, i) {
    var left = 2 * i + 1;
    var right = 2 * i + 2;
    var max = i;

    if (left < array_length && input[left] > input[max]) {
        max = left;
    }

    if (right < array_length && input[right] > input[max])     {
        max = right;
    }

    if (max != i) {
        swap(input, i, max);
        heap_root(input, max);
    }
}

function swap(input, index_A, index_B) {
    var temp = input[index_A];

    input[index_A] = input[index_B];
    input[index_B] = temp;
}

function heapSort(input) {
    
    array_length = input.length;

    for (var i = Math.floor(array_length / 2); i >= 0; i -= 1)      {
        heap_root(input, i);
      }

    for (i = input.length - 1; i > 0; i--) {
        swap(input, 0, i);
        array_length--;
      
      
        heap_root(input, 0);
    }
}

var arr = [3, 0, 2, 5, -1, 4, 1];
heapSort(arr);
console.log(arr);


결과 :

-1,0,1,2,3,4,5