2750 수 정렬하기

삽입 정렬

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

배열의 첫 요소는 정렬 되어 있고, 그 뒤의 요소들을 정렬된 요소들과 비교하여 위치를 찾아간다.

process

1. 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

풀이

// 백준 2750번 수 정렬하기
// 시간 복잡도 O(n^2) 삽입 정렬, 거품 정렬

const fs = require('fs');
const [n, ...arr] = fs.readFileSync("input.txt").toString().trim().split("\n");
const input = arr.map((x => parseInt(x, 10)));

function insertSort(arr) {
  for(let i=1; i<input.length; i++) {
    let temp = arr[i];

    let prev = i-1;

    while (prev >= 0 && arr[prev] > temp) { // temp가 정렬된 원소보다 작으면 정렬된 원소를 뒤로 옮긴다.
      arr[prev+1] = arr[prev];
      prev--;
    }

    // temp와 앞의 원소들이 다 정렬되었으니 temp는 temp의 자리에 넣는다.
    arr[prev+1] = temp;
  }
  return arr;
}

const result = insertSort(input);
for (let i=0; i<result.length; i++) {
  console.log(result[i]);
}

• temp
  정렬 검사를 진행할 당사자

• prev
  temp 이전의 정렬된 원소들 중 하나

• while()
  prev의 올바른 자리 찾기.
  temp 보다 크면 그 자리에 있어선 안된다. 지금 현재 자리보다 뒷 자리로 이동해야한다.
  이 작업을 정렬된 모든 원소들에게 진행한다.

거품 정렬

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

두 인접한 원소를 검사하여 정렬하는 방법이다.
인접한 원소들끼리 검사하는 모습이 보글보글(?)한 모습이다.

인접한 원소들끼리 검사해서 큰 숫자를 오른쪽, 작은 숫자는 왼쪽으로 보내는 방식이다.

첫번째 사이클 : (1번째,2번째 / 2번째,3번째 / 3번째,4번째 / ... )
두번째 사이클 : (2번째,3번째 / 3번째,4번째 / ... )
...

Process

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.

2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

풀이

// 백준 2750번 수 정렬하기
// 시간 복잡도 O(n^2) 삽입 정렬, 거품 정렬

const fs = require('fs');
const [n, ...arr] = fs.readFileSync("input.txt").toString().trim().split("\n");
const input = arr.map((x => parseInt(x, 10)));

function bubbleSort(arr) {
  for(let i=n-1; i>0; i--) { 
    for(let j=0; j<=i; j++) {
      if (arr[j] > arr[j+1]) { // 왼쪽에 위치한 원소가 더 작다 -> 있어야할 위치가 아니다.
        // swap
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
}

const result = bubbleSort(input);
for (let i=0; i<result.length; i++) {
  console.log(result[i]);
}

• 첫번째 for문
  인접한 원소들끼리 비교하여 자기 자리를 찾아가면 가장 큰 원소는 맨 마지막 자리에 있다.
  마지막에서 하나씩 작아지면서 모든 원소를 정렬한다.
  첫번째 반복을 돌면 마지막 원소만 정렬된 상태라고 볼 수 있다.

• 두번째 for문
  첫번째 원소부터 시작해서 정렬되지 않은 원소들까지(i)

• if문
  작은 것은 왼쪽, 큰 것은 오른쪽에 놓여야하는데 그렇지 않을 경우(자기 자리가 아니다) 두 원소를 swap(교차)한다.

참고
삽입정렬
버블정렬

문제 제대로 안 읽고 몇 번이나 틀렸습니다를 보는지...
멘탈 잡자.