sort 메서드 안에는 어떤 종류의 sort가 사용되었을까?

오늘부터 다시 토이를 1문제씩 풀어보려고 한다.

1번, 2번 문제는 내가 너무 힘들게 풀었던 문제였기에, 

3번 _isSubsetOf 문제부터 시작하려고 했다.

근데..? 예전에 통과했던 문제들이 지금은 통과가 안된다..ㅎㅎ 수정이 되었다나보다.

3번 문제같은 경우에는 시간복잡도에 대한 문제가 Advanced로 추가가 된 것 같다.

그래서 전에 통과했던 로직으로 테스트를 실행시켰을 때, 시간 초과가 결과로 출력이 된다.

 

내가 사용한 코드의 처리 방식은

base = [10, 99, 123, 7]; sample = [7, 100, 99, 123]; 가 있을 때

sample의 요소들이 있는지 없는지 base를 모두 순회하면서 찾는다.

10 === 7, 99 === 7, 123 === 7, 7 === 7 

10 === 100, 99 === 100, 123 === 100, 7 === 100 false!

이렇게 되다보니 시간복잡도가 O(N²) 이다.

그렇다보니 검토해야할 요소들이 70000개 이상일 때, 처리 시간이 기하급수적으로 높아질 수 밖에 없다.

 

이때 내 코드에 sort를 사용해서 먼저 엘리먼트들을 정렬시킨 후 비교를 한다면? 

base = [10, 99, 123, 7]; sample = [7, 100, 99, 123];

base.sort(a-b) = [7,10,99,123]; , sample.sort(a-b) = [7,99,100,123];

7 === 7,

7 === 99, 10 === 99, 99 === 99

7 === 100, 10 === 100, 99 === 100, 123 === 100 false!

엘리먼트들이 내림차순으로 정렬 되었기 때문에 두 배열의 요소들을 비교하는 시간복잡도가 낮아질 것 이다.

---

Timsort

immersive 에서 toy를 풀다보면 Bubble sort부터 merge sort, heap sort 등등 다양한 종류의 정렬들을 볼 수 있다.

그럼 내가 javascript에서 사용하고 있는 array.prototype.sort()는 어떤 방식의 sort가 사용되었을까?

바로 위에 보이는 Timsort라고 한다.

Timsort는 합병정렬과 삽입정렬의 장점을 합쳐놓은 정렬이라고 한다.

밑에 보이는 것 처럼 가장 복잡할 때가 nlogn(Logarithmic Time)이고

가장 효율적일 때가 O(n)[Linear Time]의 시간복잡도를 갖는다고 한다.

 

insertion sort는 시간복잡도가 O(N²)라고 알고 있는데 왜 그 정렬을 결합했는지 궁금해서 찾아보았다.!

 

d2.naver.com/helloworld/0315536

네이버에서 친절하게 설명을 해주시는데 너무 죄송하다..

글을 이해할 만큼의 지식이 아직 쌓이지 않아서 이해를 못하겠다.

내가 저런 글을 읽고 이해할 수 있는 수준이 되도록 노력해야겠다.

 

---

단어 ~

 

derive 발음이 drive와 비슷하지만 강세가 다르다!

They won't be getting the most out of Pairprograming. 

Tutor has to help them to derive skills from the program.

wiki에서는 수동태로 사용 !