버블 정렬(Bubble sort)

버블 정렬

• 인접한 두 요소를 비교하여 정렬하는 방식
• 시간복잡도 O(n^2)로 느리지만 코드가 단순하기 때문에 많이 사용된다.
  
  

정렬 과정

https://bournetocode.com/projects/GCSE_Computing_Fundamentals/pages/3-1-4-sort_alg.html

1. 처음 두 요소를 비교한다. 바르게 정렬되어 있으면 그대로 두고, 그렇지 않다면 두 개의 자리를 바꾼다.
2. 1번의 과정을 반복한다.
3. 한 번을 다 돌면 정렬되지 않은 요소가 없을 때까지 과정을 반복한다.
   • 위와 같은 과정이 한 번 진행될 때마다, 제일 뒤에서부터 정렬이 완료된 요소들이 위치하게 되므로, 다음 순회부터는 이미 정렬이 된 요소를 방문할 필요가 없다.
     
     

구현

const solution = arr => {
    let answer = arr;

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

• 순회는 배열의 마지막 요소 바로 앞까지만 해주면 되기 때문에 i < arr.length이다.
• 한번 순회할 때마다 비교할 요소가 하나씩 줄어들기 때문에 j < arr.length-i-1이다.
• 요소의 위치를 바꿔줄 때 구조 분해 할당을 사용할 수 있다.
  [MDN]구조 분해 할당