lsort — 리스트의 원소 정렬하기

리스트의 원소들을 순서대로 정렬하고 싶을 때 쓰는 명령어가 lsort예요. 기본적으로는 ASCII 오름차순으로 정렬하지만, -integer, -real, -dictionary처럼 비교 방식을 고르거나, -index로 하위 리스트의 특정 원소를 기준으로 삼고, -unique로 중복을 없앨 수도 있어요. 정렬은 안정(stable)한 merge-sort 알고리즘으로 이루어져요.

출처: 문서

본문

lsort 명령어는 list의 원소들을 정렬해 정렬된 순서의 새 리스트로 반환해요. lsort 명령어의 구현은 안정(stable)한 merge-sort 알고리즘을 사용하며 O(n log n) 성능 특성을 가져요.

기본적으로는 결과를 오름차순으로 반환하는 ASCII 정렬이 사용돼요. 다만 list 앞에 다음 옵션들 중 어떤 것이든 지정해 정렬 과정을 제어할 수 있어요(고유 약어 허용):

구문은 다음과 같아요.

lsort ?options? list

-ascii — 유니코드 코드포인트 대조 순서를 쓰는 문자열 비교예요(이름은 하위 호환성 때문). 이것이 기본이에요.

-dictionary — 사전식(dictionary-style) 비교를 사용해요. -ascii와 같은데, (a) 동률일 때를 제외하고 대소문자를 무시하고, (b) 두 문자열에 숫자가 포함되어 있으면 그 숫자를 문자로가 아니라 정수로 비교한다는 점만 달라요. 예를 들어 -dictionary 모드에서 bigBoy는 bigbang과 bigboy 사이에 정렬되고, x10y는 x9y와 x11y 사이에 정렬돼요. -nocase 옵션을 무시해요.

-integer — 리스트 원소를 정수로 변환해서 정수 비교를 사용해요.

-real — 리스트 원소를 부동소수점 값으로 변환해서 부동소수점 비교를 사용해요.

-command command — command를 비교 명령으로 사용해요. 두 원소를 비교하려면 command에 두 원소를 추가 인수로 붙인 Tcl 스크립트를 평가해요. 스크립트는 첫 번째 원소가 두 번째보다 작으면 0보다 작은 정수, 같으면 0, 크면 0보다 큰 정수를 반환해야 해요.

-increasing — 리스트를 오름차순으로 정렬해요("가장 작은" 항목이 먼저). 이것이 기본이에요.

-decreasing — 리스트를 내림차순으로 정렬해요("가장 큰" 항목이 먼저).

-indices — 값 자체 대신 정렬된 순서대로의 list 인덱스 리스트를 반환해요.

-index indexList — 이 옵션을 지정하면 list의 각 원소는 그 자체로 올바른 Tcl 하위 리스트여야 해요(-stride를 쓰는 경우 제외). 전체 하위 리스트를 기준으로 정렬하는 대신, lsort는 각 하위 리스트에서 indexList 번째 원소를 추출해(전체 원소와 indexList를 lindex에 전달한 것처럼) 그 원소를 기준으로 정렬해요. 예를 들어

lsort -integer -index 1 \
      {{First 24} {Second 18} {Third 30}}

는 {Second 18} {First 24} {Third 30}을 반환하고,

lsort -index end-1 \
        {{a 1 e i} {b 2 3 f g} {c 4 5 6 d h}}

는 {c 4 5 6 d h} {a 1 e i} {b 2 3 f g}를 반환하며,

lsort -index {0 1} {
    {{b i g} 12345}
    {{d e m o} 34512}
    {{c o d e} 54321}
}

는 {{d e m o} 34512} {{b i g} 12345} {{c o d e} 54321}을 반환해요(e가 i보다, i가 o보다 먼저 정렬되기 때문). 이 옵션은 -command로 같은 효과를 내는 것보다 훨씬 효율적이에요.

