KTUG마당은 KTUG를 방문하는 모든 이용자가 대화를 나누고 소식을 전하는 곳입니다.

  • 로그인 없이 자유롭게 글을 읽고 쓸 수 있는 철학은 처음과 같이 계속됩니다.
  • Team Blog의 글을 이곳 게시판의 "정보글"로 모았습니다. Team blog는 기고자가 올린 글에 질문을 받는 부담을 줄이기 위하여 댓글을 허용하지 않았습니다. 그러나 이곳 게시판으로 모으면서 댓글을 달 수 있습니다. 게시물을 작성하실 때 댓글을 원하지 않으시면 댓글을 허용하시지 않으시기를 바랍니다. 또한 불필요한 소모성 댓글을 달지 않도록 주의하여 주시기를 바랍니다.
  • TeX과 관련된 질문이나 답변은 QnA 마당을 이용하십시오. TeX과 관련된 질문은 지웁니다
  • MathJax를 이용한 수식조판을 사용하실 수 있습니다. 여기를 참조하세요.
  • 스팸 글을 막기 위하여 짧은 시간 내에 다시 글이 등록되는 IP를 막거나, 광고 글을 막기 위하여 금지어로 .com, .net 등을 설정하고 있습니다. 다소간의 불편함이 있으시더라도 양해 바랍니다.
    • 금지어에서 ktug, stackexchange, stackoverflow, ctan, overleaf, google.com, sil.org, kopus.org등은 해제하였습니다.
  • 사용하는 편집기는 CKeditor입니다. 편집기에서 [enter]를 누르면 <p> 태그가 들어가고, 문단으로 생각하고 한줄을 비웁니다. 글줄만 바꾸려면 shift-enter 를 누르시면 <BR>가 들어가므로 용도에 맞게 나누어 쓸 수 있습니다.

자유글 clist sorting

2020.09.09 09:41

yihoze 조회 수:128

http://www.ktug.org/xe/index.php?document_srl=246410&mid=KTUG_QnA_board 에서 제시된 솔루션을 분석하다가 \clist_sort:Nn이 어떤 정렬 알고리즘을 사용할까 궁금해졌습니다.

\clist_sort:Nn \l_foo_clist {
\int_compare:nNnTF { #1 } > { #2 }
{ \sort_return_swapped: }
{ \sort_return_same: } }

이것은 단지 오름차순으로 할지 내림차순으로 할지 지정하는 것이기 때문에 내부에서 어떻게 돌아가는지 알 수 없죠.

찾아보니, bubble, insertion, merge, quicksort 알고리즘이 있는가 봅니다. \clist_sort:Nn은, 근거는 없지만, bubble 아니면 insertion을 사용할 것 같습니다. bubble과 insertion은 유사한데 bubble은 뒤쪽부터 정렬되게 하고, insertion은 앞쪽부터 정렬되게 하는 것으로 이해했습니다. merge와 quicksort는 쪼갰다가 합치는 것인데, quicksort는 이름과 달리 그닥 빠른 것 같지도 않습니다. 

아무튼 텍에서 sort 같은 고급(?) 함수가 제공된다는 것이 놀랍습니다. 

웹을 뒤져서 구한 파이썬 코드로 이렇게 해봤습니다. merge 알고리즘에서는 merge 함수가 요체인 듯하여, 실은 꼼수 같은 느낌이 들어서, 제외했습니다.

pysort.png

bubble이 이해하기도 쉽고, 데이터가 다르면 결과가 달라질지 모르겠지만, 저 정렬 처리를 1000번 반복하는 데에 0.0026 초로 가장 빨랐습니다.

import timeit
from random import randint

list = [8, 2, 6, 4, 5, 5, 7, 2, 3, 9, 1, 0, 2, 7, 6]

def bubble_sort(array=list):
    n = len(array)
    for i in range(n):
        already_sorted = True
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                already_sorted = False
        if already_sorted:
            break
    return array

def insertion_sort(array=list):
    for i in range(1, len(array)):
        key_item = array[i]
        j = i - 1
        while j >= 0 and array[j] > key_item:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key_item
    return array

def quicksort(array=list):
    if len(array) < 2:
        return array
    low, same, high = [], [], []
    pivot = array[randint(0, len(array) - 1)]
    for item in array:
        if item < pivot:
            low.append(item)
        elif item == pivot:
            same.append(item)
        elif item > pivot:
            high.append(item)
    return quicksort(low) + same + quicksort(high)

print(list)
print('bubble', bubble_sort(), timeit.timeit(bubble_sort, number=1000))
print('insertion', insertion_sort(), timeit.timeit(insertion_sort, number=1000))
print('quicksort', quicksort(), timeit.timeit(quicksort, number=1000))

번호 제목 글쓴이 날짜 조회 수
공지 장애 복구 안내 [9] 관리자 2017.05.04 93349
935 [알림] 홈페이지 리뉴얼과 게시판 변경에 관하여 [4] 관리자 2010.12.23 319586
934 제주 전용서체 [5] file Progress 2010.06.15 210729
933 [공지] ko.TeX Live 2010 발표 [11] 관리자 2010.11.07 186915
932 ko.TeX Live 2013 배포 [6] file 관리자 2013.10.12 172619
931 한글텍사용자그룹/한국텍학회 웹 사이트 및 서비스 복구에 관한 말씀 관리자 2013.05.06 157792
930 [공지] ko.TeX Live 2009 발표 [9] MadToad 2009.12.23 147598
929 TeX의 수명이 긴 이유 그리고 널리 쓰이지 않는 이유 [45] 메타 2010.06.02 143192
928 [공지] ko.TeX Live 2011 발표 [9] 관리자 2011.07.29 139872
927 [공지] お知らせ: TeXユーザの集い 2010 開催予定 (10/23土@東大生研) [1] ChoF 2010.02.01 135159
926 TeX Live 2016 pretest 설치 안내 [11] 관리자 2016.06.05 134128
925 MathJax를 이용하여 웹에서 수식을 써 봅시다 [26] file 샘처럼 2010.12.29 132553
924 An Earthshaking Announcement [6] 작은나무 2010.07.12 128729
923 prologue vs preamble vs preface vs foreword 는 무슨 차이인가요? [4] 에드 2011.02.23 125949
922 TeX Live 2010을 대비한 ko.TeX 프리테스트 [14] DohyunKim 2010.07.14 125138
921 TeX Live 2013과 ko.TeX 설치 관련 안내 [11] 관리자 2013.09.01 123926
920 [공지] 한국텍학회 회비를 입금한 분들 중 회원 미등록자 분들께 [7] 관리자 2011.10.20 121212
919 (ko.) TeX Live 2014 설치를 권장합니다. [37] nanim 2014.07.14 117580
918 [공지] ko.TeX Live 2010 패치 [3] 관리자 2011.04.13 106132
917 Apple 산돌고딕 Neo 폰트 패밀리 [3] file Progress 2012.09.05 97424
916 [참가신청] 문서작성 워크숍 2013 [6] file 관리자 2013.10.10 96494



XE Login