기본 정렬 알고리즘(Bubble, Selection, Insertion sorts)

Bubble Sort (버블 정렬)

 

https://visualgo.net/en/sorting

배열의 첫 아이템을 시작으로 다음 아이템과 비교후 정렬, 이후 두번째 아이템과 그 다음 아이템을 비교후 정렬,

이렇게 순차적으로 모든 비교를 마친후 다시 배열의 첫 아이템과 다음 아이템을 비교후 정렬하며 반복적으로 이루어 진다.

 

버블 정렬 예시

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

코드를 보면 반복문 안에 반복문이 들어간다. 

처음 정렬을 완료하면 마지막 아이템은 고정이된다. 마찬가지로 정렬을 마친 아이템들은 뒤에서부터 고정이 되며 반복문을 실행할 필요가 없어지므로 내부 반복문에서 j < i-1 일경우 에만 반복을 해준다.

또한 중간에 모든 정렬이 완료되더라도 반복문은 계속 돌아가게되는데 두번째 반복문의 조건문이 작동하지 않는 다는것은 모든 중간에 모든 정렬이 완료 됬다는 의미 이므로 swapCheck라는 변수를 만들어서 조건문이 스킵 될시 모든 반복문을 종료 하도록 해준다.

 

 

Selection Sort (선택 정렬)

버블 정렬이 큰값을 배열 끝에 배치시키며 진행하는 반면 선택정렬은 배열의 첫부분부터 최소값을 정렬시키며 진행이된다. 또한 버블정렬은 각 아이템들과 비교를 진행하며 바로바로 정렬이 이루어진 반면 선택 정렬은 모든 아이템들을 비교하며 최소값을 찾아내고 그 인덱스를 이용하여 배열의 첫번째부터 정렬을 실행한다.

 

선택 정렬 예시

function selectionSrot(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowestIndex = i;
    let lowestValue = arr[i];
    for (let j = i + 1; j < arr.length; j++) {
      if (lowestValue > arr[j]) {
        lowestValue = arr[j];
        lowestIndex = j;
      }
    }
    if (i !== lowestIndex) {
      arr[lowestIndex] = arr[i];
      arr[i] = lowestValue;
    }
  }
  return arr;
}

버블 정렬과 마찬가지로 반복문안에 반복문이 들어가며 배열의 최소값을 비교할 변수와 그 인덱스를 저장할 변수를 지정해준뒤 두번째 반복문을 이용하여 각 아이템들과 비교후 최소값과 인덱스를 저장, 이후 두번째 반복문을 빠저나와 현재 위치에 저장된 최소값을 배열에 넣어주며 함수가 종료된다.

 

 

Insertion Sort (삽입 정렬)

다른 두 정렬방식은 배열의 첫 아이템부터 다음아이템과 비교를 시작했다면 삽입정렬의 경우 배열의 두번째 아이템을 시작으로 기준을 잡고 그 이전의 아이템들과 비교하며 진행된다. 이후 다음 아이템을 기준으로잡고 또다시 그 이전의 정렬된 아이템들과 비교하며 자신의 자리를 찾는다.

삽입 정렬의 경우 배열의 앞부분은 이미 정렬된 상태이며 뒷부분의 아이템을 정렬된 앞부분에 끼어 넣는 특이한 방식을 사용하며 실시간으로 들어오는 데이터를 계속해서 정렬해 주어야 할때 유용해보인다.

 

삽입 정렬 예시

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

삽입정렬 또한 두개의 반복문이 중첩으로 들어간다. 첫번째 반복문의 경우 배열의 index 1번 부터 시작하며 현재 비교를 진행할 대상을 변수에 저장해준다. 이후 두번째 반복문을 이용하여 기준이되는 아이템과 이전의 아이템들을 순차적으로 비교하며 기준 아이템보다 비교대상 아이템 값이 높을경우 비교대상 아이템을 배열의 한단계씩 이동, 기준아이템보다 비교 대상의 아이템의 값이 낮을경우 기준아이템에 그 자리의 인덱스를 부여한다. 

 

 

Big O notation 비교

3가지 정렬 모두 반복문을 중첩하여 사용하므로 평균 시간 복잡도는 O(n²)이 된다. 시간 복잡도의 효율은 그리 좋지 않지만 공간 복잡도의 경우 받아온 배열외에 변수 몇몇개만 추가해주기때문에 공간복잡도에서의 효율은 좋아 보인다. 

또한 버블정렬과 삽입정렬의 경우 정렬이 얼추 되있는 배열의 경우 해당 반복문을 지나치게되며 상황에따라 시간 복잡도는 O(n)이 된다.