자주 나오는 정렬 알고리즘

선택 정렬

선택 정렬이란 오름차순, 내림차순에 따라 하위 인덱스부터 하나씩 위치를 정렬시켜 나가는 방법으로 이중 for 문을 통해 구현됩니다.

function solution(arr) {
  /*
    선택 정렬이란 최솟값부터 하나씩 위치 변경을 시켜주는 것이다
    이중for문을 돌면서 i번 위치에 올 최솟값, i + 1 위치에 올 최솟값... 
    이렇게 정렬시켜나간다
  */
  let answer = arr;

  for (let i = 0; i < arr.length; i++) {
    let idx = i;
    for (let j = i; j < arr.length; j++) {
      if (arr[idx] > arr[j]) idx = j; // 자리바꾸기
    }

    // 이렇게 하면 아래와 똑같이 자리가 바뀐다 아래 tmp 변수를 활용하는 것과 같다
    [arr[i], arr[idx]] = [arr[idx], arr[i]];
    // let tmp = arr[i];
    // arr[i] = arr[idx];
    // arr[idx] = tmp;
  }

  return answer;
}

 

버블 정렬

버블 정렬은 이웃한 두 수끼리 비교해서 정렬하는 방식으로 선택정렬이 하위 인덱스부터 정렬되었다면 버블 정렬은 마지막 인덱스부터 정렬되게됩니다.

 

function solution(arr) {
  /*
    버블 정렬은 맨 뒷자리가 결정된다
    오름차순에선 가장 큰 수가 맨 뒷자리로와 정해진다

    따라서 맨 뒤를 하나씩 줄이면서 더하면 된다.
    i가 0일땐 맨 뒤까지
    i가 1일땐 맨 뒤 - 1
    i가 2일땐 맨 뒤 - 2..
   */
  let answer = arr;

  for (let i = 0; i < arr.length; i++) {
    for (j = 0; j < arr.length - i - 1; j++) {
      // arr.length - i - 1까지 도는 이유는
      // 마지막 인덱스부터 정렬되기 때문에 마지막 인덱스 위치가 변한다
      // i가 커질수록 작아진다
      if (arr[j] > arr[j + 1]) {
        // let tmp = arr[j];
        // arr[j] = arr[j + 1];
        // arr[j + 1] = tmp;
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

 

삽입 정렬

삽입 정렬은 순차적으로 시작해서 옮기려는 인덱스의 값을 복사해놓은 뒤 이미 정렬시켜놨던 부분과 비교해가며  옮기려는 인덱스까지 정렬해놓은 뒤 따로 복사해놓은 인덱스의 값을 삽입하는 방식입니다.

 

arr[i] 이하 인덱스를 복사해놓은 뒤 i부터 시작 인덱스 0까지 역순으로 내려가면서 값을 비교해나갑니다

이때 arr[i]값이 비교하는 값보다 작다면 비교되었던 값을 다음으로 복사해놓습니다.

만약 작다면 복사하지 않고 종료한 뒤 원래 복사되어야하는 위치에 인덱스 값을 저장시켜 놓습니다.

 

이후 계속 반복하면서 정렬해나가게 됩니다.

function solution(arr) {
  let answer = arr;
  const len = arr.length;

  for (let i = 0; i < len; i++) {
    let tmp = arr[i];
    let j = i - 1;
    for (j; j >= 0; j--) {
      // - 값으로 넘어가진 않는다
      if (arr[j] > tmp) {
        // arr[j]가 tmp보다 크면 다음 인덱스로 복사
        // 복사시키면서 정렬해나간다
        arr[j + 1] = arr[j];
      }
      // 그게 아니면 다음 자리에 넣고 종료
      else break;
    }

    // j가 종료된 시점은 tmp에 있는 값보다 작은 것이 되니
    // 그 다음 자리에 넣어야 한다
    arr[j + 1] = tmp;
  }

  return answer;
}