[TIL][Fri] Python| JavaScript 내부적으로 사용하는 정렬 알고리즘

Python

정렬을 위해 두 가지 메서드를 제공한다.

sort()의 경우 반환하는 값이 없으며 원본(mylist)를 정렬한다. 반대로 전역 함수 sorted()는 정렬된 배열을 반환한다.

메서드

# 리스트 타입에 대한 정렬 
mylist.sort() 

# 전역 함수
result = sorted()

 

알고리즘

Timsort ( Merge + Insertion )( 병합 + 삽입 ) 

시간 복잡도 : O(nlogn)

 

TimSort?

이 글이 정말 잘 설명이 되어있었다. 

Tim sort에 대해 알아보자

Javascript

배열을 정렬하기 위해 Array의 instance 메서드인 myArr.sort() 메서드를 제공한다. 작동 원리로는 요소를 문자열로 변환하여 UTF-16 코드 단위 값의 시퀀스를 비교하는 방식으로 사전식 순서로 비교하거나 사용자가 정의하는 정렬 기준을 사용해 비교할 수 있다. 

Array.prototype.sort()

:: referece

만약 메모리 주소 100에 배열 myArray = [3, 2, 1] 이 있을 때, myArray.sort()시 어떤 일이 일어날까?

이 메서드는 제자리에서 원소들을 정렬(sort elements of an array in place)하고 정렬된 동일한 배열에 대한 참조 주소를 반환( returns the reference to the same array, now sorted )한다. 즉, 반환된(the same array, now sorted) 배열의 메모리 위치 주소는 여전히 100 이다.

 

:: toSorted()

만약 원래 배열을 변형하지 않으려면 toSorted() 메서드를 사용한다.

알고리즘

Quick Sort

시간복잡도(최악): O(n2)

 

특징

Javascript 엔진에 따라 사용되는 알고리즘이 차이가 날 수 있다. 

v8엔진은 긴 배열은 Quick sort, 짧은 배열의 경우 Insertion Sort를 사용한다.

stable 한 정렬이다.

 

[주의] 숫자 정렬

그런데! mdn문서를 읽다보니 굉장히 흥미로운 것을 보았다. 요소를 문자열로 변환하여 UTF-16 코드 단위 값의 시퀀스를 비교하는 방식으로 정렬 하기에 발생하는 특이점이 있다. 

// sort in javascript 

const numberArray = [40, 1, 5, 200];
numberArray.sort();

console.log(numberArray);
// 예상 : [1, 5, 40, 200]
// 실제 출력되는 값: [ 1, 200, 40, 5 ]

 

정렬 과정

1. sort() 메서드로 정렬 시 각 숫자가 문자열로 변환된다. | ['40', '1', '5', '200'] 
2. 문자열의 첫번째 문자 순서대로 정렬된다. | ['1', '200', '40', '5']
   1. '2' 의 utf-16 단위 값이 '4' 보다 작아서, '200' 이 '40'보다 앞에 위치한다.
3. 2에 맞춰 정렬된 값이 반환된다. | [1, 200, 40, 5]

숫자 정렬하기 

const numberArray = [40, 1, 5, 200];
numberArray.sort( (a, b)=> a-b );

// a가 b보다 작으면 음수를, 같으면 0을, 크면 양수를 반환

a-b가 

• 음수 반환: a가 b보다 작다 = a가 b보다 먼저 온다.  a가 더 낮은 인덱스로 간다. 
• 양수 반환: a가 b보다 크다 = a가 b보다 늦게 온다. b가 더 낮은 인덱스로 이동한다.
• 0 반환 : a와 b는 같은 순위를 가졌고, javascript의 sort()메서드는 stable하기 때문에 순서가 그대로 유지된다. 

 

차후 다룰 것: java

 

 

Reference

 

[mdn] Array.prototype.sort()

 

이미지 저장소