CSE117 프로그래밍기초강의노트 1 10 프로그램디자인사례 : 정렬 Program Design Case Study: Sorting 한양대학교 ERICA캠퍼스컴퓨터공학과도경구 2013년 2학기 (version 0.8) 1 c 도경구 (2013). 본문서는한양대학교 ERICA 캠퍼스컴퓨터공학과프로그래밍기초강의용으로제 작되었습니다. 강의이외의용도로저자의허락없이무단복제하여배포할수없습니다.
정렬문제란크기비교가가능한데이터의시퀀스를오름또는내림차순으로재배치하는문제를말한다. 즉, 다음의정수리스트를오름차순으로정렬하면, [4,2,3,1,6,8,3,2,6,7] 다음과같이된다. [1,2,2,3,3,4,6,6,7,8] 이장에서는정수리스트를오름차순으로정렬하는함수를다양한알고리즘을적용하여파이썬함수로작성해본다. 먼저리스트구조부터공부하자. 1. ( 진짜 ) 리스트갖고놀기 Python의리스트는배열 (array) 과같이위치번호로접근과수정이가능하기때문에리스트연산이가능하고모양이리스트와같음에도불구하고엄밀히따져서리스트라고할수없다. 진짜리스트를공부해보자. 정수리스트는다음과같이귀납으로정의할수있다. 1. nil은정수리스트이다. 2. n이정수이고, ns가정수리스트이면, cons(n,ns) 는정수리스트이다. 3. 다른정수리스트는없다. 이정의를사용하면다음과같이정수리스트를만들수있다. nil cons(3,nil) cons(3,cons(4,nil)) cons(7,cons(2,cons(4,nil)))... 잘보면, cons( 콘스 로읽음 ) 는주어진정수와정수리스트를결합하여새로운정수리스트를만드는연산자이다. 리스트를결합하는연산자가있으므로분리하는연산자도있어야한다. 전통적으로 (1950년대만든 LISP라는언어에서유래 ) 분리연산자는 car( 카 로읽음 ) 와 cdr( 쿠더 로읽음 ) 라고하며다음과같이작동한다. car(cons(n,ns)) = n cdr(cons(n,ns)) = ns 이연산자로리스트계산을직접해보기위해서 Python으로함수를다음과같이정의하고이연산자만사용하여프로그램을만들어보자. 1
nil = [] def null(ns): return ns == nil def cons(n,ns): return [n] + ns def car(ns): return ns[0] def cdr(ns): return ns[1:] 리스트를취급하는프로그램을디자인할때이러한귀납적인구조를이용하여재귀프로그램을만들수있다. 정수리스트길이계산하기정수리스트 xs의길이를계산하는함수 length는정수리스트의귀납구조를따라서다음과같이고안할수있다. 1. 정수리스트 xs가 nil이면, 길이는 0이다. 2. 정수리스트 xs의길이가 l이면, cons(x,xs) 의길이는 l + 1이다. 이아이디어로재귀함수를짜면다음과같다. def length(xs): if null(xs): return 0 else: return 1 + length(cdr(xs)) 꼬리재귀형태로바꾸면, def length(xs): def loop(xs,l): if null(xs): return l else: return loop(cdr(xs),l+1) return loop(xs,0) 2
while 루프로바꾸면, def length(xs): = 0 while not null(xs): xs = cdr(xs) l = l + 1 return l 정수리스트붙이기두개의정수리스트 xs와 ys를붙이는함수 append는첫인수정수리스트 xs의귀납구조를따라서다음과같이작성할수있다. def append(xs,ys): if null(xs): return ys else: return cons(car(xs),append(cdr(xs),ys)) 이함수를꼬리재귀형태로그대로바꾸려면쉽지않다. 하지만 xs를뒤집어놓으면자연스럽게꼬리재귀함수를만들수있다. 리스트를뒤집는함수 reverse가있다고가정하고만들어보자. def append(xs,ys): def loop(xs,rs): if null(xs): return rs else: return loop(cdr(xs),cons(car(xs),rs)) return loop(reverse(xs),ys) while 루프로바꾸면, def append(xs,ys): xs = reverse(xs) rs = ys while not null(xs): xs, rs = cdr(xs), cons(car(xs),rs) return rs 3
정수리스트뒤집기정수리스트 xs를뒤집는함수 reverse는 xs의귀납구조를따라서다음과같이작성할수있다. append를사용할수밖에없음에주목하자. def reverse(xs): if null(xs): return xs else: return append(reverse(cdr(xs)),cons(car(xs),nil)) 이함수를꼬리재귀형태로바꾸면아주자연스러워진다. def reverse(xs): def loop(xs,rs): if null(xs): return rs else: return loop(cdr(xs),cons(car(xs),rs)) return loop(xs,nil) while 루프로바꾸면, def reverse(xs): rs = nil while not null(xs): xs, rs = cdr(xs), cons(car(xs),rs) return rs 2. 삽입정렬 (Insertion Sort) 삽입정렬은다음과같은전략으로정렬한다. 정렬할정수리스트 xs에서수를앞에서부터하나씩꺼내서새로운리스트를만들면서정렬이되도록제위치에끼워넣는다. 예를들어, cons(3,cons(6,cons(5,cons(2,cons(4,nil))))) 은다음과같이정렬한다. 3을꺼내어 cons(3,nil) 을만든다. 6을꺼내어 cons(3,nil) 의제위치에끼워넣어 cons(3,cons(6,nil)) 을만든다. 5를꺼내어 cons(3,cons(6,nil)) 의제위치에끼워넣어 cons(3,cons(5,cons(6,nil))) 을만든다. 4
2를꺼내어 cons(3,cons(5,cons(6,nil))) 의제위치에끼워넣어 cons(2,cons(3,cons(5,cons(6,nil)))) 을만든다. 4를꺼내어 cons(2,cons(3,cons(5,cons(6,nil)))) 의제위치에끼워넣어 cons(2,cons(3,cons(4,cons(5,cons(6,nil))))) 을만든다. 삽입정렬프로그램디자인정수리스트의귀납적구조를이용하여재귀적으로삽입정렬프로그램을디자인해보자. 정수리스트 xs를정렬하는함수 isort(xs) 는다음과같이디자인한다. xs가비어있으면, 정렬할필요가없다. xs가비어있지않으면, 재귀적으로 isort(cdr(xs)) 를호출하여 cdr(xs) 를먼저정렬한후, 그리스트의정렬이흩틀어지지않도록적절한위치에첫째아이템 car(xs) 을끼워넣는다. 이를프로그램으로작성하면다음과같다. 1 def isort(xs): 2 if null(xs): 3 return nil 4 else: 5 return insert(car(xs),isort(cdr(xs))) 이제아이템 x를정렬된리스트 ss에정렬을흩트리지않으면서제위치에끼워넣는 insert(x,ss) 를디자인해보자. ss가 nil이면 ( 비어있으면 ), x를끼워넣은결과는 cons(x,nil) 가된다. ss가 nil이아니고, x가 ss의첫째아이템 car(ss) 보다작거나같으면, x를 ss의맨앞에붙여서 cons(x,ss) 를만들면된다. ss가 nil이아니고, x가 ss의첫째아이템 car(ss) 보다크면, insert(x,cdr(ss)) 를재귀호출하여 x를정렬된리스트 cdr(ss) 에끼워넣는다. 이를프로그램으로작성하면다음과같다. 1 def insert(x,ss): 2 if null(ss): 3 return cons(x,nil) 4 elif x <= car(ss): 5 return cons(x,ss) 6 else: 7 return cons(car(ss),insert(x,cdr(ss))) 5
실행추적 다음과같이특정입력리스트로실행추적을해보면프로그램이어떻게실행되는지살펴볼수 있다. isort(cons(3,cons(6,cons(5,cons(2,cons(4,nil)))))) insert(3,isort(cons(6,cons(5,cons(2,cons(4,nil)))))) insert(3,insert(6,isort(cons(5,cons(2,cons(4,nil)))))) insert(3,insert(6,insert(5,isort(cons(2,cons(4,nil)))))) insert(3,insert(6,insert(5,insert(2,isort(cons(4,nil)))))) insert(3,insert(6,insert(5,insert(2,insert(4,isort(nil)))))) insert(3,insert(6,insert(5,insert(2,insert(4,nil))))) insert(3,insert(6,insert(5,insert(2,cons(4,nil))))) insert(3,insert(6,insert(5,cons(2,cons(4,nil))))) insert(3,insert(6,cons(2,insert(5,cons(4,nil))))) insert(3,insert(6,cons(2,cons(4,insert(5,nil))))) insert(3,insert(6,cons(2,cons(4,cons(5,nil))))) insert(3,cons(2,insert(6,cons(4,cons(5,nil))))) insert(3,cons(2,cons(4,insert(6,cons(5,nil))))) insert(3,cons(2,cons(4,cons(5,insert(6,nil))))) insert(3,cons(2,cons(4,cons(5,cons(6,nil))))) cons(2,insert(3,cons(4,cons(5,cons(6,nil))))) cons(2,cons(3,cons(4,cons(5,cons(6,nil))))) 성능분석 이함수들은원초적재귀함수형식으로작성하였다. 삼입정렬하는작업은재귀함수 isort 로구현하였고, 정렬된리스트에원소를하나씩끼워넣는작업은재귀함수 insert 로구현하 였다. 정렬할리스트 xs 의길이를 n 이라고하면, isort 함수는 n 번호출된다. insert 함수는 원소를하나씩정렬된리스트의제위치에끼워넣는다. 정렬된리스트의길이가 k 이면, 맨뒤에 끼워넣는경우 insert 함수를 k 번호출한다. 하지만운이좋아맨앞에끼워넣는경우 1 번밖에 호출하지않는다. 즉, insert 함수를호출하는횟수는끼워넣는원소와대상리스트의내용에 따라서다르다. 맨앞에붙이는경우가최선의경우이며, 맨뒤에붙이는경우가최악의경우이 다. 정렬할리스트가완전히역순으로정렬이되어있으면최악의경우이고, 정렬할리스트가 이미완전히정렬되어있으면최선의경우이다. 최선의경우에는 insert 함수호출횟수는 n 번 밖에안되지만, 최악의경우에는 Σ n i=1i = n(n + 1)/2 가되어, insert 함수를호출하는횟수로 기준으로최악의경우실행시간은리스트의길이의제곱에비례한다고할수있다. 6
공간효율향상원초적재귀함수형식은재귀호출에서돌아온후해야할계산을남기므로이를기록하는만큼의저장공간이추가로필요하다. 이를피하기위해서위의두함수를꼬리재귀함수형식으로변환한뒤, 루프버전으로변환해보자. 먼저 insert 함수를꼬리재귀함수형식으로변환하면다음과같이된다. 1 def insert(x,ss): 2 def loop(ss,rs): 3 if null(ss): 4 return append(rs,cons(x,nil)) 5 elif x <= car(ss): 6 return append(rs,cons(x,ss)) 7 else: 8 return loop(cdr(ss),append(rs,cons(car(ss),nil))) 9 return loop(ss,nil) 다음, isort 함수도꼬리재귀함수형식으로변환하면다음과같이된다. 1 def isort(xs): 2 def loop(xs,ss): 3 if null(xs): 4 return ss 5 else: 6 return loop(cdr(xs),insert(car(xs),ss)) 7 return loop(xs,nil) while 루프를사용하여변환하면다음과같다. 이두프로그램은모양만다를뿐작동방식이같으므로성능의차이는없다. 1 def insert(x,ss): 2 rs = nil 3 while not null(ss): 4 if x <= car(ss): 5 break 6 else: 7 rs = append(rs,cons(car(ss,nil))) 8 ss = cdr(ss) 9 return append(rs,cons(x,ss)) 7
1 def isort(xs): 2 ss = nil 3 while not null(xs): 4 ss = insert(car(xs),ss) 5 xs = cdr(xs) 6 return ss 파이썬의 for 루프를사용하면프로그램이더간결해진다. 1 def isort(xs): 2 ss = nil 3 for x in xs: 4 ss = insert(x,ss) 5 return ss 공간은절약하였지만 insert 함수를호출하는횟수는줄지않는다. 즉, 시간적인효율성은 변함이없다. 3. 선택정렬 (Selection Sort) 선택정렬은다음과같은전략으로정렬한다. 정수리스트 xs가주어지면, 그리스트를정렬되지않은리스트로놓고, 그리스트전체를훑어서제일작은수하나를꺼내어정렬된리스트로만들어나간다. 정렬되지않은리스트가빌때까지그과정을반복한다. 예를들어, [3,6,5,2,4] 은다음과같이정렬한다. [3,6,5,2,4] 에서 2을꺼내어 [2] 를만든다. [3,6,5,4] 에서 3을꺼내어 [2,3] 을만든다. [6,5,4] 에서 4를꺼내어 [2,3,4] 를만든다. [6,5] 에서 5를꺼내어 [2,3,4,5] 를만든다. [6] 에서 6을꺼내어 [2,3,4,5,6] 을만든다. 선택정렬프로그램디자인정수리스트의귀납구조를이용하여재귀적으로선택정렬프로그램을원초적재귀함수형식으로디자인해보자. 정수리스트 xs를정렬하는함수 ssort는다음과같이디자인한다. xs가비어있으면, 정렬된결과리스트도비어있다. 8
xs가비어있지않으면, xs에서가장작은아이템을하나떼어와서줄세우고, 나머지리스트도같은방법으로재귀적으로정렬한다. 그러면리스트에서가장작은아이템을어떻게떼어올까? 여러가지방법이있을텐데우리는다음과같은방법을써보자. 리스트전체를훑어서가장작은값을찾은뒤그값을맨앞으로옮긴다. 이역할을하는함수를 select라고하자. 그러면 select(xs) 를호출하면 xs에서가장작은값을맨앞으로옮긴리스트를결과로내주게될것이다. select 함수를써서선택정렬함수를작성하면다음과같다. 1 def ssort(xs): 2 if null(xs): 3 return nil 4 else: 5 ys = select(xs) 6 return cons(car(ys),ssort(cdr(ys))) 이제 select 함수를역시재귀로디자인해보자. 입력리스트 xs가주어졌을때, xs에원소가하나밖에없으면그냥그대로내주면된다. xs에원소가둘이상있으면, 앞의두원소를꺼내서비교한다. 둘중작은원소를선택하여나머지리스트와붙여서재귀적으로호출하여결과리스트를얻은후, 큰원소는뒤에붙인다. 이를원초적재귀함수형식으로작성하면다음과같다. 1 def select(xs): 2 if length(xs) <= 1: 3 return xs 4 else: 5 first = car(xs) 6 second = car(cdr(xs)) 7 if first < second: 8 rest = cdr(cdr(xs)) 9 return append(select(cons(first,rest)),cons(second,nil)) 10 else: 11 rest = cdr(xs) 12 return append(select(rest),cons(first,nil)) 9
실행추적 다음과같이특정입력리스트로실행추적을해보면프로그램이어떻게실행되는지살펴볼수 있다. ssort(cons(3,cons(6,cons(5,cons(2,cons(4,nil)))))) ys = select(cons(3,cons(6,cons(5,cons(2,cons(4,nil)))))) first = 3 second = 6 rest = cons(5,cons(2,cons(4,nil))) append(select(cons(3,cons(5,cons(2,cons(4,nil))))),cons(6,nil)) first = 3 second = 5 rest = cons(2,cons(4,nil)) append(select(cons(3,cons(2,cons(4,nil)))),cons(5,nil)) first = 3 second = 2 rest = cons(2,cons(4,nil)) append(select(cons(2,cons(4,nil))),cons(3,nil)) first = 2 second = 4 rest = nil append(select(cons(2,nil)),cons(4,nil)) cons(2,nil) cons(2,cons(4,nil)) cons(2,cons(4,cons(3,nil))) cons(2,cons(4,cons(3,cons(5,nil)))) cons(2,cons(4,cons(3,cons(5,cons(6,nil))))) cons(2,ssort(cons(4,cons(3,cons(5,cons(6,nil)))))) ys = select(cons(4,cons(3,cons(5,cons(6,nil))))) first = 4 second = 3 rest = cons(3,cons(5,cons(6,nil))) append(select(cons(3,cons(5,cons(6,nil)))),cons(4,nil)) first = 3 second = 5 rest = cons(6,nil) append(select(cons(3,cons(6,nil))),cons(5,nil)) first = 3 second = 6 rest = nil append(select(cons(3,nil)),cons(6,nil)) cons(3,nil) cons(3,cons(6,nil)) cons(3,cons(6,cons(5,nil))) cons(3,cons(6,cons(5,cons(4,nil)))) 10
cons(3,ssort(cons(6,cons(5,cons(4,nil))))) ys = select(cons(6,cons(5,cons(4,nil)))) first = 6 second = 5 rest = cons(5,cons(4,nil)) append(select(cons(5,cons(4,nil))),cons(6,nil)) first = 5 second = 4 rest = cons(4,nil) append(select(cons(4,nil)),cons(5,nil)) cons(4,nil) cons(4,cons(5,nil)) cons(4,cons(5,cons(6,nil))) cons(4,ssort(cons(5,cons(6,nil)))) ys = select(cons(5,cons(6,nil))) first = 5 second = 6 rest = nil append(select(cons(5,nil)),cons(6,nil)) cons(5,nil) cons(5,cons(6,nil)) cons(5,ssort(cons(6,nil))) ys = select(cons(6,nil)) cons(6,nil) cons(6,ssort(nil)) nil cons(6,nil) cons(5,cons(6,nil)) cons(4,cons(5,cons(6,nil))) cons(3,cons(4,cons(5,cons(6,nil)))) cons(2,cons(3,cons(4,cons(5,cons(6,nil))))) 성능분석 이함수들은원초적재귀함수형식으로작성하였다. 선택정렬하는작업은재귀함수 ssort 로 구현하였고, 리스트에서제일작은값을맨앞에옮기는작업은재귀함수 select 로구현하였 다. ssort 함수는입력리스트 xs 의길이만큼재귀호출되고, select 함수도입력리스트 xs 의 길이만큼재귀호출된다. 전체적으로 xs 의길이를 n 으로놓고 select 함수를호출하는횟수를 기준단위로실행시간을따져보면정확하게 Σ n i=1i = n(n + 1)/2 가되어, 입력리스트의길이의제곱에비례한다고할수있다. 여기서입력리스트의내용과무관하게항상 select 함수호출 횟수는같다. 11
공간효율향상원초적재귀함수형식은재귀호출에서돌아온후해야할계산을남기므로이를기록하는만큼의저장공간이추가로필요하다. 이를피하기위해서위의두함수를꼬리재귀함수형식으로변환해보자. 먼저 select 함수를꼬리재귀함수형식으로변환하면다음과같이된다. 1 def select(xs): 2 def loop(xs,rs): 3 if length(xs) <= 1: 4 return append(xs,rs) 5 else: 6 first = car(xs) 7 second = car(cdr(xs)) 8 if first < second: 9 rest = cdr(cdr(xs)) 10 return loop(cons(first,rest),cons(second,rs)) 11 else: 12 rest = cdr(xs) 13 return loop(rest,cons(first,rs)) 14 return loop(xs,nil) 다음, ssort 함수도꼬리재귀함수형식으로변환하면다음과같이된다. 1 def ssort(xs): 2 def loop(xs,rs): 3 if null(xs): 4 return rs 5 else: 6 ys = select(xs) 7 return loop(cdr(ys),append(rs,cons(car(ys),nil))) 8 return loop(xs,nil) 실행추적꼬리재귀함수도같은입력리스트로실행추적해보자. ssort1([3,6,5,2,4]) loop([3,6,5,2,4],[]) ys = select1([3,6,5,2,4]) 12
loop([3,6,5,2,4],[]) loop([3,5,2,4],[6]) loop([3,2,4],[5,6]) loop([2,4],[3,5,6]) loop([2],[4,3,5,6]) [2,4,3,5,6] loop([4,3,5,6],[2]) ys = select1([4,3,5,6]) loop([4,3,5,6],[]) loop([3,5,6],[4]) loop([3,6],[4,5]) loop([3],[4,5,6]) [3,4,5,6] loop([4,5,6],[2,3]) ys = select1([4,5,6]) loop([4,5,6],[]) loop([4,6],[5]) loop([4],[5,6]) [4,5,6] loop([5,6],[2,3,4]) ys = select1([5,6]) loop([5,6],[]) loop([5],[6]) [5,6] loop([6],[2,3,4,5]) ys = select1([6]) [6] loop([],[2,3,4,5,6]) [2,3,4,5,6] 꼬리재귀호출은돌아와서할계산을남기지않으므로그만큼의공간을절약할수있다. 하지만 select 함수를호출하는횟수를원천적으로줄일수있는방법은없다. 즉, 시간적인효율성은같다. 루프버전 꼬리재귀함수프로그램은 while 루프를사용하여다음과같이재작성할수있다. 이두프로 그램은모양만다를뿐작동방식이같으므로성능의차이는없다. 13
1 def select(xs): 2 rs = nil 3 while length(xs) > 1: 4 first = car(xs) 5 second = car(cdr(xs)) 6 if first < second: 7 rest = cdr(cdr(xs)) 8 xs = cons(first,rest) 9 rs = cons(second,rs) 10 else: 11 rest = cdr(xs) 12 xs = rest 13 rs = cons(first,rs) 14 return append(xs,rs) 1 def ssort(xs): 2 rs = nil 3 while not null(xs): 4 ys = select(xs) 5 xs = cdr(ys) 6 rs = append(rs,cons(car(ys),nil)) 7 return rs 4. 합병정렬 (Merge Sort) 합병정렬은다음과같은전략으로정렬한다. 정수리스트 xs가주어지면, 그리스트를반으로나누어각각재귀적으로정렬한후, 두정렬된리스트를하나의정렬된리스트로합병한다. 예를들어, [3,6,5,2,4,1,8,7] 는다음과같이정렬한다. [3,6,5,2] 와 [4,1,8,7] 로반으로나누어각각정렬한다. 정렬된두리스트 [2,3,5,6] 과 [1,4,7,8] 을앞에서부터차례로훑어가며작은수를먼저선택하는방식으로하나로합병한다. 그결과로 [1,2,3,4,5,6,7,8] 을얻는다. 14
합병정렬프로그램디자인앞에서와마찬가지로정수리스트의귀납적구조를이용하여재귀적으로합병정렬프로그램을디자인해보자. 정수리스트 xs를합병정렬하는함수 msort는다음과같이디자인한다. xs가비어있거나아이템이하나밖에없으면정렬할필요가없다. 그렇지않으면, xs를반으로쪼개서각각 ls와 rs하고하고 msort(ls) 와 msort(rs) 를각각재귀적으로호출하여정렬하고 두개의정렬된리스트를하나의정렬된리스트로합병한다. 아래프로그램은이방법을그대로적용하여원초적재귀함수형식으로작성한정렬함수이다. split 함수는리스트를반으로쪼개서내주는일을하고, 재귀함수 merge는두개의정렬된리스트를하나의정렬된리스트로합병하는일을하고, 재귀함수 msort는합병정렬하는일을한다. 1 def split(xs,mid): 2 def lefthalf(xs,mid): 3 if mid <= 0: 4 return nil 5 else: 6 return cons(car(xs),lefthalf(cdr(xs),mid-1)) 7 def righthalf(xs,mid): 8 if mid <= 0: 9 return xs 10 else: 11 return righthalf(cdr(xs),mid-1) 12 return lefthalf(xs,mid),righthalf(xs,mid) 1 def msort(xs): 2 if null(xs) or null(cdr(xs)): 3 return xs 4 else: 5 mid = length(xs) // 2 6 ls, rs = split(xs,mid) 7 return merge(msort(ls),msort(rs)) 1 def merge(xs,ys): 2 if null(xs) or null(ys): 15
3 return append(xs,ys) 4 elif car(xs) < car(ys): 5 return cons(car(xs),merge(cdr(xs),ys)) 6 else: 7 return cons(car(ys),merge(xs,cdr(ys))) 실행추적 msort를호출하여계산절차을추적해보자. msort(cons(3,cons(6,cons(5,cons(2,cons(4,cons(1,cons(8,cons(7,nil))))))))) merge(msort(cons(3,cons(6,cons(5,cons(2,nil))))), msort(cons(4,cons(1,cons(8,cons(7,nil)))))) merge(merge(msort(cons(3,cons(6,nil))),msort(cons(5,cons(2,nil)))), merge(msort(cons(4,cons(1,nil))),msort(cons(8,cons(7,nil))))) merge(merge(merge(msort(cons(3,nil)),msort(cons(6,nil))), merge(msort(cons(5,nil)),msort(cons(2,nil)))), merge(merge(msort(cons(4,nil)),msort(cons(1,nil))), merge(msort(cons(8,nil)),msort(cons(7,nil))))) merge(merge(merge(cons(3,nil),cons(6,nil)), merge(cons(5,nil),cons(2,nil))), merge(merge(cons(4,nil),cons(1,nil)), merge(cons(8,nil),cons(7,nil)))) merge(merge(cons(3,cons(6,nil)),cons(2,cons(5,nil))), merge(cons(1,cons(4,nil)),cons(7,cons(8,nil)))) merge(cons(2,cons(3,cons(5,cons(6,nil)))), cons(1,cons(4,cons(7,cons(8,nil))))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,cons(7,cons(8,nil)))))))) 위의계산추적에서는 merge 함수의실행추적은자세히보여주지않았다. 하나만대표로추적해보자. merge(cons(2,cons(3,cons(5,cons(6,nil)))), cons(1,cons(4,cons(7,cons(8,nil))))) cons(1,merge(cons(2,cons(3,cons(5,cons(6,nil)))), cons(4,cons(7,cons(8,nil))))) cons(1,cons(2,merge(cons(3,cons(5,cons(6,nil))),cons(4,cons(7,cons(8,nil)))))) cons(1,cons(2,cons(3,merge(cons(5,cons(6,nil)),cons(4,cons(7,cons(8,nil))))))) cons(1,cons(2,cons(3,cons(4,merge(cons(5,cons(6,nil)),cons(7,cons(8,nil))))))) 16
cons(1,cons(2,cons(3,cons(4,cons(5,merge(cons(6,nil),cons(7,cons(8,nil))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,merge(nil,cons(7,cons(8,nil))))))))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,append(nil,cons(7,cons(8,nil))))))))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,cons(7,cons(8,nil)))))))) split 함수를순수리스트로만들다보니복잡해졌지만, Python 리스트 ( 사실상배열 ) 의범위자르기를이용하면다음과같이간단해진다. 1 def split(xs,mid): 2 return xs[:mid], xs[mid:] 시간및공간효율향상 merge 함수를꼬리재귀형식으로변환하면다음과같이된다. 1 def merge(xs,ys): 2 def loop(xs,ys,rs): 3 if null(xs) or null(ys): 4 return append(rs,append(xs,ys)) 5 elif car(xs) < car(ys): 6 return loop(cdr(xs),ys,append(rs,cons(car(xs),nil))) 7 else: 8 return loop(xs,cdr(ys),append(rs,cons(car(ys),nil))) 9 return loop(xs,ys,nil) 이꼬리재귀형식의프로그램은쉽게 while 루프형식으로프로그램으로다음과같이변환할수있다. 1 def merge(xs,ys): 2 rs = nil 3 while not null(xs) and not null(ys): 4 if car(xs) < car(ys): 5 rs = append(rs,cons(car(xs),nil)) 6 xs = cdr(xs) 7 else: 8 rs = append(rs,cons(car(ys),nil)) 9 ys = cdr(ys) 10 return append(rs,append(xs,ys)) 17
성능분석합병절렬알고리즘은일반적으로앞에서공부한삽입정렬과선택정렬과비교해서정렬하는시간이빠르다. 이를계산하는건알고리즘을분석하는수학적기술을이해해야하므로여기서자세한언급은피하겠다. 추후에 알고리즘설계및분석 과목에서자세히배우게될것이다. 연습문제 split 함수를꼬리재귀형태로바꾼뒤, while 루프로된프로그램으로변환해보자. 5. 퀵정렬 (Quick Sort) 퀵정렬은영국의유명한컴퓨터학자 C.A.R. Hoare가 60년대에고안해낸알고리즘이다. 이알고리즘은합병정렬과비슷하나대상리스트를무조건반으로쪼개는대신피봇 (pivot) 이라고하는기준값을선택하고그값을기준으로작은값만들어있는리스트와큰값만들어있는리스트로나눈후, 재귀적으로정렬한다. 합병정렬은무조건반으로나누어재귀적으로정렬하므로추후에합병절차가필요하지만. 퀵정렬은피봇값을중심으로작은값과큰값을따로끼리끼리나누는수고를미리하고재귀적으로정렬하므로뒤에합병하는절차는필요없다. 퀵정렬프로그램디자인정수리스트 xs를퀵정렬하는함수 qsort는다음과같이디자인한다. xs가비어있거나아이템이하나밖에없으면정렬할필요가없다. 그렇지않으면, pivot이라고하는기준아이템을리스트에서하나고른다. 여기에서는편의상맨앞아이템을고르기로한다. ( 사실피봇값을잘골라서리스트가항상반으로쪼개질때퀵정렬의성능이가장좋으므로피봇값을고르는작업은중요하다.) 그 pivot 아이템을기준으로작은아이템은왼쪽리스트에, 큰아이템은오른쪽리스트에있도록옮긴다음리스트를쪼갠다. 왼쪽리스트를재귀적으로정렬하고, 오른쪽리스트를재귀적으로정렬한다음, pivot 아이템은그사이에끼운다. 다음프로그램은이전략을그대로적용하여, 원초적재귀함수형식으로작성한정렬함수이다. 퀵정렬하는작업은재귀함수 qsort로구현하였고, pivot 아이템을기준으로작거나같은아이템은왼쪽리스트에, 큰아이템은오른쪽리스트에있도록리스트를쪼개는작업은재귀함수 partition으로구현하였다. 1 def qsort(xs): 2 if null(xs): 18
3 return xs 4 else: 5 pivot = car(xs) 6 ls, rs = partition(pivot,cdr(xs)) 7 return append(qsort(ls),cons(pivot,qsort(rs))) 1 def partition(pivot,xs): 2 if null(xs): 3 return nil,nil 4 else: 5 ls, rs = partition(pivot,cdr(xs)) 6 if car(xs) <= pivot: 7 return cons(car(xs),ls), rs 8 else: 9 return ls, cons(car(xs),rs) 실행추적 qsort를호출하여계산절차을추적해보자. qsort(cons(3,cons(6,cons(5,cons(2,cons(4,cons(1,cons(8,cons(7,nil))))))))) append(qsort(cons(2,cons(1,nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(qsort(cons(1,nil)), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(append(qsort(nil),cons(1,qsort(nil)))), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(append(nil,cons(1,qsort(nil)))), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(append(nil,cons(1,nil))), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(cons(1,nil)), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) 19
append(append(cons(1,nil)), cons(2,nil)), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) cons(3,append(qsort(cons(5,cons(4,nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(qsort(cons(4,nil)), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(append(qsort(nil),cons(4,qsort(nil))), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(append(nil,cons(4,qsort(nil))), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(append(nil,cons(4,nil)), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(cons(4,nil), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(cons(4,nil), cons(5,nil)), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(cons(4,cons(5,nil)), 20
cons(6,append(qsort(cons(7,nil)), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(append(qsort(nil), cons(7,qsort(nil))), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(append(nil, cons(7,qsort(nil))), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(append(nil, cons(7,nil)), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(cons(7,nil), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(cons(7,nil), cons(8,nil)))))) cons(3,append(cons(4,cons(5,nil)), cons(6,cons(7,cons(8,nil)))))) cons(3,cons(4,cons(5,cons(6,cons(7,cons(8,nil))))))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,cons(7,cons(8,nil)))))))) 위의계산추적에서는 partition 함수의실행추적은자세히보여주지않았다. 하나만대표로해보자. partition(6,cons(5,cons(4,cons(8,cons(7,nil))))) xs = cons(5,cons(4,cons(8,cons(7,nil)))) ls,rs = partition(6,cons(4,cons(8,cons(7,nil)))) xs = cons(4,cons(8,cons(7,nil))) 21
ls,rs = partition(6,cons(8,cons(7,nil))) xs = cons(8,cons(7,nil)) ls,rs = partition(6,cons(7,nil)) xs = cons(7,nil) ls,rs = partition(6,nil) nil,nil nil,cons(car(xs),nil) nil,cons(7,nil) nil,cons(car(xs),cons(7,nil)) nil,cons(8,cons(7,nil)) cons(car(xs),nil),cons(8,cons(7,nil)) cons(4,nil),cons(8,cons(7,nil)) cons(car(xs),cons(4,nil)),cons(8,cons(7,nil)) cons(5,cons(4,nil)),cons(8,cons(7,nil)) 이함수도꼬리재귀형태로재작성해보자. 1 def partition(pivot,xs): 2 def loop(xs,ls,rs): 3 if null(xs): 4 return ls, rs 5 elif car(xs) <= pivot: 6 return loop(cdr(xs),cons(car(xs),ls),rs) 7 else: 8 return loop(cdr(xs),ls,cons(car(xs),rs)) 9 return loop(xs,nil,nil) 위와같은예로실행추적을해보면다음과같다. partition(6,cons(5,cons(4,cons(8,cons(7,nil))))) loop(cons(5,cons(4,cons(8,cons(7,nil)))),nil,nil) loop(cons(4,cons(8,cons(7,nil))),cons(5,nil),nil) loop(cons(8,cons(7,nil)),cons(4,cons(5,nil))) loop(cons(7,nil),cons(4,cons(5,nil)),cons(8,nil)) loop(nil,cons(4,cons(5,nil)),cons(7,cons(8,nil))) cons(4,cons(5,nil)),cons(7,cons(8,nil)) 결과는다르지만정렬에는영향을미치지않는다. 위의꼬리재귀함수는다음과같이 while 루프로만된함수로변환할수있다. 22
1 def partition(pivot,xs): 2 ls, rs = nil, nil 3 while not null(xs): 4 if car(xs) <= pivot: 5 ls = cons(car(xs),ls) 6 else: 7 rs = cons(car(xs),rs) 8 xs = cdr(xs) 9 return ls, rs 제자리정렬지금까지살펴본퀵정렬프로그램은 partition을할때마다새로운리스트를만들어나간다. 정렬대상리스트의길이가 n일때, 최선의경우 log n배에서최악의경우 n배만큼의리스트를저장할메모리를추가로사용해야한다. 정렬하면서새로운리스트를만들어가면서추가메모리를사용하는대신, 있는그자리에서서로위치만바꾸면서정렬할수있으면공간을절약할수있다. 이와같이추가공간을사용하지않고서로위치만바꾸면서하는정렬을제자리정렬 in-place sorting이라고한다. 순수리스트를조작해서는제자리정렬이불가능하다. 배열 (Python의리스트 ) 을사용하면가능하다. 제자리정렬하는퀵정렬프로그램을만들어보자. 1 def quicksort(xs): 2 def loop(xs,start,finish): 3 if start >= finish: 4 return xs 5 else: 6 pivotindex = start # 맨앞의값을 pivot으로정함 7 pivotindex = permutepivot(xs,start,finish,pivotindex) 8 xs = loop(xs,start,pivotindex-1) 9 return loop(xs,pivotindex+1,finish) 10 return loop(xs,0,len(xs)-1) 다음함수 swap(xs,i,j) 는리스트 xs 에서 i 번째값과 j 번째값을바꾼다. 1 def swap(xs,i,j): 2 xs[i], xs[j] = xs[j], xs[i] 다음함수 permutepivot(xs,start,finish,pivotindex) 는리스트 xs 의시작위치 start, 끝 위치 finish, 피봇위치 pivotindex 의인덱스를가지고, pivotindex 의값을기준으로작은값은 23
모두왼쪽으로옮기고, 큰값은모두오른쪽으로옮긴후, 피봇값을그사이에넣고, 그위치인텍스를결과로내준다. 1 def permute_pivot(xs,start,finish,pivot_index): 2 def loop(xs,i,j): 3 if i == j: 4 if xs[i] > pivot: 5 i = i - 1 6 swap(xs,start,i) 7 return i 8 else: 9 if xs[j] >= pivot: 10 return loop(xs,i,j-1) 11 else: 12 swap(xs,i,j) 13 return loop(xs,i+1,j) 14 swap(xs,start,pivot_index) 15 pivot = xs[start] 16 return loop(xs,start+1,finish) 위프로그램을 while루프로바꾸면다음과같다. 1 def permutepivot(xs,start,finish,pivotindex): 2 swap(xs,start,pivotindex) 3 pivot = xs[start] 4 i = start+1 5 j = finish 6 while i < j: 7 if xs[j] >= pivot: 8 j = j - 1 9 else: 10 swap(xs,i,j) 11 i = i + 1 12 if xs[i] > pivot: 13 i = i - 1 14 swap(xs,start,i) 15 return i 24
연습문제 집합집합을순수리스트로표현해보자. 그러면원소 x가집합 xs에속해있는지검사하는 member 함수는다음과같이작성할수있을것이다. def member(x,xs): if null(xs): return False else: return x == car(xs) or member(x,cdr(xs)) 집합에는같은원소가 2개이상있는것이의미가없으므로리스트에같은원소가반복되지않도록하면다루기간편해진다. 그러기위해서집합에원소를추가할때는다음과같이해당원소가이미집합에속해있는지검사해보고그렇지않은경우에만원소를추가해서중복을피할수있다. def add(x,xs): if member(x,xs): return xs else: return cons(x,xs) 집합에서특정원소를제거하고싶으면다음과같이원소를하나만찾아서제거하면충분하다. def remove(x,xs): if null(xs): return nil elif x == car(xs): return cdr(xs) else: return cons(car(xs),remove(x,cdr(xs))) 1. 위에서정의한 add 함수와 remove 함수를모두꼬리재귀함수로변환한뒤, while 루프형태로변환하시오. 2. 위에서정의한세함수를최대한이용하여아래의함수를작성하시오. (a) 두집합의합집합을구하는 union 함수 (b) 두집합의차집합을구하는 difference 함수 (c) 두집합의교집합을구하는 intersection 함수 25
묶기다음 zip 함수는두개의순수리스트를받아서그리스트의원소의쌍 ( 튜플 ) 의리스트를내주는함수이다. def zip(xs,ys): if null(xs) or null(ys): return nil else: return cons((car(xs),car(ys)),zip(cdr(xs),cdr(ys))) 다음은이함수의실행결과를보여준다. >>> zip([1,3],[2,4]) [(1, 2), (3, 4)] >>> zip([1,3,5,7],[2,4]) [(1, 2), (3, 4)] 1. 위의 zip 함수는두인수리스트의길이가다른경우긴리스트의남는부분은무시한다. 긴리스트의남는부분을아래예와같이버리지않는 sprice 함수를원초적재귀형식으로작성해보자. >>> sprice([1,3],[2,4]) [(1, 2), (3, 4)] >>> sprice([1,3,5,7],[2,4]) [(1, 2), (3, 4), (5, 5), (7, 7)] 2. zip 함수와 sprice 함수를모두꼬리재귀형식으로변환하시오. 3. zip 함수와 sprice 함수를 while 루프형식으로변환하시오. 26