문제 31, 셸 정렬, ShellSort, PC/UVa ID : 110407/10152

PC/UVa ID : 110407/10152

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• firefox4 beta11
  
• eclipse 3.6.1 + vrapper
  
• lua 5.1.4

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 31, 쉘 정렬, ShellSort, page 129)
  

참조 링크

• http://blog.naver.com/PostView.nhn?blogId=ccamchar&logNo=110079225241 : 피봇 랭크로 문제를 푼 방법
  
• http://www.algorithmist.com/index.php/UVa_10152 : 문제 원문
  

간략한 이야기/프로그램의 입출력

생략 - 난 한글판 책이 있어서 : )

맛보기 사진

맛보기 코드 - 루아로 작성 되었음
-- PC/UVa : 110407/10152 -- title : ShellSort -- http://ikpil.com -- 2011.02.25 ------------------------------------------------------------------------------- function optimum_order_sequence(tb_stack, tb_std_stack) local pivot_rank = 0 local sequence_rank = #tb_stack for i = #tb_stack, 1, -1 do local rank = tb_std_stack[tb_stack[i]] if nil == rank then return 0 end if sequence_rank == rank then sequence_rank = sequence_rank - 1 else pivot_rank = pivot_rank < rank and rank or pivot_rank end end return pivot_rank end function main() local case_count = io.read("*line") case_count = case_count + 0 for i = 1, case_count do local stack_size = io.read("*line") stack_size = stack_size + 0 local tb_stack = {} while #tb_stack < stack_size do local name = io.read("*line") if "" ~= name then tb_stack[#tb_stack+1] = name end end local i = 1 local tb_std_stack = {} while i <= stack_size do local name = io.read("*line") if "" ~= name then tb_std_stack[name] = i i = i + 1 end end local pivot_rank = optimum_order_sequence(tb_stack, tb_std_stack) for i = pivot_rank, 1, -1 do for k, v in pairs(tb_std_stack) do if v == i then print(k); break end end end print();io.flush() end end main() --[[ path = package.path package.path = "C:\\Users\\ikpil\\Desktop\\programming_challenges\\?.lua" package.path = package.path .. ";" .. path require "lunit" test_case = lunit:new() function test_case:test_case1() local tb_stack = {} tb_stack[#tb_stack+1] = "Yertle" tb_stack[#tb_stack+1] = "Duke of Earl" tb_stack[#tb_stack+1] = "Sir Lancelot" local tb_std_stack = {} tb_std_stack["Duke of Earl"] = 1 tb_std_stack["Yertle"] = 2 tb_std_stack["Sir Lancelot"] = 3 local pivot_rank = optimum_order_sequence(tb_stack, tb_std_stack) lunit:assert_true(pivot_rank == 1) end function test_case:test_case2() local tb_stack = {} tb_stack[#tb_stack+1] = "Yertle" tb_stack[#tb_stack+1] = "Duke of Earl" tb_stack[#tb_stack+1] = "Sir Lancelot" tb_stack[#tb_stack+1] = "Elizabeth Windsor" tb_stack[#tb_stack+1] = "Michael Eisner" tb_stack[#tb_stack+1] = "Richard M. Nixon" tb_stack[#tb_stack+1] = "Mr. Rogers" tb_stack[#tb_stack+1] = "Ford Perfect" tb_stack[#tb_stack+1] = "Mack" local tb_std_stack = {} tb_std_stack["Yertle"] = 1 tb_std_stack["Richard M. Nixon"] = 2 tb_std_stack["Sir Lancelot"] = 3 tb_std_stack["Duke of Earl"] = 4 tb_std_stack["Elizabeth Windsor"] = 5 tb_std_stack["Michael Eisner"] = 6 tb_std_stack["Mr. Rogers"] = 7 tb_std_stack["Ford Perfect"] = 8 tb_std_stack["Mack"] = 9 local pivot_rank = optimum_order_sequence(tb_stack, tb_std_stack) lunit:assert_true(pivot_rank == 3) end lunit:run() --]]

여담

• 정렬이 필요한 최적 순위(랭크)만 찾으면, 나머진 쉽다.

:wq!