{\rtf1\ansi\deff0\adeflang1025
{\fonttbl{\f0\froman\fprq2\fcharset0 Times New Roman{\*\falt Thorndale};}{\f1\froman\fprq2\fcharset0 Times New Roman{\*\falt Thorndale};}{\f2\fmodern\fprq1\fcharset0 Courier New;}{\f3\froman\fprq2\fcharset0 Times New Roman;}{\f4\fswiss\fprq2\fcharset0 Arial;}{\f5\fnil\fprq2\fcharset0 HG Mincho Light J;}{\f6\fnil\fprq2\fcharset0 Arial Unicode MS;}}
{\colortbl;\red0\green0\blue0;\red0\green0\blue128;\red128\green128\blue128;}
{\stylesheet{\s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\snext1 Default;}
{\s2\sa120\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext2 Text body;}
{\s3\sb240\sa120\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f4\fs28\lang1033\sbasedon1\snext2 Heading;}
{\s4\sb240\sa60\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f4\fs28\lang1033\b\sbasedon1\snext1{\*\soutlvl0} Heading 1;}
{\s5\sb240\sa60\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f4\fs24\lang1033\i\b\sbasedon1\snext1{\*\soutlvl1} Heading 2;}
{\s6\sb240\sa60\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f4\fs24\lang1033\sbasedon1\snext1{\*\soutlvl2} Heading 3;}
{\s7\sb240\sa60\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f4\fs24\lang1033\b\sbasedon1\snext1{\*\soutlvl3} Heading 4;}
{\s8\sb240\sa60\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f4\fs22\lang1033\sbasedon1\snext1{\*\soutlvl4} Heading 5;}
{\s9\sb240\sa60\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs22\lang1033\i\sbasedon1\snext1{\*\soutlvl5} Heading 6;}
{\s10\li360\ri0\fi-360\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext10 List;}
{\s11\li720\ri0\fi-360\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext11 List 2;}
{\s12\li1080\ri0\fi-360\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext12 List 3;}
{\s13\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext13 Header;}
{\s14\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext14 Footer;}
{\s15\sb240\sa60\cf1\qc{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f4\fs32\lang1033\b\sbasedon1\snext16 Title;}
{\s16\sa60\cf1\qc{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f4\fs24\lang1033\sbasedon1\snext2 Subtitle;}
{\s17\li360\ri0\fi1\sa120\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext17 WW-List Continue;}
{\s18\li360\ri0\fi1\sa120\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext18 WW-Body Text 2;}
{\s19\li360\ri0\fi1\sa120\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon18\snext19 WW-Body Text 3;}
{\s20\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext20 Normal;}
{\s21\li720\ri0\fi0\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon20\snext21 Body Text 2;}
{\*\cs23\cf1{\*\updnprop5801}\up10\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\fs24\lang1033\sbasedon26 Footnote Characters;}
{\*\cs24\cf1\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\fs24\lang1033 Page Number;}
{\*\cs25\cf2\ul\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\fs24\lang1033 Internet Link;}
{\*\cs26\cf1\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\fs24\lang1033 WW-Absatz-Standardschriftart;}
{\*\cs27\cf1\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\lang1033 WW-Absatz-Standardschriftart1;}
{\*\cs28\cf1{\*\updnprop5801}\up10\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\lang1033\sbasedon27 WW-Footnote Symbol;}
{\*\cs29\cf1\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\lang1033 WW-Default Paragraph Font;}
{\*\cs30\cf1\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\lang1033 WW-Page Number;}
{\*\cs31\cf1\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\lang1033\sbasedon29 WW-Page Number1;}
{\*\cs32\cf1\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f0\lang1033\b\sbasedon29 WW-Strong;}
}
{\info{\title 132hw07 - s03}{\author Sharon Tuttle}{\creatim\yr2001\mo1\dy23\hr10\min30}{\operator Sharon Tuttle}{\revtim\yr2003\mo3\dy27\hr10\min59}{\printim\yr2003\mo3\dy27\hr10\min59}{\comment StarWriter}{\vern6410}}\deftab720
{\*\pgdsctbl
{\pgdsc0\pgdscuse195\pgwsxn12240\pghsxn15840\marglsxn1440\margrsxn1440\margtsxn720\margbsxn720\headery0{\*\headeryb283\headerxl0\headerxr0\headeryh0}{\header \pard\plain \s13\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\ltrch\loch\fs12 {\ltrch\loch\f3 CIS 132 - HW #7\tab \tab p. {\field{\*\fldinst \\page}{\fldrslt 6}}}
\par {\ltrch\loch\f3 Spring 2003}
\par }
\pgdscnxt0 Default;}}
\paperh15840\paperw12240\margl1440\margr1440\margt720\margb720\sectd\sbknone\pgwsxn12240\pghsxn15840\marglsxn1440\margrsxn1440\margtsxn1303\margbsxn720\headery720{\header \pard\plain \s13\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\ltrch\loch\fs12 {\ltrch\loch\f3 CIS 132 - HW #7\tab \tab p. {\field{\*\fldinst \\page}{\fldrslt 6}}}
\par {\ltrch\loch\f3 Spring 2003}
\par }
\ftnbj\ftnstart1\ftnrstcont\ftnnar\aenddoc\aftnrstcont\aftnstart1\aftnnrlc
\pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\qc{\*\tlswg8236}\tx6300\ltrch\loch\fs24\b {\ltrch\loch\f3 HUMBOLDT STATE UNIVERSITY}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\qc\ltrch\loch\fs24\b {\ltrch\loch\f3 CIS 132 - Introduction to Computer Science II - Spring 2003}
\par {\ltrch\loch\f3 Homework #7 - due Friday, April 5th,  4:30 pm}
\par {\ltrch\loch\f3 Sort Detective}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033{\*\tlswg8236}\tx1260\ltrch\loch\fs24\b 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\fs24 {\ltrch\loch\f3 AND NOW, FOR SOMETHING COMPLETELY DIFFERENT...}
\par {\ltrch\loch\f3 MODIFIED from the assignment by:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\qc\ltrch\loch\fs24\b {\ltrch\loch\f3 David B. Levine, Computer Science Department, St. Bonaventure University}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\fs20 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24\b{\ltrch\loch\f3{\b0 Since there are only write-ups involved in this lab, you should e-mail them to me by the time and date specified above, in e-mail(s) with the Subject: }132hw07{\b0 .}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24 
\par {\ltrch\loch\f3 This assignment has the purpose of getting you to (hopefully) really think about many of the different sorts that we discussed in Ch. 5 (all except for poor radix sort, which is not included).}
\par 
\par {\ltrch\loch\f3 The files for a Java program {\b SortDetective} are in a file on axe {\b ~st10/132hw07_public}. You should be able to copy them as follows:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li705\ri0\fi-360\ltrch\loch\f3\fs24 {\ltrch\loch\f3 *\tab telnet to axe, and log onto your axe account}
\par {\ltrch\loch\f3 *\tab {\b mkdir 132hw07}}
\par {\ltrch\loch\f3 \tab (or whatever directory you want to put these files into...)}
\par {\ltrch\loch\f3 *\tab {\b cd 132hw07}}
\par {\ltrch\loch\f3 \tab (or whatever new directory you just created)}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li705\ri0\fi-360{\ltrch\loch\f3{\b0\ulnone\i0\fs24\f3 *\tab {\b cp ~st10/132hw07_public/*   .}}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li705\ri0\fi-360\ltrch\loch\f3\fs24\b {\ltrch\loch\f3 \tab {\b0 (see that lone period? It is important! This copies everything in ~st10/132hw07_public into your current working directory)}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li705\ri0\fi-360\ltrch\loch\f3\fs24 {\ltrch\loch\f3 *\tab (you can log off of axe now and close your telnet window, if you'd like...)}
\par {\ltrch\loch\f3 *\tab now you can use {\b WS-FTP} to connect to axe, go to your directory {\b 132hw07} (or whatever you called it), and copy over all of those files to a folder on the machine where you hope to use BlueJ.}
\par {\ltrch\loch\f3{\b0 *\tab And, since this includes BlueJ project info, you should now be able to open that folder you just WS-FTP'd into as a BlueJ project.}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24 
\par {\ltrch\loch\f3 You should see two boxes when you open BlueJ, labeled {\b SortDetective}{\b0  and }{\b SortingExperiment}{\b0 . You run this program by right-clicking on the }{\b SortDetective}{\b0  box, selecting }{\b void main(args)}{\b0  from the options that appear, and clicking OK in the window that appears a
fter that. Look for a }{\b SortDetective}{\b0  window, it *might* appear under other currently open windows.}}
\par 
\par {\ltrch\loch\f3 This program lets you practice running implementations of {\b several different} sort implementations, with lists of sizes you choose and various features. It then shows you the {\b number of comparison} and {\b number of movements} that that run of that sort took.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24 {\ltrch\loch\f3 The primary objective of this assignment is for you to apply your theoretical knowledge of sorting algorithms to solve a problem of poor user interface design.  More specifically, SortDetective is designed to measure comparisons, data movements, and execut
ion time for the several sorting algorithms discussed in class.  Unfortunately, the designer of the program did not label the buttons properly.  You must apply your understanding of the general properties of the algorithms to determine the proper labeling 
of the buttons.}
\par {\ltrch\loch\f3 The secondary objective of this lab is for you to gain experience writing a concise, but complete analysis of a system.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24 {\ltrch\loch\f3 The sorts have dummy names; they are actually implementations of the discussed sorts  {\b bubblesort}, {\b selection sort}, {\b insertion sort}, {\b mergesort}, and {\b quicksort}. (Poor {\b radix sort} is not included, oh well...)}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24{\ltrch\loch\f3{\b CONSIDER}: you know the {\b basic run-time }complexity of these; you know a bit about how they work.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20\b 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24\b {\ltrch\loch\f3 FIRST{\b0 , make a plan --- what kinds of tests could you run to }GUESS{\b0  which sort is which? }Write{\b0  this plan/strategy out, and turn it in as part of your assignment.}}
\par {\ltrch\loch\f3 THEN{\b0 , }run{\b0  tests, and }write down{\b0  the results. (Yes, we are practicing a little scientific experimentation here, too.) }}
\par {\ltrch\loch\f3 FINALLY{\b0 , you will take your notes from those experiments, and }write up{\b0  your }guesses{\b0  as to which sort is which. You will first summarize your guesses, and }then {\b0 justify them; the format should be like that given on the example on the next page. }{\ul (Although you
 may experiment, speculate, and brainstorm with other class members, THIS write-up is INDIVIDUAL work)}}
\par 
\par {\ltrch\loch\f3 CONSIDER:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24 {\ltrch\loch\f3 As you know from class, if you double the size of the data set that you give to a quadratic algorithm, it will do four times the work; by contrast, an O(NlogN) algorithm will do a bit more than twice as much; and, a linear algorithm will do only twice as m
uch work.  As you also know, the characteristics of the input data set can affect the expected performance of many of our sorting algorithms.  Before you begin the testing, you can see how it would be helpful for you to review the {\b expected} performance of t
he algorithms on various data sets.}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24\b {\ltrch\loch\f3 Grading notes:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24 {\ltrch\loch\f3 There is no coding in this assignment.  Thus, you should expect that a significant portion of the grade for this assignment will be determined by the quality of the writing of the report.  This includes the completeness of the report, the clarity of the wr
iting, and general presentation.  You could get a poor grade for poor writing, even if you "get" all of the right matches. }
\par {\ltrch\loch\f3 Some of the sorts may be difficult to distinguish.  A carefully outlined experiment may compensate for an error in these cases if the writing makes it clear that your conclusions/guesses are substantiated by the data.}
\par {\ltrch\loch\f3 Finally, remember that your report needn't detail every experiment you ran.  Rather, it should give sufficient information to justify your conclusions.  It is possible to write a very short report that is completely correct if your experiments are well-cho
sen.  After you learn the matching, you might consider whether there was a shorter way to arrive at your conclusion!}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs24{\ltrch\loch\f3{\b To Hand In}:  your before-experimenting plan of attack  and your final report.}
\par 
\par {\ltrch\loch\f3 (what follows this is an example of a final report, and the implementations of the sorts used within the SortDetective program; no example plan of attack is included...)}
\par \page\pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20 {\ltrch\loch\f3 Searching Lab Report}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20 {\ltrch\loch\f3 A. Beauregard Clump}
\par {\ltrch\loch\f3 4-5-03}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\qc\ltrch\loch\f3\fs20 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ul\ltrch\loch\f3\fs20\b {\ltrch\loch\f3 General Results}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\qc\ltrch\loch\f3\fs20 
\par {\ltrch\loch\f3 Button Name\tab Searching Algorithm}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20\b {\ltrch\loch\f3 ----------------- \tab ---------------------------}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20 {\ltrch\loch\f3 Sigma\tab \tab Binary Search}
\par {\ltrch\loch\f3 Tau\tab \tab \tab Sequential Search}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\qc\ltrch\loch\f3\fs20\b 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ul\ltrch\loch\f3\fs20\b {\ltrch\loch\f3 Rationale}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\qc\ltrch\loch\f3\fs20 {\ltrch\loch\f3                                               }
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\ltrch\loch\f3\fs20 {\ltrch\loch\f3 I chose to search data sets of size 500, 1000, and 2000, looking for the last data item each time. Button Tau took 500, 1000, and 2000 comparisons each time, doubling the number of comparisons each time the size of the searchable list doubled. Button Sigma
 took many fewer comparisons and this number increased by only one each time the size of the searchable list was doubled.}
\par 
\par {\ltrch\loch\f3 Since a sequential list is linear, I conclude that TAU is SEQUENTIAL SEARCH.}
\par 
\par {\ltrch\loch\f3 Then by process of elimination, I conclude that SIGMA is BINARY SEARCH.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360\ltrch\loch\f3\fs20 {\ltrch\loch\f3 -----------------------------------------------------------------------------------------------------------------------------------------}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20 {\ltrch\loch\f2 /* Here are the implementations of the sorts as used in SortDetective. */}
\par {\ltrch\loch\f2 /* (note that they have had code added to count comparisons and data   */}
\par {\ltrch\loch\f2 /* movements)                                                          */}
\par 
\par {\ltrch\loch\f2 /* Code and Comments by David B. Levine, Computer Science Department,  */}
\par {\ltrch\loch\f2 /* St. Bonaventure University                                          */}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20\b {\ltrch\loch\f2 /* BubbleSort */}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20 
\par {\ltrch\loch\f2 // Code basically taken from Sedgewick, "Algorithms"}
\par 
\par {\ltrch\loch\f2 protected void bubbleSort(int list[])}
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab int temp;}
\par {\ltrch\loch\f2 \tab      \tab do \{}
\par {\ltrch\loch\f2 \tab      \tab \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab \tab temp = list[0];}
\par {\ltrch\loch\f2 \tab      \tab \tab for (int j=1; j<list.length; j++)}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab comparisons++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab if (list[j-1]>list[j])}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \tab movements += 3;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \tab temp = list[j];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \tab list[j] = list[j-1];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \tab list[j-1] = temp;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab comparisons++;}
\par {\ltrch\loch\f2 \tab      \tab \} while (temp != list[0]);}
\par {\ltrch\loch\f2 \}}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20\b 
\par \page\pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20\b {\ltrch\loch\f2 /* Selection Sort */}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20 
\par {\ltrch\loch\f2 // Code from memory}
\par 
\par {\ltrch\loch\f2 protected void selectionSort(int list[])}
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab for (int j=list.length-1; j>0; j--)}
\par {\ltrch\loch\f2 \tab      \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab int maxpos = 0;}
\par {\ltrch\loch\f2 \tab      \tab \tab for (int k=1; k<=j; k++)}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab comparisons++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab if (list[k]>list[maxpos])}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \tab maxpos = k;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab if (j != maxpos)\tab // Only move if we must}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab movements += 3;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab int temp = list[j];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab list[j] = list[maxpos];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab list[maxpos] = temp;}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \}}
\par {\ltrch\loch\f2 \}}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20\b {\ltrch\loch\f2 /* Insertion Sort */}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20 
\par {\ltrch\loch\f2 // Code basically taken from Sedgewick, "Algorithms"}
\par 
\par {\ltrch\loch\f2 protected void insertionSort(int list[])}
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab for (int j=1; j<list.length; j++)}
\par {\ltrch\loch\f2 \tab      \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab \tab int temp = list[j];}
\par {\ltrch\loch\f2 \tab      \tab \tab int k = j;}
\par {\ltrch\loch\f2 \tab      \tab \tab while( k > 0 && list[k-1]>temp )}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab comparisons++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab list[k] = list[k-1];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab k--;}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab if (k > 0)}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab comparisons++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab \tab list[k] = temp;}
\par {\ltrch\loch\f2 \tab      \tab \}}
\par {\ltrch\loch\f2 \}}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20\b 
\par \page\pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20\b {\ltrch\loch\f2 /* MergeSort */}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20\b 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20 {\ltrch\loch\f2 // Code basically taken from Horowitz and Sahni, "Fundamentals of Computer }
\par {\ltrch\loch\f2 // Algorithms"}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs18 {\ltrch\loch\f2 protected void mergeSort(int list[])}
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab msort(list, 0, list.length-1);}
\par {\ltrch\loch\f2 \}}
\par {\ltrch\loch\f2 \tab      }
\par {\ltrch\loch\f2 private void msort(int list[], int low, int high) }
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab if (low<high)}
\par {\ltrch\loch\f2 \tab      \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab int mid = (low+high)/2;}
\par {\ltrch\loch\f2 \tab      \tab \tab msort(list, low, mid);}
\par {\ltrch\loch\f2 \tab      \tab \tab msort(list, mid+1, high);}
\par {\ltrch\loch\f2 \tab      \tab \tab merge(list, low, mid, high);}
\par {\ltrch\loch\f2 \tab      \tab \}}
\par {\ltrch\loch\f2 \}}
\par {\ltrch\loch\f2 \tab      }
\par {\ltrch\loch\f2 private void merge(int list[], int low, int mid, int high)}
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab int h = low;}
\par {\ltrch\loch\f2 \tab      \tab int i = 0;}
\par {\ltrch\loch\f2 \tab      \tab int j = mid+1;}
\par {\ltrch\loch\f2 \tab      \tab int otherList[] = new int[high-low+1];}
\par {\ltrch\loch\f2 \tab      \tab }
\par {\ltrch\loch\f2 \tab      \tab while ((h <= mid) && (j <= high))}
\par {\ltrch\loch\f2 \tab      \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab comparisons++;}
\par {\ltrch\loch\f2 \tab      \tab \tab if (list[h] <= list[j])}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab otherList[i] = list[h];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab h++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab else}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab otherList[i] = list[j];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab j++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab i++;}
\par {\ltrch\loch\f2 \tab      \tab \}}
\par {\ltrch\loch\f2 \tab      \tab if (h>mid)}
\par {\ltrch\loch\f2 \tab      \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab for (int k=j; k<=high; k++)}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab \tab      \tab \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab otherList[i] = list[k];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab i++;}
\par {\ltrch\loch\f2      \tab \tab \tab \}}
\par {\ltrch\loch\f2      \tab \tab \}}
\par {\ltrch\loch\f2      \tab \tab else}
\par {\ltrch\loch\f2      \tab \tab \{}
\par {\ltrch\loch\f2  \tab      \tab \tab for (int k=h; k<=mid; k++)}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab \tab      \tab \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab otherList[i] = list[k];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab i++;}
\par {\ltrch\loch\f2      \tab \tab \tab \}}
\par {\ltrch\loch\f2      \tab \tab \}}
\par {\ltrch\loch\f2    }
\par {\ltrch\loch\f2      \tab \tab for (int m=0; m<otherList.length; m++)}
\par {\ltrch\loch\f2      \tab \tab \{}
\par {\ltrch\loch\f2      \tab \tab \tab movements++;}
\par {\ltrch\loch\f2      \tab \tab \tab list[low+m] = otherList[m];}
\par {\ltrch\loch\f2      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \}}
\par {\ltrch\loch\f2 \}}
\par \page\pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20\b {\ltrch\loch\f2 /* QuickSort */}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs20 
\par {\ltrch\loch\f2 // Code basically taken from Cormen, Leiserson, and Rivest, "Introduction to }
\par {\ltrch\loch\f2 // Algorithms"}
\par 
\par {\ltrch\loch\f2 protected void quickSort(int list[])}
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab qsort(list, 0, list.length-1);}
\par {\ltrch\loch\f2 \}}
\par {\ltrch\loch\f2 \tab      }
\par {\ltrch\loch\f2 private void qsort(int list[], int low, int high) }
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab if (low<high)}
\par {\ltrch\loch\f2 \tab      \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab int pivot = partition(list, low, high);}
\par {\ltrch\loch\f2 \tab      \tab \tab qsort(list, low, pivot);}
\par {\ltrch\loch\f2 \tab      \tab \tab qsort(list, pivot+1, high);}
\par {\ltrch\loch\f2 \tab      \tab \}}
\par {\ltrch\loch\f2 \}}
\par {\ltrch\loch\f2 \tab      }
\par {\ltrch\loch\f2 private int partition(int list[], int low, int high)}
\par {\ltrch\loch\f2 \{}
\par {\ltrch\loch\f2 \tab      \tab movements++;}
\par {\ltrch\loch\f2 \tab      \tab int temp = list[low];}
\par {\ltrch\loch\f2 \tab      \tab int i = low-1;}
\par {\ltrch\loch\f2 \tab      \tab int j = high+1;}
\par {\ltrch\loch\f2 \tab      \tab while(true)}
\par {\ltrch\loch\f2 \tab      \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab do \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab j--;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab comparisons++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \} while (list[j] > temp);}
\par {\ltrch\loch\f2 \tab      \tab \tab do \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab i++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab comparisons++;}
\par {\ltrch\loch\f2 \tab      \tab \tab \} while (list[i] < temp);}
\par {\ltrch\loch\f2 \tab      \tab \tab if (i < j)}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab movements += 3;}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab int swapTemp = list[i];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab list[i] = list[j];}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab list[j] = swapTemp;}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \tab else}
\par {\ltrch\loch\f2 \tab      \tab \tab \{}
\par {\ltrch\loch\f2 \tab      \tab \tab \tab return j;}
\par {\ltrch\loch\f2 \tab      \tab \tab \}}
\par {\ltrch\loch\f2 \tab      \tab \}}
\par {\ltrch\loch\f2 \}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af6\afs24\lang255\ltrch\dbch\af5\afs24\langfe255\loch\f3\fs20\lang1033\li420\ri0\fi-420\ltrch\loch\f2\fs24 
\par }