[algorithm] bubble sort

문제

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

 

입력

인자 1 : arr

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

출력

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

주의사항

• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

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

Advanced

• 수행 시간을 단축할 수 있도록 코드를 수정해보세요.
• 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다.

풀이

let bubbleSort = (arr) => {
	let temp
    for(let i=0; i < arr.length; i++){
      let count = 0; // 자리가 바뀔때 카운트를 하는데 만약 끝까지 0이라면 이미 정열 되어 있다고 간주한다.
      for(let j=0; j< arr.length -1 -i; j++){ //가장 큰 수는 마지막으로 가기 때문에 i를 하여 마지막 겨우의 수를 줄여주는 것
        if(arr[j] > arr[j+1]){ // 앞의 수가 뒤의 수보다 큰 경우만 생각하면 되기 때문에 조건은 하나면 충분다.
          count++;
          temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp; // 임의의 변수를 사용하여 앞과 뒤의 값을 바꾼다.
        }
      }
      if(count === 0){ // count 값이 0이라면 이미 정열이 되어 있음으로 바로 값을 반환한다.
      	break; 
      }
    }
	return arr;
}

point

· 버블소트에 대한 이해가 필요하다.

//두 변수를 바꾸는 방법(sort)

  // 1) 임시 변수를 활용한 방법
  // let temp = arr[i];
  // arr[i] = arr[i+1];
  // arr[i+1] = temp;
  //ex
  i = 2;
  i+1 = 1;
  // 라고 가정할때 위의 방법을 대입하면 
  temp = 2;
  i = 1;
  i+1 = 2;
  // 만약 temp없이 i = i+1 이라고 한다면 기존의 i 값이 초기화 되기 때문에 i+1값에 할당 할 수가 없다. 

  // 2) Destructuring assignment를 활용한 방법
  // arr이 reference type이라 가능
  [arr[i], arr[i+1]] = [arr[i+1], arr[i]]; // 구조분해 할당을 통하여 앞뒤의 값을 변환(ES6)
  // 간단하게 표현하자면 [i, i+1] = [1,2] 
  // 구조분해 할당은 공부해보면 값을 할당 하기 쉬워진다.
  
  // 3) XOR 연산을 활용한 방법 // 이 방법은 잘 모르겠다.. 스스로 공부해 보도 록 하자.
  // arr이 reference type이라 가능
  // arr[i] ^= arr[i+1];
  // arr[i+1] ^= arr[i];
  // arr[i] ^= arr[i+1];

· 시간을 단축하기 위한 break 의 조건을 알아야 한다.