[Day29] JavaScript - 정렬 구현 & slice, splice

정렬(버블)

버블정렬 알고리즘이란?

1. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
2. 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
3. 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
4. 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
5. 1~3의 과정을 첫 요소부터 다시 반복합니다.
6. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
7. 1~3의 과정을 총 n번(배열의 크기) 반복합니다.

풀이 과정

아래와 같이 for문을 중첩하여 먼저 swapping을 구현해주었다.
안쪽 for문은 한 번 배열 순회이고,
바깥쪽 for문을 통해 배열의 길이만큼 또 반복해주었다.

for(let j=0; j<arr.length-1; j++){
    for(let i=0; i<arr.length-1; i++){
      if(arr[i]>arr[i+1]){
        let x = arr[i+1];
        arr[i+1] = arr[i];
        arr[i] = x;
      }
    }//1~3과정임.
  }

장점

버블 정렬은 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있다. 여기서 "in place"라는 것은 자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻이다.

또한 구현하기 매우 쉽다는 장점도 있다. 그 외에도 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용될 수도 있다.

단점

버블 정렬의 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점이다. 왜냐면 최악의 경우 O(n^2)이 소요되기 때문이다. 만약 데이터가 위 이미지처럼 5개밖에 없다면 최대 25번 순회를 해야하지만 데이터가 1,000개라면 1,000,000번이나 순회를 해야한다.

Big O

Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우
Best Case: O(n): 이미 정렬이 되어있는 경우
버블 정렬은 최악의 경우에 O(n^2)의 시간 복잡도를 가진다. 왜냐하면 각 자리를 찾기 위해서 n번의 순회를 해야하며 n번의 회전 동안에 요소의 개수만큼 또 순회를 해야하기 때문이다. 그러나 이미 정렬이 되어있는 경우에는 한 번의 순회로 정렬 여부를 알 수 있다.
따라서, 안 쪽 for문이 한 번 작동이 끝났을 때 if문으로 어떤 요소도 위치가 바뀌지 않은 경우, break로 바깥for문이 더 이상 작동하지 않도록 해주었다.

또한 기존의 배열과 for문이 작동된 후의 배열을 구분시켜주기 위하여 초반에 slice메소드로 배열을 복사하였고,

배열이 같은지 여부를 판단할 때 JSON.stringify메소드로 두 배열(기존 배열 vs for문이 돌고난 후의 배열)을 비교해주었다.

const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  
  let newArr = arr.slice() //배열을 복사한다

  for(let j=0; j<newArr.length-1; j++){
    for(let i=0; i<newArr.length-1; i++){
      if(newArr[i]>newArr[i+1]){
        let x = newArr[i+1];
        newArr[i+1] = newArr[i];
        newArr[i] = x;
      }
    }//1~3과정임.
    if(JSON.stringify(newArr)===JSON.stringify(arr)){ //어떠한 요소도 바뀌지 않은 경우
      break;
    }
  }

  return newArr;
  
  
};

---

---

slice, splice

자바스크립트에서 배열을 다룰 때 자주 사용하게되는 함수 중에서 이름이 상당히 비슷한 slice()와 splice()가 있다. 이 두 메서드의 차이점을 아는 것이 중요하다.

slice() 함수

slice() 함수는 배열로 부터 특정 범위를 복사한 값들을 담고 있는 새로운 배열을 만드는데 사용한다. 첫번째 인자로 시작 인덱스(index), 두번째 인자로 종료 인덱스를 받으며, 시작 인덱스부터 종료 인덱스까지 값을 복사하여 반환한다. (여기서 중요한 것은 복사하여 반환한다는 것이다. 즉 원본에 손상을 가하고 싶지 않을 때 사용할 수 있다는 것!)

간단한 실습을 위해 숫자 0부터 19까지를 담고있는 배열을 생성하여 nums라는 변수에 할당해보겠다.

const nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

이 숫자 배열에서 5부터 9까지를 복사한 값을 담고 있는 새로운 배열을 만들어 보겠다.

> nums.slice(5, 10)
< [5, 6, 7, 8, 9]

여기서 주의할 점은 첫번째 인자로 넘어온 시작 인덱스가 가리키는 값은 포함하지만, 두번째 인자로 넘어온 종료 인덱스가 가리키는 값은 포함하지 않는다는 것이다. 즉 (5,10) 이라고 한다면 5번째 인덱스 부터 9번째 인덱스까지 slice 된다는 것이다.

두번째 인자를 넘기지 않으면, 시작 인덱스가 가리키는 값부터 배열의 마지막 값까지 모두 복사해준다. (시작점 부터 끝까지 그냥 다 복사해서 가져와준다는 것)

