Data Structure 3번째 HW(번역)

1. Now we have four sorting algorithm implementations, which were originated from the 2nd week homework.
이제 우리는 2번째 과제의 4개의 정렬 알고리즘을 갖고있다.
This is the time for asymptotically analyze each program. Of course, you have to analyze them under best, worst and average cases.
이번엔 점근적인(asymptotically) 분석을 해보자. 물논, 최악, 최적, 평균적인 사건에 대해 분석해야 된다.

2. Since we have the actual implementations, we can measure the execution time of them.
실제로 구현을 해놓았기 때문에 우리는 각 알고리즘의 실행시간을 측정할수 있다.

As we learned in the class, insert profiling (time measuring) code into your programs, and measure the time to sort randomly generated data sets (Yes, you have to make random student object generating code, too!).
우리가 수업에서 배운 시간 측정용 코드를 너의 프로그램에 넣어라, 그리고 임의로 생성된 데이터셋을 정렬하는 시간을 측정하여라(우리는 랜덤한 학생 오브젝트를 만드는것도 수업시간에 해 보았다.)

The number of students to be sorted must vary from 10 to 1,000,000 by log-scale increment (10, 100, 1,000, 10,000, … on and on).
학생의 숫자는 10에서 1,000,000 까지 큼직큼직하게 변해야 한다(10, 100, 1,000, 10,000, 이런식으로,,)

Draw graphs illustrating the tendency of the execution time changes depending on the changes of the data set size.
데이터 셋의 사이즈에 따라 실행 시간이 변하는 추세를 나타내는 그래프를 그려라.

The source codes, analysis results and graphs have to be prepared in a PDF file.
소스코드와, 분석결과, 그리고 그래프는 반드시 PDF파일로 보내세요.

Data Structure 3번째 HW

1. Now we have four sorting algorithm implementations, which were originated from the 2nd week homework. This is the time for asymptotically analyze each program. Of course, you have to analyze them under best, worst and average cases.

2. Since we have the actual implementations, we can measure the execution time of them. As we learned in the class, insert profiling (time measuring) code into your programs, and measure the time to sort randomly generated data sets (Yes, you have to make random student object generating code, too!). The number of students to be sorted must vary from 10 to 1,000,000 by log-scale increment (10, 100, 1,000, 10,000, … on and on). Draw graphs illustrating the tendency of the execution time changes depending on the changes of the data set size.

The source codes, analysis results and graphs have to be prepared in a PDF file.

Eclipse 단축키

파란 블로그의 라삐 님께서 정리하신 Eclipse단축키 입니다.
원본 주소 : http://blog.paran.com/rabbii/14608118
 

Kind	Category	Name (Command)	Key Sequence	When	Remark
Function Key	File	Rename	F2	In Windows
	Edit	Show Tooltip Description	F2	Editing in Structured Text Editors
	Navigate	Open Declaration	F3	In Windows	★
	Navigate	Open Type Hierarchy	F4	In Windows
	File	Refresh	F5	In Windows
	Run/Debug	Debug Last Launched	F11	In Windows
	Window	Activate Editor	F12	In Windows	★Editor창으로
↑ ←↓→ Arrow	Text Editing	Scroll Line Down	Ctrl+Down	Editing Text
	Text Editing	Scroll Line Up	Ctrl+Up	Editing Text
	Navigate	Go to Previous Member	Ctrl+Shift+Up	Editing Java Source
	Navigate	Go to Next Member	Ctrl+Shift+Down	Editing Java Source
	Navigate	Backward History	Alt+Left	In Windows	★History
	Navigate	Forward History	Alt+Right	In Windows
	Text Editing	Move Lines Up	Alt+Up	Editing Text
	Text Editing	Move Lines Down	Alt+Down	Editing Text
	Edit	Select Previous Element	Alt+Shift+Left	Editing in Structured Text Editors	Select…
	Edit	Select Next Element	Alt+Shift+Right	Editing in Structured Text Editors
	Edit	Select Enclosing Element	Alt+Shift+Up	Editing in Structured Text Editors
	Edit	Restore Last Selection	Alt+Shift+Down	Editing in Structured Text Editors
File Control	File	New	Ctrl+N	In Windows
	File	New menu	Alt+Shift+N	In Windows
	File	Close	Ctrl+F4	In Windows
	File	Close All	Ctrl+Shift+F4	In Windows
	File	Save	Ctrl+S	In Windows
	File	Save All	Ctrl+Shift+S	In Windows
	File	Print	Ctrl+P	In Windows
	File	Properties	Alt+Enter	In Windows
