Transcript look
Computing Concepts Searching and Sorting What we have done so far in data structures • data structure as a way of organising the storage of data • brief look at: – – – – records arrays sequences (lists, queues, stacks) trees What we have done so far in data structures • Done more on – records – arrays Example • What are the contents of the element in the array PlayOffTeams which has index 3 ? • What is the value of PlayOffTeams[2] ? Example • Describe completely the structure of the array PlayOffTeams. Example • The index for the array PlayOffTeams lies in the range 1..4 • The elements are of type Name Example • Write a fragment of Pascal that would display the third name in the array. WriteLn(PlayOffTeams[3]); Example • Write a fragment of Pascal that would display all the names in the array. Example FOR I := 1 TO 4 DO BEGIN WriteLn(PlayOffTeams[I]); END What we shall do today • Look at arrays in Pascal (not on assessment) • Search arrays • Sort (re-order) arrays Pascal Array • X[1] gets 2 • X[2] gets 4 • X[3] gets 6 etc Prog1_BigArray Searching an array • Example: – How does hole in the wall find your account from your credit card details ? • Need to search through the array of bank records Different kinds of search available • Linear Search • Binary search Linear Search • Searching for a birthday day of the month • Searching for bank records – 1,000 bank records – Fastest find in • 1 comparison – Slowest find in • 1,000 comparisons – Average find in • 500 comparisons Binary Search • How can we speed up the process ? • Binary search for a number in range 1 to 1000 • Searching for a birthday day of the month Sorting • We need to sort to – be able to use the fast binary search – produce reports in required order Sorting • Many different ways of carrying out a sort on an array. • We shall examine EXCHANGE SORT (Also known as the BUBBLE SORT) • We shall look at others Exchange Sort • • • • Simple Slow Demo with heights Demo with birthday day of the month Pascal Exchange Sort • Prog3_LittleSort – 10,000 elements – 20,000 elements – 40,000 elements Sorting Demos • http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html •http://www.cs.hope.edu/~alganim/animator/Animator.html