Searching and Sorting Algorithms Implement functions: a. iterative sequential se

ID: 3539053 • Letter: S

Question

Searching and Sorting Algorithms

Implement functions:

a. iterative sequential search (given in the chapter)

b. iterative binary search (given in the chapter)

c. recursive sequential search.

d. recursive binary search.

Also write a program to test your algorithms ( assume, that for binary search your data in array is in ascending order)

///Generic interface that describes various searching and sorting

//algorithms. Note that the type parameter is unbounded. However,

//for these algorithms to work correctly, the data objects must

//be compared using the method compareTo and equals.

//In other words, the classes implementing the list objects

//must implement the interface Comparable. The type parameter T

//is unbounded because we would like to use these algorithms to

//work on an array of objects as well as on objects of the classes

//UnorderedArrayList and OrderedArrayList.

import java.io.PrintStream;

public class SearchSortAlgorithms<T> implements SearchSortADT<T>

{

//Sequential search algorithm.

//Postcondition: If searchItem is found in the list,

// it returns the location of searchItem;

// otherwise it returns -1.

public int seqSearch(T[] list, int length, T searchItem)

{

int loc;

boolean found = false;

for (loc = 0; loc < length; loc++)

{

if (list[loc].equals(searchItem))

{

found = true;

break;

}

if (found)

return loc;

else

return -1;

} //end seqSearch

//Binary search algorithm.

//Precondition: The list must be sorted.

//Postcondition: If searchItem is found in the list,

// it returns the location of searchItem;

// otherwise it returns -1.

public int binarySearch(T[] list, int length, T searchItem)

{

int first = 0;

int last = length - 1;

int mid = -1;

boolean found = false;

while (first <= last && !found)

{

mid = (first + last) / 2;

Comparable<T> compElem = (Comparable<T>) list[mid];

if (compElem.compareTo(searchItem) == 0)

found = true;

else

if (compElem.compareTo(searchItem) > 0)

last = mid - 1;

else

first = mid + 1;

}

if (found)

return mid;

else

return -1;

}//end binarySearch

}

//Generic interface that describes various searching and sorting

//algorithms. Note that the type parameter is unbounded. However,

//for these algorithms to work correctly, the data objects must

//be compared using the method compareTo and equals.

//In other words, the classes implementing the list objects

//must implement the interface Comparable. The type parameter T

//is unbounded because we would like to use these algorithms to

//work on an array of objects as well as on objects of the

//classes UnorderedArrayList and OrderedArrayList.

public interface SearchSortADT<T>

{

public int seqSearch(T[] list, int length, T searchItem);

//Sequential search algorithm.

//Postcondition: If searchItem is found in the list,

// it returns the location of searchItem;

// otherwise it returns -1.

public int binarySearch(T[] list, int length, T searchItem);

//Binary search algorithm.

//Precondition: The list must be sorted.

//Postcondition: If searchItem is found in the list,

// it returns the location of searchItem;

// otherwise it returns -1.

public void bubbleSort(T list[], int length);

//Bubble sort algorithm.