거품이 위로 올라가듯이 상승 중인 가벼운 물체는 바로 자기 위의 것과 자신의 무게를 비교한다. 자신이 가벼우면 자리를 바꾼다. 그 과정에서 모든 것과 비교를 하니 약 N²/2회의 비교를 해야 한다. 이미 정렬이 된 것도 비교 시간은 소모된다. 역순일 때는 자리바꿈도 약 N²/2회의 시간을 소모한다. 자리바꿈 1회는 3회 대입에 해당한다. 가장 무식하고 느린 방법이다.
a ↔ b (자리바꿈)
a → c (보관)
b → a (이동)
c → b (복구)
최소치를 찾아 순서대로 배치하는 방법이다. 최소치를 찾는 과정에서 역시 모든 것과 비교를 하니 약 N²/2회의 비교를 해야 한다. 이미 정렬이 된 것도 비교 시간은 소모 된다. 자리 바꿈 N회의 시간이 추가 된다. 자리바꿈 1회 = 3회 대입. 자리 바꿈 시간에서 거품 정렬보다 유리하다.
자기 자리를 찾아 삽입하는 과정에서 많은 양의 데이터 이동이 필요하다. 허나 부분적으로 정렬이 되어 있는 경우는 삽입 시간을 줄여준다. 이미 정렬이 된 것에는 삽입 시간은 없지만 비교 시간은 약 N²/2회가 소모 된다. 삽입이 없으니 선택 정렬보다 좀 빠르다. 반대로 역순인 경우는 비교 시간이 N회이고 삽입 시간이 약 N²/2회 소모 된다. 비교(뺄셈)나 이동(대입)이나 시간이 거의 비슷할 것이다. 자리바꿈은 3회 대입, 삽입은 1회 대입이라 선택 정렬보다 조금 빠르다.
a(1) → a(2) → a(3) → a(4) (삽입)
a(4) → temp (보관)
a(3) → a(4) (이동)
a(2) → a(3) (이동)
a(1) → a(2) (이동)
temp → a(1) (복구)
기준 값보다 큰 것들과 작은 것들로 양분하는 것을 반복하는 것인데 이 과정에서 다음 단계에선 앞 단계보다 비교할 상대가 줄어들어 비교 시간을 줄여준다. 약 N*log₂N회의 시간이 소모된다. 이런 것을 분할 점령법이라 한다. 정렬 상태일 때는 비교 시간만 소모 된다. 역순일 때는 자리 바꾸는 시간이 추가로 약간(N/2회) 소모 된다. 기준 값을 잠시 보관하기 위해서 마지막 값과 자리를 바꾼다. 그 후에 기준 값을 제자리에 박아 넣는다. 그렇지 않을 경우 기준치를 보관하는 장소가 배열 크기만큼 필요하다. 재귀 호출을 할 경우는 스택에 이 정도의 메모리를 차지하게 되니 불안정하다. 스택의 한계가 정렬할 수 있는 배열의 크기가 된다. 자기 자리에 박힌 기준 값은 다시는 움직일 필요가 없다. 가장 빠른 정렬법이다.
정수를 자릿수별로 정렬한다는 것이다. 100단위, 10단위, 1단위 순으로 비교를 한다는 말이다. 큰 단위를 나누고 그 속에서 작은 단위로 나누는 전략은 퀵 정렬과 같다. 퀵 정렬의 기준치 대신 기수를 이용한 것이다. 분할 점령법이라 비교 시간이 약 N*log₂N회로 준다. 컴퓨터에서 정수는 2진수이니까 비트의 자리수의 0과 1을 검사하거나 그 수의 이상과 이하로 나누면서 정렬할 수 있다. 역시 정수에 대해선 가장 빠르다.
2명씩 짝을 이뤄 승자와 패자를 가른다. 그 다음에 4명씩 짝을 이뤄 서열을 정한다. 그 다음에 8명씩 짝을 이뤄 서열을 정한다. 이렇게 부분적으로 서열을 정한 후에 삽입 정렬을 하면 속도가 빠른 것을 이용한 것이다. 삽입 정렬에서 비교 시간과 이동 시간은 배열 규모의 제곱에 비례한다. 고로 분할하여 미리 서열을 정하면 시간이 많이 절약 된다. 역순일 때 마지막에 대규모의 삽입정렬에선 50%는 순서가 잡혀 있기 때문에 N/2회 비교와 삽입이 필요하다.퀵 정렬보다 약간 느리다.
n = 8
8*8 = 64 (통으로 할 때의 시간)
4*4 = 16, 16*2 = 32 (2등분)
2*2 = 4, 4*4 = 16 (4등분)
합병, 병합 정렬은 약간 어설픈 분할 점령법이다. 셸 정렬과 흡사한 것이 2진 트리를 만들어 승자와 패자를 결정하는 식으로 부분적으로 정렬하는 것이다. 이웃집과 서열을 결정할 때는 삽입 정렬과 비슷하지만, 삽입 정렬을 하지 않고 서열 순서대로 서로 비교하여 새로운 목록을 만든다. 그러면 비교 시간도 삽입 정렬보다 짧고, 삽입 시간도 없다. 대신 작업용 메모리가 배열만큼 필요하다. 그래도 느리다.
if A(x) >= B(y) then
A(x) 출력, x 증가
else
B(y) 출력, y 증가
end if
힙 정렬은 선택 정렬과 비슷하게 최소치, 최대치를 골라낸다. 그런데 그 방법이 토너먼트 식이다. 토너먼트 방식이라고 해도 최소치, 최대치 고를 때는 약 N번의 비교를 해야 한다. 2진 트리를 구성해서 자기 엄마와 자식 사이에 비교를 통해 자리 바꾸기를 하여 최소치, 최대치를 정상(배열의 앞)으로 보낸다. 이것을 마지막 자리와 바꾸고 다시 N-1개를 가지고 2진 트리를 구성하여 다시 최소치, 최대치를 앞으로 뽑는다. 이 것을 반복한다. 마지막에 앞뒤의 순서를 뒤바꾼다. 이 복잡한 짓을 왜 하지? 그냥 선택 정렬과 다를 게 없어 보이는데? 이것도 느리다.
인터넷의 여러 실험 결과를 보면 퀵 정렬, 셸 정렬이 단순하면서도 가장 빠르다. 기수 정렬도 비슷한 효과를 낼 것이다. 이유는 정말 노골적으로 간단한 분할 점령 방식이라서 그렇다. 비교 회수가 일단 약 N²/2에서 N*log₂N으로 줄어든다. 다른 방법들은 복잡하기만 하지 그렇게 빠르지는 않다.
- e=mc², 질량 에너지 보존의 법칙, 질량과 에너지의 총합은 일정하다.
- 빈부 격차 보존의 법칙 = 부자와 거지의 재산의 총합은 일정하다.
- 시공간 보존의 법칙 = 시간과 공간의 곱은 일정하다.
- 품질 = 시간×비용
- 행복 = 여가+소득, 인생 보존의 법칙.
질량 보존의 법칙은 잘 이해하고 있을 것이다. 에너지는 돈이고 질량은 물질이라고 하자. 돈은 물질로 바꿀 수 있다. 돈을 주고 물질을 샀으니 돈은 없어지고 물질이 생겼다.
부자가 늘어나면 거지도 늘어난다. 부자가 더 부유해지면 거지는 더 가난해진다. 부자의 돈은 세상에서 긁어모은 것이기 때문이다. 99명이 1명에게 돈을 몰아주는 것이다.
10명이 1시간 동안 할 일은 5명이 2시간, 2명이 5시간, 1명이 10시간을 해야 하는 노동량이다. 병렬처리를 하면 공간을 낭비하지만 시간은 절약된다. 직렬처리는 식간을 낭비하지만 공간이 절약된다. 컴퓨터에서도 메모리를 많이 쓰면 프로그램이 간단명료하고 빨라진다. 메모리 제약이 있으면 프로그램이 복잡하고 느려진다.
품질은 시간과 비용에 비례한다. 공기업 민영화(사유화)를 하면 이상하게 비용은 올라가는데 품질은 떨어진다. 손님과 하인을 동시에 착취해서 그렇다. 손님에겐 비싸게 팔고, 하인은 싸게 부려먹는 것이다.
노동 시간이 많으면 소득은 늘겠지만 여가시간이 줄어든다. 인생의 시간은 정해져 있으니 여가시간이든 노동시간이든 어느 한쪽으로만 사용할 수 있다.
노동 시간이 많으면 소득은 늘겠지만 여가시간이 줄어든다. 인생의 시간은 정해져 있으니 여가시간이든 노동시간이든 어느 한쪽으로만 사용할 수 있다.
