[알고리즘] 버블정렬
버블정렬
인접한 두 원소간 값 비교만을 통하여 정렬을 수행한다.
1회 정렬 수행시 가장 큰 값이 가장 마지막에 위치함으로 이후부터는 정렬 횟수를 -1씩 감소하여 처리할 수 있다.
최대시간복잡도는 n-1팩토리로 구할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
var aData = [2,5,6,9,0,11,3,1], nCount = 1; // 버블정렬 function bubbleSort(aData){ var temp, i, j, len = aData.length-1; // 마지막 원소는 비교대상이 없으므로 length -1로 비교 횟수를 제한 for(i=0; i<len; i++){ for(j=0; j<len-i; j++){ console.log(nCount++); if(aData[j] > aData[j+1]){ temp = aData[j]; aData[j] = aData[j+1]; aData[j+1] = temp; } } } } bubbleSort(aData); console.log(nCount); // len-i 29 ++연산이라 28 + 1 console.log(nCount); // len 50, 1회 정렬수행한 값을 제외하지 않을경우 21번의 function ft(n){ if(n==1) return n; return n+ft(n-1); } console.log('최대시간복잡도',ft(aData.length-1)); |
*해당 포스트는 알고리즘 학습을 위한 포스트로 정확하지 못한 개념과 코드가 있을 수 있습니다. 익숙한 언어인 js로 코드를 작성하였는데 개념이나 적절하지 못한 코드는 코멘트 들아주시면 감사하겠습니다 ^^