Thus, in terms of the card deck analogy, last represents the last card in the unsorted portion of the deck.A linear search looks down a list, one item at a time, without jumping. When last gets to be 0, the array will be sorted. On the second, it will be arr.length − 2, and so on. On the first call to this method, last will be arr.length − 1. The second parameter, int last, defines that portion of the array, from right to left, that is yet to be sorted. In this definition, the array is one parameter. The code provides a partial implementation of selection sort for an array of int. This is represented in our design by moving last down one element to the left. The recursive case involves searching an ever-smaller portion of the array. An array with one element in it is already sorted. The base case is reached when the last parameter is pointing to the first element in the array. If we use parameter to represent last, then it will be moved one card to the left at each level of the recursion. After each pass or recursion, the last card will be in its proper location, and the cards before it will represent the unsorted portion of the deck. The algorithm we just described is like a head-and-tail algorithm in reverse, where the last card in the deck is like the head, and the cards before it are like the tail. Let’s design a recursive version of this algorithm. If you repeat this process 51 times, the deck will be completely sorted. Then go through the deck again starting at the next to the last card, find the next largest card, and exchange it with the next to the last card. Starting at the last card, look through the deck, from last to first, find the largest card and exchange it with the last card. Lay them out on a table, face up, one card next to the other. To review the concept of Selection Sort, suppose you have a deck of 52 cards. */ private int search ( int arr, int head, int key ) Selection Sort in Java Using Recursion * Post: if arr = key for k, 0 <= k < arr.length, * Pre: arr != null and 0 <= head <= arr.length * search(arr,head,key)-Recursively search arr for key It controls the progress of the recursion. Here the head parameter serves as the recursion parameter. This underscores the point we made earlier about the importance of parameters in designing recursive methods. In effect, this is like saying the recursion should stop when we have reached a tail that contains 0 elements. The algorithm is bounded when head = arr.length. Note that the recursive search method takes three parameters: the array to be searched, arr, the key being sought, and an integer head that gives the starting location for the search. This leads to the definition for recursive search shown algorithm below. The method will stop when head = arr.length.Ī parameter, head, can represent the head of some portion of the array If we let head vary from 0 to arr.length on each recursive call, the method will recurse through the array in head/tail fashion, searching for the key. Our method will always be passed a reference to the whole array, but it will restrict the search to the portion of the array starting at head. Then ℎ□□□+1 represents the start of the tail, and arr.length-1 represents the end of the tail. Let’s have the int parameter, head, represent the current head of the array. To help us out of this dilemma, we can use an integer parameter to represent the head of the array. Unfortunately, we have no method comparable to the substring() method for strings that lets us represent the tail of the array. For an array named arr, the expression arr represents the head of the array. For strings, we had methods such as s.charAt(0) to represent the head of the string and s.substring(1) to represent the string’s tail. The challenge in developing this algorithm is not so much knowing what to do but knowing how to represent concepts like the head and the tail of the array. This algorithm clearly resembles the approach we used in recursive string processing: Perform some operation on the head of the array and recurse on the tail of the array. Return the result of searching the tail of the array If the array's head doesn't match the key, If the array's head matches the key, return its index
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |