자바스크립트 배열의 정렬

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 Sort)

셸 정렬은 정렬 방법의 원리로만 보자면 “분할 증분 정렬”(diminishing incremental sort)이라고도 불리는 방법이며, 굉장히 오래된 정렬 알고리듬 중 하나이다. 이 정렬 방법은 삽입 정렬을 근간으로 하면서 삽입 정렬의 성능을 간단한 아이디어로부터 크게 증가시키는 방법이다.

삽입 정렬은 왼쪽에 있는 원소부터, 그 원소가 이동할 수 있는 ‘가장 왼쪽 자리’에 그 값을 삽입하여 정렬해 나가는 방식이다. 이 때 ‘삽입’을 위한 공간을 만들기 위해 원래자리부터 삽입될 자리 사이의 값들이 하나씩 오른쪽으로 이동해야 한다. 따라서 삽입 정렬은 어떤 원소가 이동해야 할 거리가 크면 클수록 효율이 떨어지며 배열이 반대로 정렬되어 있는 경우가 이에 해당할 것이다.

셸 정렬 (Shell Sort) 더보기

병합정렬

병합정렬은 기초적인 정렬 알고리듬 중에서 널리 알려진 알고리듬 중 하나이며, 대표적인 분정복 알고리듬의 예인 동시에 재귀 알고리듬의 좋은 예이다. 이름에 ‘병합'(merge)이 들어가는 이유는 배열을 2개 혹은 그 이상의 작은 조각으로 나누고 각각의 조각을 정렬한 다음, 각 조각의 앞에서부터 가장 작은 값을 순서대로 골라서 정렬된 결과를 생성하기 때문이다.

원래의 배열을 쪼갠 각각의 조각 역시 똑같은 병합 정렬을 이용해서 정렬하는 재귀적인 동작을 수행한다. 재귀적 알고리듬의 수행 과정을 복잡하고 어렵게 여기는 사람들이 있는데, 입력과 결과에 집중하는 방식으로 바라보면 오히려 더욱 명료하고 간단하다는 것을 알 수 있다.

병합정렬 더보기

버블 정렬 (Bubble Sort)

버블정렬은 정렬 중에서 가장 기본적이고 쉬운 알고리듬이다. 버블정렬은 배열의 앞에서부터 큰 원소를 뒤쪽으로 보내는 작업을 반복적으로 시행하여 배열 전체를 정렬한다. 이 때 큰 값들이 물속에서 거품이 떠오르는 것처럼 움직이기 때문에 ‘버블’이라는 이름이 붙었다.

간단한 예를 통해서 버블 정렬이 어떻게 작동하는지 살펴보자. 아래와 같은 배열이 있다고 가정하자.

버블 정렬 (Bubble Sort) 더보기