Searching And Sorting

Question 1

public static int search( int[ ] nums, int numRequired)
{
for ( int i=0; i < nums.Length; i++ )
{
if ( nums[i] == numRequired)
return i ;
}
return - 1;
}
What improvement could be made to the linear search method above if the array passed as a parameter has the figures sorted in numerical order?

Answer 1

Check if current number is greater than target number.
Exit loop. On average this will greatly enhance efficiency.

Question 2

Discuss why a linear search method might not be effective for a large array of sorted numbers and why the binary search method would improve efficiency.

Answer 2

Sorted array would allow for search from either end.
Average number of comparisons is half of array length.
Could half search area until found or not present.

Question 3

Name and describe a simple sorting method.

Answer 3

Bubble sort.

The bubble sort is a simple sorting algorithm not suitable for large sets of data due to O(n2) performance.

The bubble sort passes sequentially over a list, comparing each value to the adjacent following value.

Their positions are swapped if the first value is greater. Each pass finds the maximum item and puts it at the end and so the list to be sorted can be reduced at each pass.

A boolean variable is used to track if any swaps have been made in the current pass.

The algorithm terminates when a pass completes without any swaps (boolean variable is false).

Question 4

Indicate the number of swaps at each pass.
5, 16, 11, 7, 26

Answer 4

1st pass 5 11 7 16 26 2 swaps(true)
2nd pass 5 7 11 16 26 1 swap (true)
3rd pass 5 7 11 16 26 0 swap (false) – terminate

Question 5

A linear / sequential search may be used to locate a required value in an array.
1.Give one reason why this is not efficient when searching a large sorted array.

Answer 5

Full array searched if value not present.
Time complexity.
Very inefficient if target value is located towards end of array but may improve by exiting when a higher value than target value reached.

Question 6

Name an efficient technique, with which you are familiar, that is recommended for searching a large sorted array.

Answer 6

Binary

Question 7

Using this technique, write a method that, given a large sorted integer array and a target value, will search the array and return the target array index if found or −1 if it is not found.

Answer 7

public static int BinarySearch( int[] arr, int target){
int minIndex = 0, maxIndex = arr.Length -1, midIndex;
while (minIndex <= maxIndex){
midIndex = (minIndex + maxIndex ) / 2;
if ( target == arr [ midIndex ] )
return midIndex;
else if (target < arr [ midIndex ] )
maxIndex = midIndex – 1;
else
minIndex = midIndex + 1;
}
return – 1;
}

Question 8

Choose a simple sorting method that can be used to sort data. Describe how this sort works.

Answer 8

Bubble.
Description of sequence.
Pass.
Swap method.
Termination.