[알고리즘] 버블정렬, 선택정렬, 삽입정렬

1. 버블정렬

(1) 개념

버블정렬의 개념은 배열을 가장 작은 숫자에서 가장 큰 숫자순으로 오름차순으로 정렬을 한다면 

더 큰 숫자가 한번에 하나씩 뒤로 이동한다.

(2) 예시

[5,1,2,3,4]
[1,5,2,3,4]
[1,2,5,3,4]
[1,2,3,5,4]
[1,2,3,4,5]

(3) 코드

function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

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

bubbleSort([8, 1, 2, 3, 4, 5, 6, 7]);

위의 코드는 정렬이 완료되도 모든 for문을 돌아야 종료되기 때문에 효율성이 좋지 않다.

그렇기 때문에 변수하나를 추가하여 변경된 값이 있는지 확인해준다.

function bubbleSort(arr) {
  var noSwaps;
  for (var i = arr.length; i > 0; i--) {
    noSwaps = true;
    for (var j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        noSwaps = false;
      }
    }
    if (noSwaps) break;
  }
  return arr;
}

(4) 시간복잡도

버블정렬은 기본적으로 2중for문이 들어가 있기 때문에 시간복잡도는 O(n^2) 이다.

하지만 데이터가 거의 정렬되어있거나 이미 끝난상태에서는 O(n)에 더 가깝다.

최악의 경우 : 모든 for문을 다 실행한 경우

최상의 경우 : 데이터가 거의 정렬되어있는경우, 이미 정렬이 끝난 경우

2. 선택정렬

(1) 개념

선택정렬은 작은 값을 한번에 하나씩 위치시킨다.

버블정렬과 마찬가지로 처음부터 끝까지 움직이지만 실제 정렬된 데이터는 처음부터 누적되고 있다.

(2) 예시

[5,3,4,1,2]
[1,3,4,5,2]
[1,2,4,5,3]
[1,2,3,5,4]
[1,2,3,4,5]

(3) 코드

function sort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let index = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[index] > arr[j]) {
        index = j;
      }

      if (j == arr.length - 1) {
        [arr[i], arr[index]] = [arr[index], arr[i]];
      }
    }
  }
  return arr;
}

(4) 시간복잡도

기본적으로 시간복잡도는 O(n^2)이다.

버블정렬보다 효율이 좋은 경우는 스왑수를 최소화 하는 경우이다.

3. 삽입정렬

(1) 개념

배열을 점차적으로 정렬해 나아가는 방식이다.

각 요소를 취하여 정렬되어있는 배열속 위치를 찾아 위치시킨다.

(2) 예시

[5,3,4,1,2]
[3,5,4,1,2]
[3,4,5,1,2]
[1,3,4,5,2]
[1,2,3,4,5]

(3) 코드

function insertionSort(arr){
	var currentVal;
    for(var i = 1; i < arr.length; i++){
        currentVal = arr[i];
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

(4) 시간복잡도

기본적으로 O(n^2)이다.

데이터가 거의 정렬되어있다면 O(n)이다.

유리한 상황 : 적절한 위치에 항목을 삽입하기 때문에 라이브,스트리밍 방식으로 들어온 데이터를 즉시 입력해야할때

불리한 상황 : 반대로 정렬되어 있는경우