분류 javascript

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

컨텐츠 정보

  • 조회 990 (작성일 )

본문

설명 :

Comb Sort는 Bubble Sort의 변형입니다. 셸 정렬과 마찬가지로 빗 정렬은 비교 및 ​​교환에 사용되는 간격을 늘립니다. 일부 구현에서는 간격이 특정 양보다 작 으면 삽입 정렬을 사용합니다. 기본 아이디어는 버블 정렬에서 엄청나게 정렬 속도가 느려지므로 목록 끝 부분에있는 거북이 또는 작은 값을 제거하는 것입니다. 목록의 시작 부분에있는 큰 값의 토끼는 버블 정렬에 문제가되지 않습니다. 버블 정렬에서 두 요소를 비교할 때 항상 틈이 1입니다. 빗 정렬의 기본 개념은 갭이 1보다 훨씬 클 수 있다는 것입니다.


코드 :

function combsort(arr)
{
 function is_array_sorted(arr) {
      var sorted = true;
      for (var i = 0; i < arr.length - 1; i++) {
          if (arr[i] > arr[i + 1]) {
              sorted = false;
              break;
          }
      }
      return sorted;
  }
 
  var iteration_count = 0;
  var gap = arr.length - 2;
  var decrease_factor = 1.25;
 
  // Repeat iterations Until array is not sorted
  
  while (!is_array_sorted(arr)) 
  {
      // If not first gap  Calculate gap
      if (iteration_count > 0)
         gap = (gap == 1) ? gap : Math.floor(gap / decrease_factor);
 
  // Set front and back elements and increment to a gap
      var front = 0;
      var back = gap;
      while (back <= arr.length - 1) 
      {
          // Swap the elements if they are not ordered
        
          if (arr[front] > arr[back])
          {
              var temp = arr[front];
              arr[front] = arr[back];
              arr[back] = temp;
          }
 
          // Increment and re-run swapping
        
          front += 1;
          back += 1;
      }
      iteration_count += 1;
  }
  return arr;
}
  
 var arra = [3, 0, 2, 5, -1, 4, 1]; 
console.log("Original Array Elements"); 
console.log(arra); 
console.log("Sorted Array Elements"); 
console.log(combsort(arra));



결과 :

Original Array Elements-1,0,1,2,3,4,5

Sorted Array Elements-1,0,1,2,3,4,5