-stride strideLength — 이 옵션을 지정하면 리스트가 strideLength개 원소의 그룹들로 이루어져 있다고 취급되고, 그룹들은 첫 번째 원소 또는(-index 옵션을 쓰면) -index에 전달된 첫 번째 인덱스가 지정하는 그룹 내 원소로 정렬돼요(그 인덱스는 -index에 의해 무시돼요). 원소는 항상 자기 그룹 안에서 같은 위치를 유지해요.

리스트 길이는 strideLength의 정수 배수여야 하고, strideLength는 최소 2여야 해요. 예를 들어

lsort -stride 2 {carrot 10 apple 50 banana 25}

는 apple 50 banana 25 carrot 10을 반환하고,

lsort -stride 2 -index 1 -integer {carrot 10 apple 50 banana 25}

는 carrot 10 banana 25 apple 50을 반환해요.

-nocase — 비교를 대소문자 구분 없이 처리해요. -dictionary·-integer·-real 옵션과 함께 쓰면 효과가 없어요.

-unique — 이 옵션을 지정하면 리스트에서 마지막으로 발견된 중복 원소 집합만 남겨요. 중복은 정렬에 사용된 비교 기준에 따라 결정돼요. 따라서 -index 0을 쓰면 {1 a}와 {1 b}는 중복으로 간주되어 두 번째 원소 {1 b}만 남아요.

참고 사항(Notes)

lsort의 옵션들은 어떤 비교를 사용할지만 제어하고, 값 자체가 실제로 무엇인지를 강제하지는 않아요. 이 구분은 정렬할 리스트의 원소가 2개 미만일 때만 눈에 띄어요.

lsort 명령어는 재진입 가능(reentrant)해서, -command 옵션에 쓰인 명령어의 구현 일부로 사용해도 안전해요.

예시

ASCII 정렬로 리스트 정렬하기:

% lsort {a10 B2 b1 a1 a2}
B2 a1 a10 a2 b1

사전식 정렬로 리스트 정렬하기:

% lsort -dictionary {a10 B2 b1 a1 a2}
a1 a2 a10 b1 B2

정수 리스트 정렬하기:

% lsort -integer {5 3 1 2 11 4}
1 2 3 4 5 11
% lsort -integer {1 2 0x5 7 0 4 -1}
-1 0 1 2 4 0x5 7

부동소수점 리스트 정렬하기:

% lsort -real {5 3 1 2 11 4}
1 2 3 4 5 11
% lsort -real {.5 0.07e1 0.4 6e-1}
0.4 .5 6e-1 0.07e1

인덱스를 이용한 정렬:

% # Note the space character before the c
% lsort {{a 5} { c 3} {b 4} {e 1} {d 2}}
{ c 3} {a 5} {b 4} {d 2} {e 1}
% lsort -index 0 {{a 5} { c 3} {b 4} {e 1} {d 2}}
{a 5} {b 4} { c 3} {d 2} {e 1}
% lsort -index 1 {{a 5} { c 3} {b 4} {e 1} {d 2}}
{e 1} {d 2} { c 3} {b 4} {a 5}

사전(dict) 정렬:

% set d [dict create c d a b h i f g c e]
c e a b h i f g
% lsort -stride 2 $d
a b c e f g h i

striding과 여러 인덱스를 이용한 정렬:

% # Note the first index value is relative to the group
% lsort -stride 3 -index {0 1} \
     {{Bob Smith} 25 Audi {Jane Doe} 40 Ford}
{{Jane Doe} 40 Ford {Bob Smith} 25 Audi}

정렬로 중복 값 제거하기:

% lsort -unique {a b c a b c a b c}
a b c

비교 함수를 이용한 더 복잡한 정렬:

% proc compare {a b} {
    set a0 [lindex $a 0]
    set b0 [lindex $b 0]
    if {$a0 < $b0} {
        return -1
    } elseif {$a0 > $b0} {
        return 1
    }
    return [string compare [lindex $a 1] [lindex $b 1]]
}
% lsort -command compare \
        {{3 apple} {0x2 carrot} {1 dingo} {2 banana}}
{1 dingo} {2 banana} {0x2 carrot} {3 apple}

더 알아보기

list, lappend, lindex, linsert, llength, lsearch, lset, lrange, lreplace