Working with arrays--Searching and Sorting Algorithms Task 1: Searching an Array

Question

 Working with arrays--Searching and Sorting Algorithms

Task 1: Searching an Array Based List--Linear Search

Write a function that searches if a specific value exists in an array.  If the value is found, the function returns its index.  If the value is not in the array, it returns -1. Assume that the data in the array is not sorted.

Note: Swift has a build-in function called index(of:) that does the same thing.  However, our objective here is to study search algorithms.  So we're going to ignore it and write our own function.

Write an algorithm and verify it with an example

Implement it in Swift and test it.

Be ready to demo

Submit your final solution for credit

Task 2: A More Efficient Search for Sorted Lists

Assume the list stored in the array is sorted in ascending order. How would you change your search algorithm to make more efficient?

write an algorithm and verify it with an example

Implement it in Swift and test it

Be ready to demo

Submit your final solution for credit

Task 3: Sorting an array based list

Assume you’re given a list of numbers to sort (in either order). Develop an algorithm to sort it.

Note: Swift also has a sort function that can be used to sort arrays.  But then again, our objective in this activty is to study sorting algorithm as we work with arrays. So we will develop our own sort function(s).

To develop an algorithm you need to be able to solve the problem manually first using some sample data.

Create a sample list to work with

Sort the sample list manually

Note: As you develop your algorithm, you need to assume that the list is very long to the point that you can’t visually scan it all at once and sort the data mentally. This is to simulate the fact that the computer can only “see” one number at a time as it re-arranges them

Verify your algorithm with another simple example

Implement your algorithm in Swift

Test it using one of the examples you used in the steps above

Be ready to demo your algorithm and your Swift function

Explanation / Answer

//linear search

//BInary search

var lower = 0
var upper = a.count
while lower < upper {
let mid= lower + (upper - lower) / 2
if a[mid] == key {
return mid
} else if a[mid] < key {
lower = mid + 1
} else {
upper = mid
}
}
return -1
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.