[Algorithm] Bubble Sort

kich555·2021년 10월 31일
0

Sort Algorithm

목록 보기
2/2

버블 정렬은 인접한 데이터를 교환해서 정렬하는 알고리즘입니다. 알고리즘의 정렬되는 모습이 마치 거품처럼 보인다고 해서 붙여진 이름입니다.

nums라는 배열을 주면, 버블정렬 알고리즘으로 오름차순(1,2,3..10) 으로 정렬된 배열을 return해주세요.

const bubbleSort = nums => {

  for(i=0; i<nums.length; i++) {
    
    for(j=0;j<nums.length-1-i; j++) {
      
    if(nums[j] > nums[j+1]) {     
     let swap = nums[j]
      nums[j] = nums[j+1]
      nums[j+1] = swap  
    }
  
    }
    
  }
    return nums
}

버블 정렬의 장단점

버블정렬은 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식을 말한다.
선택 정렬과 마찬가지로 코드가 간단한게 특징이며 마찬가지로 n개의 원소에 대하여 n개의 메모리를 사용한다.
하지만 선택 정렬과는 다르게 버블 정렬은 비교횟수도, 교환 횟수도 많은것이 최대 단점으로
시간복잡도는 선택 정렬과 같은 O(n²)이지만, 실질적 성능은 선택 정렬이 조금 더 빠르다.

하지만 선택 정렬과는 다르게 버블정렬은 데이터 세트가 이미 정렬되어 있다는 것을 첫 번째 반복에서 인식 할 수 있는데 이는 이미 정렬된 상태에서 다른 자료가 추가하거나 하는 상황에서 상황에 따라 선택 정렬보다 더 나은 선택이 될 수 있을 것이다.

profile
const isInChallenge = true; const hasStrongWill = true; (() => { while (isInChallenge) { if(hasStrongWill) {return 'Success' } })();

0개의 댓글