퀵정렬

최악의 경우가 아닌 Average Case로 Big O notation을 계산한다.

최악의 경우는 O(n^2) : 이미 정렬된 데이터가 들어온 경우 혹은 반대로 정렬된 경우

최선의 경우는 O(N*logN) : 매번 반으로 쪼개지는 경우!

var test =Array.from({length: 6}, () => Math.floor(Math.random() * 39)+1);

function quicksort(start,end){


    if(start===end)
    {
        return;
    }

    var pointer=start;
    var pivot=test[end];

   for(var j=start;j<end;j++){

        if(test[j]<=pivot){

            var tmp2=test[j];
            var tmp=test.splice(pointer,j-pointer);
            
            if(tmp){
            for(var i=0;i<tmp.length;i++)
            {
                test.splice(pointer+1+i,0,tmp[i]);
            }
            }

            test[pointer]=tmp2 ;
            pointer++;
        }
 
   }

   if(pointer===end){
        quicksort(start,end-1);
   }
   else if(pointer===start){
       test[end]=test[start];
       test[start]=pivot
       
       quicksort(start+1,end);

   }
   else{
       var tmp=test[pointer];
       test[pointer]=pivot
       test[end]=tmp;
       quicksort(start,pointer);
       quicksort(pointer+1,end);
   }
}


console.log(test);
quicksort(0,test.length-1);
console.log(test);