Bubble Sort

Bubble Sort 

 

• 바로 옆에 있는 요소와 비교해서 자리를 바꾸면서 정렬  바로 옆에 있는 요소와 비교한 후 자리를 바꾸는 방식으로 정렬한다.
• 큰 수를 뒤로 보내다보니 큰 수가 먼저 가장 마지막에 자리를 잡는다.
• 즉, 매번 반복할 때마다 i만큼의 수가 뒤에서부터 자리잡으니까 i개는 더이상 계산할 필요가 없다.

 

시간 복잡도

O(n^2)

 

 

구현하기

let bubbleSort = function(arr){
/*
  arr = [2,1,3]
  2,1 비교 : 2가 1보다 크니까 1,2 로 자리를 바꾼다. 
  2,3 비교 : 2가 3보다 작으니까 자리 바꾸지 않는다.

  */
    let swap
    for(let i = 0; i < arr.length-1; i++){
      for(let j = 0; j < arr.length-1-i; j++){ // 이미 i개는 계산되어 뒤에서부터 정렬되었으니까 i개는 정렬할 필요가 없음 (매번 하나씩 자리잡아서 인덱스만큼 늘어남)
        if(arr[j] > arr[j+1]){    // arr[j]가 더 큰 수이면 뒤로 가야함  
          swap = arr[j]           // swap 에 arr[j]를 넣어주고
          arr[j] = arr[j+1]       // arr[j]에는 더 작은 수 arr[j+1]을 할당해 준다.
          arr[j+1] = swap         // arr[j+1]이 더 큰 수가 되었으니까 swap이 된다.
        }
      }
    }
    return arr
  }

 

 

추가 : 재귀로도 풀 수 있지 않을까?