20.12.19 bubbleSort_Algorithms

bubbleSort

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

입력

• 인자 : arr
• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr[i]의 길이는 1,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
• 수행 시간을 단축할 수 있도록 코드를 수정해보세요.
• 위에서 설명된 알고리즘 1~3의 과정 중 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다.

입출력 예시
let output = bubbleSort([2, 1, 3]);
console.log(output); // --> [1, 2, 3]

버블 정렬 알고리즘

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

코드

const bubbleSort = function (arr) {
  /*
  n번째 정렬 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정된다.
  이중for 문을 사용해야하는데 
  첫번째 반복은 arr.length까지
  두번째 반복은 arr.length -1 -i 까지(두번째는 마지막까지 볼 필요는 없으니까 마지막에서 두번째 까지만 보는 것)
  1.(잠깐 위치를 바꾸기 위한 장소) swap 변수 선언
  2.(반복문)버블 정렬 알고리즘을 반복시키자.
    (만약 arr[j]가 그 다음 것보다 크면) swap에 데이터를 저장해놓고, arr[j]는 그 다음것으로.
    그 다음것은 swap(전 데이터가 저장되어있는)으로 바꾼다.
    (만약 스왑이 없으면.undefined라면) 정렬이 다 되어있다는 뜻이므로 반복문 종료.
  3.arr(정렬된) 리턴
  */
  let swap;
  for( let i = 0; i < arr.length; i++ ) {
    for( let j = 0; j < arr.length -1 -i; j++ ) {
      if( arr[j] > arr[j+1] ) {
        swap = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = swap;
      }
    }
    if( !swap ) {
        break;
    }
  }
  return arr;
};