코딩테스트 문제 4

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.

버블 정렬 알고리즘은 아래와 같습니다.

1. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
2. 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
3. 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
4. 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
5. 1~3의 과정을 첫 요소부터 다시 반복합니다.
6. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
7. 1~3의 과정을 총 n번(배열의 크기) 반복합니다.
   이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부릅니다.

주의사항

위에서 설명한 알고리즘을 구현해야 합니다.
arr.sort 사용은 금지됩니다.
입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력예시

let output = bubbleSort([2, 1, 3]);
console.log(output); // --> [1, 2, 3]

작성코드

const bubbleSort = function (arr) {
  for(let i = 0; i < arr.length; i++) {
    let breakPoint = 0;   // // 브레이크 포인트를 만들어서 바꿀게 없을때 브레이크
    for(let j = 0; j < arr.length; j++) {
      if(arr[j] > arr[j + 1]) {
        breakPoint++
        let change = arr[j]  // 반복문으로 모든 수를 비교하여 앞에 큰 값이 생기면 배열의 위치를 바꾼다.
        arr[j] = arr[j + 1]
        arr[j + 1] = change
      }
    }
    if(breakPoint === 0) break; //배열이 완성됐는지 안됐는지 확인하기 위한 브레이크 포인트 작성
  }
  return arr; // 반복문 끝나고 배열 리턴
};

디버깅

debugger;
bubbleSort([1,5,3,2]);

arr = [1,5,3,2] 가 들어가면
두번째반복문에 들어와서 
arr[0]과 arr[1] 값을 비교한다. 
arr[0]이 크지 않기 때문에, 반복문이 다시 돈다.
// arr=[1,5,3,2]

arr[1]과 arr[2]를 비교한다.
arr[1]이 arr[2]보다 크기 때문에, breakpoint를 추가한다.
arr[1]의값을 change라는 변수에 저장하고
arr[1]의 값을 arr[2]의 값으로 바꾸고,
arr[2]의 값을 change라는 변수의 값으로 바꾼다.
// arr=[1,3,5,2]

arr[2]와 arr[3]을 비교한다.
arr[2]가 arr[3]보다 크기 때문에, breakpoint를 추가한다.
arr[2]의값을 change라는 변수에 저장하고
arr[3]의 값을 arr[2]의 값으로 바꾸고,
arr[2]의 값을 change라는 변수의 값으로 바꾼다.
// arr= [1,3,2,5]

그 다음에 비교할 값이 없기때문에
 if(breakPoint === 0) break; 여기로 가지만, 0이 아니므로 다시 첫번째 for 구문이 돌아간다.
최대 length까지 하면 다 살펴볼수 있고, 이미 배열이 완성되면 breakpoint로 빠져나올수 있다.