CSCI103_06a_ArraysDataStructures(print)4

1 CSCI103 Spring 2011 Algorithms and Problem Solving (S6a) Data structures: Arrays: Sorting and searching Data Structures „ A data structure is an organized collection of data, and its storage allocation in a computer.p „ A data structure uses a collection of related variables that can be accessed individually or as a whole. Algorithm: findLargest Remember this from modularisation? Algorithm: showLargest Purpose: This algorithm takes a list of positive integers, finds and prints the largest value Input: list of positive integers Output: the largest integer BEGIN showLargest GET list of integers CALL findLargest WITH list of integers RETURNING largest WRITE largest END showLargest Purpose: this algorithm finds the largest value in a list of positive integers Pre: list of positive integers Return: the largest integer BEGIN findLargest SET largest to 0 WHILE more values in the list READ value IF value GREATER THAN largest THEN SET largest to value ENDIF ENDWHILE RETURN largest END findLargest How do we handle the “list of integers”? We use … Arrays „ An array is a fixed-size, sequenced collection of elements of the same data type. element 0 l t 1 • The length or size of an array is the number of elements in the array. How many Elements in this array? There are 7 From 0 to ‘n’ = ‘n’ + 1 What is the size of this array? 7 element 2 element 1 element 6 There could be an integer in each box. y • Each element in the array is identified by an integer called the index, which indicates the position of the element in the array. • For a zero-based array, index starts from 0 and goes up to the length minus 1. • The upper bound of an array is the index of the last element. What is the upper bound of this array?6 2 „ We use the index to access, or refer to, elements of an array. „ Here goes a seven element array with the identifier numbers. numbers[0] numbers[1] numbers[6] numbers Array numbers[7]; 10 17 09 40 65 10 61 89 61 Example: An array, called ages, of nine integers. ages [0] [1] [2] [3] [4] [5] [6] [7] [8] 1st element ages[0] = ? ages[5] = ? ages[7] = ? ages[2] = ? ages[9] =? ages[11]=? ages[0] = 10 ages[5] = 10 ages[7] = 89 ages[2] = 9 ages[9] =illegal ages[11]=illegal showLargest with an array Algorithm: showLargest Purpose: This algorithm takes a list of 100 positive integers, finds and prints the largest value Input: list of positive integers Output: the largest integer BEGIN showLargest GET list of integers CALL findLargest WITH list of integers RETURNING largest WRITE largest END showLargest Algorithm: showLargest Purpose: this algorithm takes a list of 100 positive integers, finds and prints the largest value Input: list of 100 positive integers Output: the largest integer BEGIN showLargest GET array of 100 integers CALL findLargest WITH array RETURNING largest WRITE largest END showLargest We might also use … SET largest to findLargest(list, 100) Algorithm: swap Purpose: this algorithm swaps 2 values Input: value1, value2 Output: value1, value2 Pre: 2 values of the same type Post: the values have been swapped Return: Nil Algorithm: swap Purpose: To swap the j’th element with k’th element in an array Input: array, j & k Pre: j & k must be valid index of the array Post: array with swapped elements Return: nil Example: Swap two array elements BEGIN swap SET temp to value1 SET value1 to value2 SET value2 to temp END swap BEGIN swap (array, j,k) SET temp to array[j] SET array[j] to array[k] SET array[k] to temp END swap (array, j,k) 3 A sneaky swap CALL echo WITH A, B RETURNING B,A SET B,A to echo(A,B) Algorithm: echo Input: first, second BEGIN echo RETURN first, second END echo Sometimes all you need is the function header. ☺ The main operations on arrays „ Defining: – DEFINE nameOfArray[0,…,N-1] (N is the array size.) – For example: DEFINE marks[0…5] DEFINE days[0...6] „ Accessing:„ Accessing: – Index ranges from 0 to N-1 for an array of size N. – For example: GET days[2] SET marks[0] to 5 „ Processing: – Initialization (or input). – Output. – Summing the elements. – . . . Initialising an array Algorithm: initArray Purpose: Set initial values of elements of an array to the days of month Input: array A, size of array (N) Output: Array A Post: A has been initialised Return: nil BEGIN initArray (A, N) SET index to 0 WHILE (index < N) SET A[index] to the days of each month INCREMENT index by 1 ENDWHILE END init1DArray showLargest with an array Algorithm: showLargest Purpose: This algorithm takes a list of positive integers, finds and prints the largest value Input: list of positive integers Output: the largest integer BEGIN showLargest GET list of integers CALL findLargest WITH list of integers RETURNING largest WRITE largest END showLargestg Algorithm: showLargest Purpose: Tthis algorithm finds and prints the largest value in an array of 100 positive integers Input: 100 positive integers Output: the largest integer BEGIN showLargest DEFINE list[0…99] FOR index from 0 to 99 GET list[index] ENDFOR SET largest to findLargest(list, 100) WRITE largest END showLargest 4 Finding the largest array element Algorithm: findLargest Purpose: This algorithm will find the largest value in an array Input: array called set, size of the array called size Output: nil Pre: valid set, size Post: nil Return: largest value in the array BEGIN FindLargest (set, size) SET largest to set[0] FOR each element in the array set start from the second element (index=1) IF the current element set[index] is larger than largest THEN SET largest to the current element ENDIF ENDFOR RETURN largest END FindLargest (set, size) Finding the smallest array element Algorithm: findSmallest Purpose: This algorithm will find the smallest value in an array Input: array called set, size of the array called size Output: nil Pre: valid set, size Post: nil Return: smallest value in the array BEGIN FindSmallest (set, size) SET smallest to set[0] FOR each element in the array set start from the second element (index=1) IF the current element set[index] is smaller than smallest THEN SET smallest to the current element ENDIF ENDFOR RETURN smallest END FindSmallest (set, size) Elementary sorting algorithms „ We are going to look at three sorting algorithms. – Selection Sort. – Insertion sort. – Bubble sort . „ All these algorithms divide the list of values they are sorting into two parts: sorted and unsorted.so g o o pa s so ed a d u so ed – This is relevant to arrays because we need to represent the list of values somehow. „ These algorithms differ in how they move elements from the unsorted part to the sorted part. 2,5,7,32,8,50,11 Sorted Unsorted Selection Sort „ This approach to sorting relies on finding the smallest number in the unsorted part of a list and swapping it with the first number in the unsorted partin the unsorted part. – The old first position in the unsorted part becomes the new end of the sorted part. – The sorted part gets bigger by one at each iteration. 5 Selection Sort – Example „ 7 3 5 9 2 1 8 – find smallest „ 1 3 5 9 2 7 8 – swap, find smallest „ 1 2 5 9 3 7 8 – swap, find smallest „ 1 2 3 9 5 7 8 – swap, find smallest „ 1 2 3 5 9 7 8 – swap, find smallest „ 1 2 3 5 7 9 8 – swap, find smallest „ 1 2 3 5 7 8 9 – swap, DONE! „ 1 2 3 5 7 8 9 Algorithm: findIndexOfSmallest Purpose: finds the index of smallest number from some position to the last element in an array Input: array, its size N and the starting index Pre: nil Return: the index to the array where the smallest element is located Post: nil BEGIN findIndexOfSmallest WITH data, N, startingIndex RETURNING minIndex SET minIndex to startingIndex SET index to (startingIndex +1) WHILE (index <= N-1) IF (data[index] < data[minIndex]) THEN SET minIndex to index ENDIF increase index by 1 ENDWHILE RETURN minIndex END findIndexOfSmallest Algorithm:selectionSort Purpose: This algorithm sorts N numbers in ascending order Input: N numbers in an array and N Pre: nil Return: The N numbers in an ascending order Post: the numbers in the array are reorganized What does wallIndex point to? First element of unsorted list? Last element of sorted list? BEGIN selectionSort(array,N) INITIALISE wallIndex to 0 WHILE (wallIndex <= N-2) CALL findIndexOfSmallest WITH array wallIndex RETURNING minIndex CALL Swap WITH array minIndex wallIndex INCREMENT wallIndex by 1 ENDWHILE RETURN array END selectionSort When does the algorithm stop? Selection Sort: Cost summary… „ Space: No extra array is needed. – Everything is being stored in the single data array. „ Number of comparisons: N-1 + (N-2) + (N-3) + ……+1 = (N-1)*(N-1+1)/2 = N(N-1)/2 „ Number of swaps:p Up to N-1. „ Worst case: If the input is 3, 7, 9, 11, 32, 50, 1 21 comparisons and 6 swaps – We swap the current unsorted smallest to the end each time. „ Best case: If the input is 1, 3, 7, 9, 11, 32, 50 21 comparisons but no swaps 6 Insertion Sort „ In this approach we again have a single data array split into sorted and unsorted sections. – We start with the first element in the sorted section. Th “ t d ti ” h li htl diff t– The “sorted section” has a slightly different meaning though, as we shall see later. „ In each iteration the first element of the unsorted is moved down into the correct place in the sorted section. „ The sorted part gets bigger by one at each iteration. Insertion Sort – Example „ 7 3 5 9 2 1 8 – sift the 2nd element down „ 3 7 5 9 2 1 8 – sift the 3rd element down „ 3 5 7 9 2 1 8 – sift the 4th element down „ 3 5 7 9 2 1 8 – sift the 5th element down „ 2 3 5 7 9 1 8 – sift the 6th element down „ 1 2 3 5 7 9 8 – sift the 7th element down „ 1 2 3 5 7 8 9 – DONE ` The “sorted section” isn’t actually “finally sorted”, unlike in selection sort, but sorted with respect to the elements so far. Algorithm:insertionSort Purpose: This algorithm sorts N numbers in ascending order Input: N numbers in an array and N Pre: nil Return: The N numbers in an ascending order Post: The numbers in the array are reorganized BEGIN insertionSort (array, N) INITIALISE wallIndex to 1 WHILE (wallIndex <= N-1) SET temp to array[wallIndex] SET index to wallIndex WHILE (index>0 AND array[index-1]>temp) SET array[index] to array[index-1]; DECREMENT index ENDWHILE SET array[index] to temp; INCREMENT wallIndex ENDWHILE RETURN array END insertionSort „ Consider the following example of how the sift down operation works: – 3 5 7 9 2 1 8 – copy the 5th element to temp – 3 5 7 9 9 1 8 – copy the 4th element up – 3 5 7 7 9 1 8 – copy the 3rd element up 3 5 5 7 9 1 8 copy the 2nd element up– 3 5 5 7 9 1 8 – copy the 2nd element up – 3 3 5 7 9 1 8 – copy the 1st element up – 2 3 5 7 9 1 8 – paste the new element in place. „ We keep on copying until we reach the final position for the element first copied. 7 Insertion Sort: Cost summary… „ Space: No extra array is needed. – Again everything is being stored in the single data array. – Operations: • Worst case N(N 1)/2 comparisons & “moves”• Worst case N(N-1)/2 comparisons & moves . • Best case N-1 comparisons, no “moves”. „ Worst case: if input is 50, 32, 11, 9, 7, 3, 1 21 comparisons and 21 moves. „ Best case: if input is 1, 3, 7, 9, 11, 32, 50 6 comparisons but no moves. Bubble Sort „ This approach relies on making the sorted part of the array one element larger by shuffling (actually swapping) the next l t l t d i t th tlargest element down into the correct place. „ The sorted part gets bigger by one at each iteration. Bubble Sort – Example „ 7 3 5 9 2 1 8 – compare elements 5 and 6 „ 7 3 5 9 2 1 8 – compare elements 4 and 5 – swap „ 7 3 5 9 1 2 8 – compare elements 3 and 4 - swap „ 7 3 5 1 9 2 8 – compare elements 2 and 3 – swap Note that we refer to elements by index! „ 7 3 1 5 9 2 8 – compare elements 1 and 2 – swap „ 7 1 3 5 9 2 8 – compare elements 0 and 1 – swap „ 1 7 3 5 9 2 8 – back to the start „ 1 7 3 5 9 2 8 – compare elements 5 and 6 „ 1 7 3 5 9 2 8 – compare elements 4 and 5 – swap „ 1 7 3 5 2 9 8 – compare elements 3 and 4 – swap „ 1 7 3 2 5 9 8 – compare elements 2 and 3 – swap… „ 1 7 3 2 5 9 8 – compare elements 2 and 3 – swap „ 1 7 2 3 5 9 8 – compare elements 1 and 2 – swap „ 1 2 7 3 5 9 8 – back to the start „ 1 2 7 3 5 9 8 – compare elements 5 and 6 - swap „ 1 2 7 3 5 8 9 – compare elements 4 and 5 „ 1 2 7 3 5 8 9 – compare elements 3 and 4 „ 1 2 7 3 5 8 9 – compare elements 2 and 3 - swap „ 1 2 3 7 5 8 9 – back to the start „ 1 2 3 7 5 8 9 – compare elements 5 and 6 „ 1 2 3 7 5 8 9 – compare elements 4 and 5 8 „ 1 2 3 7 5 8 9 – compare elements 4 and 5 „ 1 2 3 7 5 8 9 – compare elements 3 and 4 - swap „ 1 2 3 5 7 8 9 – back to the start „ 1 2 3 5 7 8 9 – compare elements 5 and 6 „ 1 2 3 5 7 8 9 – compare elements 4 and 5 „ 1 2 3 5 7 8 9 – back to the start *no swaps this time*1 2 3 5 7 8 9 back to the start no swaps this time „ 1 2 3 5 7 8 9 – compare elements 5 and 6 „ 1 2 3 5 7 8 9 – done Algorithm: bubbleSort Purposes: This algorithm sorts N numbers in an ascending order Input: N numbers in an array and N Pre: nil Return: The N numbers in an ascending order Post: The order of the numbers in the array is changed BEGIN bubbleSort (array,N) INITIALISE wallIndex to 0 WHILE (wallIndex < N-1 ) OR no swaps made in last pass( ) p p INITIALISE index to N-1 WHILE (index > wallIndex) IF (array[index] < array[index-1]) Swap(array,index,index-1); ENDIF DECREMENT index ENDWHILE INCREMENT wallIndex ENDWHILE RETURN array END bubbleSort Algorithm: bubbleSort Purpose: This algorithm sorts N numbers in ascending order Input: N numbers in an array and N Pre: nil Return: The N numbers in an ascending order Post: the order of the numbers in the array is changed BEGIN bubbleSort (array,N) INITIALISE wallIndex to 0 SET swapped to true WHILE (wall_index < N-1 AND swapped is true) Bubble Sort (another version) SET swapped to false INITIALISE index to N-1 WHILE (index > wallIndex) IF(array[index] < array[index-1]) Swap(array,index,index-1); SET swapped to true ENDIF DECREMENT index ENDWHILE INCREMENT wallIndex ENDWHILE RETURN array END bubbleSort Bubble Sort: Cost summary … „ Space: No extra array is needed. „ Operations – Comparisons & swaps – Worst case: N(N-1)/2 comparisons & N(N-1)/2 swaps – Best case: N-1 comparisons, 0 swapsp , p „ Worst case: if input is 50, 32, 11, 9, 7, 3, 1 21 comparisons and 21 swaps „ Best case: if input is 1, 3, 7, 9, 11, 32, 50 6 comparisons but no swaps 9 Summary of the 3 Sorting Algorithms „ Selection Sort: – We do calculations to find the right element to ‘place’ next. – Then, it is easy to place it. I ti S t„ Insertion Sort: – Easy to ‘get’ the next element. – We then do calculations to figure out where to put it, if necessary. „ Bubble sort: – Easy to get the pair of elements. – Do calculations to swap pairs around, if necessary. A costing summary Algorithm Selection Insertion Bubble Best Case: Comparisons N(N 1)/2 N 1 N 1 None of the algorithms require a copy of the array to be made. Best Case: Comparisons N(N-1)/2 N-1 N-1 Best Cast: Swaps/Moves 0 0 0 Worst Case: Comparisons N(N-1)/2 N(N-1)/2 N(N-1)/2 Worst Case: Swaps/Moves N-1 N(N-1)/2 N(N-1)/2 Comparisons? „ We have to be a little careful how we interpret what a comparison means. „ If we compare numerical values x and y, then it is reasonable to consider that we might need to determine whether x>y, yy and x<=y which can be done in a single comparisonand x<=y, which can be done in a single comparison operation. „ In other situations we may need two comparisons to distinguish between the equality and less than cases. „ When you learn about big O notation, you will learn that even if twice as many operations are required, the complexity of the algorithm is the same, since the big O measure it about the scaling of work as a function of some parameter, like the number of elements to be sorted. Comparing the 3 Sorting Algorithms „ Selection, Insertion & Bubble Sorts… – All do about the same amount of ‘work’ if the original array is totally unsorted. BUT: – If the array is already partially sorted,If the array is already partially sorted, then Insertion or Bubble sort do much less work. • They do no ‘work’ to find an element to consider, and then do NO work if that element doesn’t need to be moved or swapped! • On the other hand: Selection sort ALWAYS has to do ‘work’ just to get the next element to consider! 10 A couple of questions „ All three of the algorithms we have looked at take roughly N2 steps to perform the sort. „ Is this because this is the best we can do? „ It seems reasonable to assume that it will take at least as much work to sort a set of numbers asleast as much work to sort a set of numbers as to check that a set of numbers is already sorted. „ So we can safely say that the best possible sort must take at least around N steps. „ There is a big gap between N and N2 (especially as N gets big). „ Are there any sorting techniques that fill this gap? From Wikipedia: Sorting Algorithms Comparison sorts Not comparisonFrom Wikipedia: Sorting Algorithms Moving on to Searching! Problem: Design an algorithm to find the location of a specific number in a list of N numbers. List: 3,9,1,32,11,50,7Target:11 11 3,9,1,32,11,50,7 is this 11? 3,9,1,32,11,50,7 Searching: A first effort Location wanted is index 4 11? is this 11? YES! 3,9,1,32,11,50,7 is this 11? Sequential Search „ Operations: – Worst case: N comparisons. • The number is not in the array, or is at the end. – Best case: 1 comparison. • The number is at the start of the array. Costing a sequential search – Average case: N/2 comparisons. • N/2 comparisons if the number is in the array. • N comparisons if the number is not in the array, or is at the end. „ The comparisons here are used to distinguish between equal and not equal. „ Can we improve the worst case by changing the algorithm a little? How Can We Search Faster? Sort the array first! 3,9,1,32,11,50,7 Target:11 1,3,7,9,11,32,50 Sort We can now stop searching if we find a match, OR if we see a number larger than the one we’re searching for. 12 Compare SEQUENTIAL vs SORT Sequential Search Target is In Target is not in Best 1 N Worst N NWorst N N Average N/2 N SORT & SEARCH Target is In Target is not in Best 1 1 Worst N N Average N/2 Depends… Hang on… „ What about the cost of sorting? „ If you remember back to the sorting section the cost was roughly N2 steps for all three of the algorithms we looked at. „ But this means the cost of sorting would be greater than the cost of searching sequentiallythe cost of searching sequentially. – So why bother sorting then searching first. „ Well it is more the idea that if we are going to be searching without a list of data it makes sense to store it sorted. – This might mean that when we READ each element for a set of data it is inserted into the appropriate sorted position. „ If we had a set of data and only needed to find one number the sorting first would be too expensive, although it would make subsequent searches cheaper. How Can We Search Lots Faster? „ If we can gone to the trouble of sorting we should really use the extra structure. „ Binary Search: – Look at the middle element of the array. If we have a match– If we have a match… • We are done. – If it is too big… • Repeat with the first half of the array. – If it is too small… • Repeat with the second half of the array. „ Continue until we find it or we run out of array. 1,3,7,9,11,32,50 N/2 Target (11) < 9 =11? T t (11) > 9 Illustrating a binary search Target (11) < 9 =11? Target (11) > 9 1,3,7,9,11,32,50 =11?Target (11) < 32 Target (11) > 32