Goto & Move	Navigate	Go to Line	Ctrl+L	Editing Text
	Navigate	Go to Matching Bracket	Ctrl+Shift+P	Editing Java Source
	Navigate	(Go to) Last Edit Location	Ctrl+Q	In Windows
	Navigate	Previous	Ctrl+,	In Windows	★오류부분    바로가기
	Navigate	Next	Ctrl+.	In Windows
	Edit	Find Next	Ctrl+K	Editing Text
	Edit	Find Previous	Ctrl+Shift+K	Editing Text
Eclipse	Window	Maximize Active View or Editor	Ctrl+M	In Windows	화면크게보 기
	Window	Next Editor	Ctrl+F6	In Windows
	Window	Previous Editor	Ctrl+Shift+F6	In Windows
	Window	Quick Switch Editor	Ctrl+E	In Windows
	Window	Show Key Assist	Ctrl+Shift+L	In Dialogs and Windows	★키모음보 기
Comment	Source	Toggle Comment	Ctrl+/, Ctrl+7, Ctrl+Shift+C	Editing Java Source	한줄주석
	Edit	Add Block Comment	Ctrl+Shift+/	Editing in Structured Text Editors	선택영역주 석
	Edit	Remove Block Comment	Ctrl+Shift+\	Editing in Structured Text Editors
	Source	Add Javadoc Comment	Alt+Shift+J	In Windows	주석자동추가
Java Editor	Source	Organize Imports	Ctrl+Shift+O	In Windows	★import 자동
	Source	Add Import	Ctrl+Shift+M	Editing Java Source	import 커서
	Source	Indent Line	Ctrl+I	Editing Java Source
	Text Editing	Open Structure	Ctrl+F3	TapestryEditorScope
	Navigate	Quick Outline	Ctrl+O	Editing Java Source
	Navigate	Quick Hierarchy	Ctrl+T	Editing Java Source
	Edit	Quick Fix	Ctrl+1	Editing in Structured Text Editors	★빠른오류 수정
Eclipse Editor	Navigate	Open Resource	Ctrl+Shift+R	In Windows	★
	Edit	Find and Replace	Ctrl+F	In Windows
	Search	Open Search Dialog	Ctrl+H	In Windows	자바찾기
	Search	References in Workspace	Ctrl+Shift+G	In Windows	★
	Edit	Content Assist	Ctrl+Space	In Dialogs and Windows	★
	Edit	Format Document	Ctrl+Shift+F	Editing in Structured Text Editors	★형식맞추 기
	Text Editing	To Lower Case	Ctrl+Shift+Y	Editing Text	★대소문자변경
	Text Editing	To Upper Case	Ctrl+Shift+X	Editing Text
Etc	Edit	Run Query command	Ctrl+F9	Editing HQL
Editor Common Key	Edit	Select All	Ctrl+A	In Dialogs and Windows
	Edit	Copy	Ctrl+C, Ctrl+Insert	In Dialogs and Windows
	Edit	Cut	Ctrl+X, Shift+Delete	In Dialogs and Windows
	Edit	Paste	Ctrl+V, Shift+Insert	In Dialogs and Windows
	Edit	Redo	Ctrl+Y	In Windows
	Edit	Undo	Ctrl+Z	In Windows
	Edit	Delete	Delete	In Windows
	Text Editing	Line End	End	Editing Text
	Text Editing	Line Start	Home	Editing Text
	Text Editing	Text Start	Ctrl+Home	Editing Text
	Text Editing	Text End	Ctrl+End	Editing Text

