Node.js 기본 알고리즘: 버블 정렬, 이진 검색

지식 확장:

시간 복잡도: 알고리즘의 시간 복잡도는 알고리즘의 실행 시간을 설명하는 함수입니다. 시간 복잡도가 낮을수록 효율성은 높아집니다.

자기 이해: 알고리즘의 시간 복잡도는 여러 번 실행하여 결정됩니다. n번 실행하면 시간 복잡도는 O(n)입니다.

1. 버블 정렬

분석: 1. 두 개의 인접한 요소를 비교합니다. 전자가 후자보다 크면 위치를 바꿉니다.

2. 첫 번째 라운드에서는 마지막 요소가 가장 큰 요소여야 합니다.

3. 1단계에 따라 인접한 두 요소를 비교합니다. 이때 마지막 요소가 이미 가장 크기 때문에 마지막 요소를 비교할 필요가 없습니다.

　

function sort(elements){
 for(var i=0;i<elements.length-1;i++){
  for(var j=0;j<elements.length-i-1;j++){
   if(elements[j]>elements[j+1]){
    var swap=elements[j];
    elements[j]=elements[j+1];
    elements[j+1]=swap;
   }
  }
 }
}
 
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log(&#39;before: &#39; + elements);
sort(elements);
console.log(&#39; after: &#39; + elements);

2. 퀵 정렬

분석: 퀵 정렬은 첫 번째 정렬 단계에서 데이터가 두 부분으로 나누어집니다. 부분은 다른 부분의 모든 데이터보다 작습니다. 그런 다음 재귀적으로 호출하여 양쪽에서 빠른 정렬을 수행합니다.

function  quickSort(elements) {
 
　　if (elements.length <= 1) { return elements; }
 
    var pivotIndex = Math.floor(elements.length / 2);
 
    var pivot = elements.splice(pivotIndex, 1)[0];
 
 
　　var left = [];
 
　　var right = [];
 
　　for (var i = 0; i < elements.length; i++){
 
　　　　if (elements[i] < pivot) {
 
　　　　　　left.push(elements[i]);
 
　　　　} else {
 
　　　　　　right.push(elements[i]);
 
　　　　}
 
　　}
 
　　return quickSort(left).concat([pivot], quickSort(right));
 
};
 
var elements=[5,6,2,1,3,8,7,1.2,5.5,4.5];
alert(quickSort(elements));

3. 삽입정렬

분석:

(1) 첫 번째 요소부터 정렬되었다고 볼 수 있다

(2) 다음 요소를 꺼내서 정렬된 요소 순서에서 뒤에서 앞으로 스캔

(3) (정렬된) 요소가 새 요소보다 크면 다음 위치로 요소를 이동합니다.

(4) 정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지 3단계를 반복

(5) 다음 위치에 새 요소를 삽입합니다

(6 ) 2단계 반복

insertSort: function(elements) {

    var i = 1,
    j, step, key, len = elements.length;

    for (; i < len; i++) {

        step = j = i;
        key = elements[j];

        while (--j > -1) {
            if (elements[j] > key) {
                elements[j + 1] = elements[j];
            } else {
                break;
            }
        }

        elements[j + 1] = key;
    }

    return elements;
}

2. 이진 검색

분석: 이진 검색도 절반 검색입니다. 먼저 중간값을 찾아 중간값과 비교하여 큰 값이 배치되고 작은 값이 왼쪽에 배치됩니다. 그런 다음 양쪽에서 중간 값을 찾고 위치를 찾을 때까지 위 작업을 계속합니다.

(1) 재귀적 방법

function binarySearch(data,item,start,end){
    var end=end || data.length-1;
    var start=start || 0;
    var m=Math.floor((start+end)/2);
    if(item==data[m]){
        return m;
    }else if(item<data[m]){
        return binarySearch(data,item,start,m-1) //递归调用
    }else{
        return binarySearch(data,item,m+1,end);
    }
    return false;
}

    var arr=[34,12,5,123,2,745,32,4];

    binary(arr,5);

(2) 비재귀적 방법

function binarySearch(data, item){
    var h = data.length - 1,
        l = 0;
    while(l <= h){
        var m = Math.floor((h + l) / 2);
        if(data[m] == item){
            return m;
        }
        if(item > data[m]){
            l = m + 1;
        }else{
            h = m - 1;
        }
    }
  
    return false;
}
var arr=[34,12,5,123,2,745,32,4];
binarySearch(arr,5);