23.04.05. sorting 알고리즘 만들어보기

Issue

강의 숙제로 배열 연습을 위해 정렬 문제를 풀어보자

문제는 string의 요소를 가진 array에서 string의 index를 지정해서 그 순서로 정렬하는 함수를 만드는 것

---

Try&Error

sorting이 복잡한 알고리즘이 많다는건 예전 유투브에서 sorting을 이미지와 소리로 표현한 영상을 봐서 알고 있었다. 

여러 알고리즘이 있었고, 데이터의 종류에 따라 어떤 알고리즘이 더 주요하다는 등의 유불리가 있을 것으로 대충 알 고 있으나, 우선 생각나는대로 만들어봤다.

function sortingMyWay(arr, where) {
  // 정렬할 새로운 배열을 만들고 arr의 첫 요소를 넣어주는 것으로 initialize
  let newArr = [arr.shift()]
  
  // for문 n-1회 반복
  for (let e of arr) {
    
    // 비교할 string index가 string보다 큰 경우 error 던지기
    if (e.length <= where) {
      throw new Error("Index for comparison is greater than a string")
    }
    
      // newArr에 하나씩 크기 비교하며 입력 1 ~ n-1회 반복
      for (let index in newArr) {
        
        // arr의 요소가 newArr의 비교대상보다 크면 index에 arr 요소를 추가하고
        if (e[where] > newArr[index][where]) {
          newArr.splice(index, 0, e)
          // 다음 arr 요소 비교로 넘어감(break)
          break
        
        // arr의 요소가 newArr의 비교대상과 같으면, 전체 비교로 우선순위 결정하고
        } else if (e[where] === newArr[index][where]) {
          if (e > newArr[index]) {
            newArr.splice(index, 0, e)
          } else {
            newArr.splice(parseInt(index) + 1, 0, e)
          }
          // 다음 arr 요소 비교로 넘어감(break)
          break
        
        // 가장 마지막것 까지 비교했을 경우(=가장 작은 경우) 마지막에 추가(push)하고
        } else if (parseInt(index) + 1 === newArr.length) {
          newArr.push(e)
          // 다음 arr 요소 비교로 넘어감(break)
          break
        
        // 해당사항 없는 경우 pass
        } else {}
      }
  }
  return newArr
}

만들고 나서 기술매니저님에게 리뷰받았다.

---

Solution

내가 작성한 코드가 틀린건 아니고, 결론적으로 여러 알고리즘이 있으니 비교해면 좋은 공부가 될 거라는 리뷰.

 

그리고 실제로 JS의 배열에 sort()라는 method가 있고, compareFn을 만들어서 두개를 비교할 때, 원하는 기준을 만들 수 있으니, 그걸 활용한 코드도 작성해보면 좋을 것이라는 조언과,

 

여러 정렬 알고리즘은 여기에서 볼 수 있으니, 내가 만든 정렬 알고리즘이 어디에 해당하는지, 그리고 어떤 장단점이 있는지 살펴보면 좋겠다는 말씀.

---

Learned

문서를 살펴보니 내가 만든건 insertion sort에 가깝고(물론 메모리를 잘 활용한 것 같진 않다. 새로운 배열을 만들어 넣었으니), 정렬하는 순서의 정 반대순으로 주어진다면 n제곱의 복잡도를 가지고, 정렬순과 같다면 n의 복잡도를 가지는 단순한 정렬 방법이다.

 

간단한 insertion sort같은 경우는 n의 모수를 전체에 대해 비교를 하기 때문에 best는 n-1번, worst는 (n-1)*(n-2)번 정도? 되니까, n^2의 복잡도를 가지는 것은 이해된다. 하지만 divide and conquer 방식으로 하면, nlogn의 복잡도를 가지고, 재귀함수를 사용하는 알고리즘은 단축되는 경로에 대한 경우의 수를 수열로 계산해서 복잡도를 계산하고, 나누는 방법에 따라 어떤 복잡도를 가지는지에 대해 master theorem으로 있다. 까지는 이해했다만, 아직 좀 더 공부해 봐야 겠다. 

 

시간 복잡도에 대해 이해하기에 도움이 된 포스트: 재귀식에 대한 복잡도, Tim Sort에 대한 설명(block sorting과 유사하지만 병합 때 알고리즘이 merge sort방식으로 했느냐, selection sort 방식으로 했느냐의 차이인 듯)

 

근데 이런 sorting알고리즘이 2002년(tim sort), 2008년(block sort)...에 발표되었다는게 조금 놀랍다. 마치 딥러닝 보듯? 수학적으로 수백년전에 다 정리될 것 같았는데 말이다.

---