Data Structure 2번째 HW(내맘대로 분석 #2)

===================================================================================================
RankSort 분석
===================================================================================================

일단 Rank Sort 알고리즘의 소스를 보자.

교재 80p를 보면 대략
[code java]
   public static void rank(Comparable [] a, int [] r)
   {
       if(r.length < a.length)
           throw new IllegalArgumentException
                    ("length of rank array cannot" +
                      "be less than the number of object");
      
       for(int i = 0; i < a.length; i++)
           r[i] = 0;
      
       for(int i = 1; i < a.length; i++)
           for(int j = 0; j < i; j++)
               if(a[j].compareTo(a[i]) <= 0) r[i]++;
               else r[j]++;
   }
   private static void rearrange(Comparable [] a, int [] r)
   {
       Comparable [] u = new Comparable[a.length];
       for(int i = 0; i < a.length; i++)
           u[r[i]] = a[i];

       for(int i = 0; i < a.length; i++)
           a[i] = u[i];
   }
[/code]
요렇게 되어있는것을 알 수 있다.

소트는 1개인데 왜 함수가 2개냐하면
rank소트는 rank함수로 각 인덱스에 점수를 주고,
rearrange함수로 각 점수에 맞는 위치로 재정렬을 하기 때문이다.

다음으로 rank함수를 보자

rank함수에서 중요하게 봐야될것은
11~14번째 라인에
[code java]
for(int i = 1; i < a.length; i++)
   for(int j = 0; j < i; j++)
       if(a[j].compareTo(a[i]) <= 0) r[i]++;
               else r[j]++;
[/code]
이부분이다.

이중 for문을 돌리면서 각 항을 서로 비교하여
더 큰 인자에 r을 증가시키고 있다.
이렇게 하면 전부 값이 매겨지도록 된다.
예를 들면

a[] = 1 3 2 5 4           의 배열의 경우
r[]  = 0 2 1 4 3           의 랭크가 매겨지고
이정보가 rearrange함수로 넘어가게 된다.

마지막으로 rearrange함수를 보자

rearrange함수는 rank가 매겨진 배열을 rank순으로 배열하는것 뿐이다.
우선 35라인에서 크기가 같은 Comparable 오브젝트배열인 u를 생성한다.
그리고 37라인에서
[code java]
u[r[i]] = a[i];
[/code]
이것의 의미는 u라는 새로운 배열에 a의 i번째 인자를 자신의 랭크에 맞는곳에 넣으라는 뜻이다.
근데 이것만 하면 a에 값이 들어가는게 아닌, u라는 배열에 정렬되고, a는 그대로다.
그래서 그 아래 for문에서 하는일이
[code java]
a[i]=u[i];
[/code]
로 다시 a에 넣는것이다.

Data Structure 2번째 HW(내맘대로 분석)

===================================================================================================
문제 분석
===================================================================================================

음,, 일단 랭크소트가 무엇인지를 파악해야겠군,,,
최형이라면 알지도 모르지만, 혼자 해보는것도 재미있을것 같다,,
문제는 시간.

시간 복잡도의 경우도 “counting the comparison operations(비교 연산자 갯수 세기)”는 쉬운데 “counting the steps with the s/e and frequency table(스텝을 세어서 빈도분석)”법은,,,,, 서의성 교수님 시간이었지만, 전날 무리하는 바람에 못들었다..

공부할게 많네,,,

공간 사용에 대해서는 보통 정렬의 경우에 공간은 거의 차지하지 않지, 임시공간 1개 정도? (merge의 경우를 제외하면,, 저번에 보니까 merge도 새로 안만들고 어떻게 하는 모양이던데,, 나는 같은 크기의 배열을 2개 만들고 옮겨 다녔으니,,,,)

 뭐,,, 오늘부터 해봐야지..

Data Structure 2번째 HW(번역)

===================================================================================================
번역
===================================================================================================

1. Our textbook introduces another sorting algorithm called rank sort at page 80.
1. 우리의 교제에서는 또다른 정령 알고리즘인 rank정렬을 80페이지에서 소개하고 있다.
Make a rank sort program that sorts students by their name and print their scores along side the names in the sorted order.
Rank정렬을 이용하여 학생들을 그들의 이름으로 정렬하고, 그들의 점수를 정렬된 이름옆에 표시하는 프로그램을 작성하여라.
Student names and scores must be included in a Student object.
학생의 이름과 점수는 반드시 Student 오브젝트에 포함되도록 만들어져야 한다.
The data are input through keyboard and the number of students is flexible (use a sentinel).
입력받는 데이터는 키보드로 입력받도록 하고, 학생의 수는 자유롭게 입력 받을수 있도록 한다(sentinel은 보초라는 뜻인데,,,,).
Analyze the best case, worst case and average case space and time complexity of the program you made.
당신이 만든 프로그램에서 시,공간 복잡도를 최적, 최악, 평균적인 경우을 놓고 분석하여라.
For time complexity, use both “counting the comparison operations” and “counting the steps with the s/e and frequency table” approaches.
시간 복잡도의 경우 “counting the comparison operations(비교 연산자 갯수 세기)”와 “counting the steps with the s/e and frequency table(스텝을 세어서 빈도분석)”법을 모두 사용하여라.

2. Modify the program for problem 1 by replacing the sorting algorithm with bubble sort, insert sort and selection sort.
2. 1에서 만들었던 프로그램을 Bubble정렬과 Insert정렬, Selection정렬로 고쳐보아라.
Also, you have to analyze the best, worst and average case space and time complexity of each version.
또한 최적, 최악, 평균적인 경우의 시, 공간 복잡도를 각각 분석하여라.

* The source codes, analysis results and screen shots of your programs in working have to be prepared in a PDF file.
* 소스코드와 분석결과, 그리고 프로그램 작동의 스샷은 PDF파일로 작성하여라.