> nums.slice(10)
< [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

첫번째 인자도 넘기지 않으면, 배열의 처음 값부터 마지막 값까지 전체를 복제해버리는 효과를 낼 수 있다. (보통 원본을 손상시키기 싫을 때, 복사해와서 새로운 array를 만들고 싶을 때 사용하는 방법이다. 예를 들면 정렬을 위해서 함수를 만들 때, 그 안의 변수를 이렇게 복사한 array를 이용하면 된다)

> nums.slice()
< [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

slice() 함수는 밑에서 다룰 splice() 함수와 달리 아무리 많이 호출해도 원본 배열의 값은 절대 건드리지 않는다. 따라서 원본 배열이 그대로 보존되야 하는 상황에서 매우 유용하게 사용된다.

> nums
< [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

splice() 함수

slice() 함수의 이름에서 알파벳 p가 하나 더 있는 splice() 함수는 다목적으로 사용할 수 있는 함수이다. 이 함수로는 배열로 부터 특정 범위를 삭제하거나 새로운 값을 추가 또는 기존 값을 대체할 수 있습니다. 첫번째 인자로 시작 인덱스(index), 두번째 인자로 몇개의 값을 삭제할지, 그리고 세번째 인자부터는 추가할 값을 가변 인자로 넘길 수 있으며, 삭제된 값을 담고 있는 배열을 반환한다. (원본에 변형을 가하는 것이기 때문에, 이를 반드시 인지한 상태에서 써야한다)

역시 위와 동일한 방법으로 nums라는 숫자 배열을 생성해놓는다.

> nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

이 숫자 배열에서 인덱스 5가 기리키는 값부터 3개의 값을 삭제해보겠다.

> nums.splice(5, 3)
< [5, 6, 7]
> nums
< [0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

삭제된 3개의 값을 담고 있는 배열이 반환되며, 원본 배열로 부터 3개의 값이 빠져나간 것을 알 수 있다. (원본이 변경되고, 새로운 배열이 반환되는 것이다!)

이번에는 인덱스 5가 기리키는 값부터 아무 값도 삭제하지 않고, -5, -6, -7을 추가해보겠다.

> nums.splice(5, 0, -5, -6, -7)
< []
> nums
< [0, 1, 2, 3, 4, -5, -6, -7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

삭제된 값이 없으므로 빈 배열이 반환되고, 이전에 값이 삭제된 자리에 -5, -6, -7을 들어간 것을 알 수 있다.

이번에는 인덱스 10이 가리키는 값부터 2개의 값을 -10, -11로 대체해보겠다.

> nums.splice(10, 2, -10, -11)
< [10, 11]
> nums
< [0, 1, 2, 3, 4, -5, -6, -7, 8, 9, -10, -11, 12, 13, 14, 15, 16, 17, 18, 19]

삭제된 2개의 값을 담고 있는 배열이 반환되며, 원본 배열의 10, 11이 있던 자리에 -10, -11에 들어가 앉아있는 것을 볼 수 있다.

splice() 함수에 첫번째 인자만 넘기면 해당 인덱스가 가리키는 값을 포함해서 배열의 마지막 값까지 삭제된다.

> nums.splice(15)
< [15, 16, 17, 18, 19]
> nums
< [0, 1, 2, 3, 4, -5, -6, -7, 8, 9, -10, -11, 12, 13, 14]

splice() 함수를 사용할 때 가장 주의할 부분은 삭제된 값을 담고 있는 새로운 배열이 반환될 뿐만 아니라 원본 배열에도 변경이 가해진다는 점이다. 따라서 의도치 않은 데이터 유실이나 변경으로 이어질 수 있으니 특히 데이터의 불변성(immutability)이 보장되어야 하는 프로그램을 작성할 때 주의해야 한다.
(splice를 쓸 때 반드시 이를 인지하고 있어야 한다)

slice() vs. splice()

많은 자바스크립트 개발자들이 slice() 함수와 splice() 함수를 햇갈려하는 이유는 비단 이름이 비슷해서 뿐만 아니라 실제로 동일한 목적을 위해서 두 함수 중에 아무거나 사용해도 무방한 경우가 있기 때문이다.

예를 들어, nums 배열에서 5부터 7까지를 복사한 값을 담고 있는 새로운 배열을 얻고 싶을 때 다음 두 가지 방법을 다 쓸 수가 있다.

> nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
> nums.slice(5, 8)
< [5, 6, 7]
> nums.splice(5, 3)
< [5, 6, 7]

차이점이라고 하면 두번째 인자로 slice() 함수는 종료 인덱스, splice() 함수는 몇개의 값을 때어낼지를 넘긴다는 것 뿐이다.

하지만 이 두 함수를 동일한 배열을 대상으로 여러 번 호출할 수 있는 상황이라면 얘기가 좀 틀려진다.

> nums = Array(20).fill().map((_, i) => i)
< [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
> nums.slice(5, 8) // slice() 1회 호출
< [5, 6, 7]
> nums.slice(5, 8) // slice() 2회 호출
< [5, 6, 7]
> nums.slice(5, 8) // slice() 3회 호출
< [5, 6, 7]
> nums.slice(5, 3) // splice() 1회 호출
< [5, 6, 7]
> nums.splice(5, 3) // splice() 2회 호출
< [8, 9, 10]
> nums.splice(5, 3) // splice() 3회 호출
< [11, 12, 13]

항상 같은 배열을 반환한는 slice() 함수와 달리 splice() 함수는 계속해서 원본 배열를 깍아 먹기 때문에 동일한 인자로 여러 번 함수를 호출했을 때 매번 다른 배열이 반환되게 된다.
(즉 splice의 원본 변경에 대해 인지하지 못했을 경우, 큰 오류가 생길 수 있다는 것)