[JS] 선택정렬 / 버블정렬

선택정렬

배열에서 최솟값을 찾은 후, 최솟값과 맨앞에 위치한 값과 교체한다.

두번째 회전에서는 맨앞에 위치한 값을 제외한 최솟값을 찾아서 계속 바꿔주는 방법이다.

하나의 원소만 남을때까지 위의 과정을 반복한다.

//마지막 숫자는 자동으로 정렬되기때문에 숫자 -1만큼 반복
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }

    if (i !== min) {
      let swap = arr[min];
      arr[min] = arr[i];
      arr[i] = swap;
    }

    console.log(`${i + 1}회전: ${arr}`);
  }
  return arr;
}

제자리 정렬 알고리즘의 하나이다.

입력배열 이외에 다른 추가 메모리를 요구하지않는다.

 

시간복잡도는 O(n^2)

자료이동횟수가 미리 결정된다는 장점이 있으나 비효율적인 방법이다.

안정성을 보장하지않는다. 즉, 값이 같은 레코드가 있다면 상대적인 위치가 변경될 수 있다.

버블정렬

서로 인접한 두 원소를 검사해 정렬하는 알고리즘

인접한 2개의 레코드를 비교해 크기가 순서대로 되어있지않다면 서로 교환한다.

//버블 정렬
function bubbleSort(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[j + 1]) {
        let swap = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = swap;
      }
    }
  }
}

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 자료까지는 정렬에서 제외된다.

이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외하는 데이터가 늘어간다.

 

구현이 매우간단하나, 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하려면 배열에서 모든 다른 요소들과 교환되어야한다(매우 비효율적)

특정 요소가 최종정렬 위치에 이미 있는 경우라도 교환되는일이 일어난다.

일반적으로 자료의 교환작업이 자료의 이동작업보다 더 복잡하기 때문에 버블 정렬은 단순하지만 거의 쓰이지 않는다.

 

시간복잡도는 O(n^2)