버블 정렬

슬기로운 코딩생활·2021년 4월 12일
0

2021.04

목록 보기
2/13
post-thumbnail

•정의


원소가 정렬 돼 가는 모습이 마치 수면 위로 떠오르는 거품 같다고 해서 이름이 지어졌다고 한다. 정렬 알고리즘 중에서 가장 단순하나, 실행 시간은 최악이다.

•동작 원리


인접한 두 원소를 모두 다 비교하고 그 결과에 따라 두 원소의 위치를 서로 바꾼다.
<코드>
class ArrayList{
    constructor(){
        let array = [];
        
        this.insert = (item) => {
        	array.push(item);	
        };
      
        this.toString = () => {
            return array.join(); 
          // join 메소드는 배열 원소를 모두 하나의 문자열로 합친 후 문자열로 반환해준다
        };
   	this.bubbleSort = () => {
            let length = array.length;
            for(let i = 0; i < length; i++){
                for(let j = 0; j < length-1; j++){
                    if(array[j] > array[j+1])){
                        let aux = array[j];
                        array[j] = array[j+1];
                      	array[j+1] = aux;
                    }    
                }
        }
    };	
}

위의 코드는 첫번째 실행시 한번 정렬이 이뤄지고 또 정렬이 끝난 상태인 요소도 다시 루프를 돌기 때문에 불필요하게 일일이 모든 원소를 다시 비교한다.

<개선된 코드>

...

this.moifiedBubbleSort = () => {
	let length = array.length;
	for(let i = 0; i < length; i++){
            for(let j = 0; j < length -1 -i; j++){
              /*안쪽 루프에서 바깥쪽 루프의 반복 횟수를 차감하면 
              불필요한 비교작업이 줄어든다.*/
                if(array[j] > array[j+1]){
                    let aux = array[j];
                    array[j] = array[j+1];
                    array[j+1] = aux;
                }
            }
    }
}

0개의 댓글