Blog

[알고리즘] 버블정렬

On 8 10월, 2016 By With 0 Comments

버블정렬
인접한 두 원소간 값 비교만을 통하여 정렬을 수행한다.
1회 정렬 수행시 가장 큰 값이 가장 마지막에 위치함으로 이후부터는 정렬 횟수를 -1씩 감소하여 처리할 수 있다.
최대시간복잡도는 n-1팩토리로 구할 수 있다.

JavaScript
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로 코드를 작성하였는데 개념이나 적절하지 못한 코드는 코멘트 들아주시면 감사하겠습니다 ^^

, , ,