자바스크립트 배열의 정렬

javascrip는 개인적으로 참 마음에 안드는 부분이 많은데, 그 중에서도 배열의 sort() 메소드는 좀 좌절스러운 것이…

a = [0 to 10].map -> parseInt Math.random! * 100
# [ 74, 7, 45, 41, 43, 85, 84, 66, 41, 91 ]
a.sort!
# [ 41, 41, 43, 45, 66, 7, 74, 84, 85, 91 ]

숫자로 된 배열을 정렬할 때도 사전식으로 비교해서 어이없는 결과를 만들어낸다…. sort() 메소드는 비교 함수를 받긴하므로, 정수 크기별로 비교하려면, 다음과 같이 각 값을 정수형으로 계산한 결과를 던져주는 비교함수를 넣어준다. (-첫째인자 + 둘째인자로 코딩하면 -첫째인자에 의해서 자동으로 정수형으로 인식함.

#livescript
a.sort -> +&0 -&1
# [ 7, 41, 41, 43, 45, 66, 74, 84, 85, 91 ]

업데이트

원글의 내용이 라이브스크립트로 씌여져 있어서 문법이 익숙치 않은 사람을 위해서 자바 스크립트 문법으로 대체합니다.

let a = [0,1,2,3,4,5,6,7,8,9].map( () => parseInt(Math.random() * 100));
console.log(a.sort((x, y) => +x-y));

Shell 정렬 (셸 정렬)

Shell 정렬

Shell 정렬은 “분할 증분 정렬”(diminishing Incremental Sort)이라고도 불리는 방법으로 삽입정렬을 원래 리스트를 더 작은 서브리스트들로 나눠서 정렬함으로써 성능을 향상시키는 방법이다. 즉 리스트를 더 작은 조각들로 나눈다음 각각을 삽입정렬을 사용하여 정렬한다. 이 때 서브리스트들을 나누는 기준을 정하는 방법이 독특한데, 연속된 원소들로 구성된 서브리스트를 나누는게 아니라 i개씩 건너뛰고 원소들을 선택하여 서브리스트를 만든다. 이 때 i는 gap이라고도 불리운다. Shell 정렬 (셸 정렬) 더보기

병합정렬

Merge Sort

Shell 정렬은 보통의 삽입정렬을 리스트를 쪼개는 방식으로 성능을 향상시킨 예이다. 이러한 분할정복방식을 검색에 도입한 알고리듬이 여럿 있는데, 병합정렬(merge sort)도 그 중 하나이다. 병합정렬은 리스트를 재귀적으로 절반으로 나누어 처리하는 방식이다. 만약 리스트가 비어있거나 원소가 하나만 있다면 그 자체로 정렬되어 있다고 보고, 그것이 베이스 케이스1가 된다. 병합정렬 더보기

Bubble Sort

버블정렬알고리듬

버블 정렬은 가장 기본적인 정렬 알고리듬이다. 물속에서 거품이 떠오르는 것처럼 큰 값이 뒤쪽으로 떠올라가는 과정을 계속 반복하는 방식이다. 예를 들어 다음과 같은 정수값의 배열이 있다고 가정해보자.

[45][53][26][93][62][20][33][17]

버블 정렬을 사용해서 이 배열을 오름차순으로 정렬해볼 것이다. 버블 정렬의 알고리듬은 매우 간단하다. Bubble Sort 더보기