Busy. Please wait.
or

show password
Forgot Password?

Don't have an account?  Sign up 
or

Username is available taken
show password

why


Make sure to remember your password. If you forget it there is no way for StudyStack to send you a reset link. You would need to create a new account.
We do not share your email address with others. It is only used to allow you to reset your password. For details read our Privacy Policy and Terms of Service.


Already a StudyStack user? Log In

Reset Password
Enter the associated with your account, and we'll email you a link to reset your password.
Don't know
Know
remaining cards
Save
0:01
To flip the current card, click it or press the Spacebar key.  To move the current card to one of the three colored boxes, click on the box.  You may also press the UP ARROW key to move the card to the "Know" box, the DOWN ARROW key to move the card to the "Don't know" box, or the RIGHT ARROW key to move the card to the Remaining box.  You may also click on the card displayed in any of the three boxes to bring that card back to the center.

Pass complete!

"Know" box contains:
Time elapsed:
Retries:
restart all cards
share
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

  Normal Size     Small Size show me how

Chapter 18

Searching and Sorting

TermDefinition
Searching Data Involves determining whether a value(referred to as the search key) is present in the data and, if so, finding the value's location
Sorting Places data in order, based on one or more sort keys
Linear Search Algorithm Searches each element in an array sequentially
Big O Notation A measure of the worst-case runtime for an algorithm - that is, how hard an algorithm may have to work to solve a problem
Constant Runtime Means that the number of comparisons a particular search algorithm does is constant - it does not grow as the size of the array increases. Represented in Big O notation as O(1). Ex: Algorithm designed to test whether 1st element of array is equal to 2nd
1. Linear Runtime Describes a search algorithm that requires a total of n - 1 comparisons. Represented as O(n). Pronounced "on the order of n" or "order n".
2. Linear Runtime Ex: An algorithm that test whether the first element of an array is equal to any of the other elements of the array will require at most n - 1 comparisons, where n is the number of elements in the array
1. Quadratic Runtime Describes an algorithm in which the number of comparisons grows as the square of n(doubling number element quadruples number comparisons). Represented as O(n^2). Pronounced "on the order of n-squared" or "order n-squared".
2. Quadratic Runtime Ex: An algorithm that tests whether any element of an array is duplicated elsewhere in the array. The 1st element must be compared to every other element in the array, then the second element to every other element, then the third and so on.
1. Binary Search Algorithm More efficient than the linear search algorithm, but requires that the array first be sorted. Test middle element in array, if it is a match, algorithm ends. If search key is less than middle element, the algorithm searches only the first half of array.
2. Binary Search Algorithm If search key is greater than the middle element, algorithm searches only second half of the array. Each iteration tests the middle value of the remaining portion of the array.
Method Sort A static method of class Array that sorts the elements of an array in ascending order
Logarithmic Runtime All logarithms grow at roughly the same rate, so in Big O notation the base can be omitted. This results in a Big O of O(log(n)) for a binary search, which is also known as logarithmic runtime
Selection Sort A simple, but inefficient, sorting algorithm. First iteration of algorithm selects smallest element in array and swaps it with first element. Second iterations selects second-smallest element and swaps it with second element, and so on.
Insertion Sort A simple, but inefficient, sorting algorithm. 1st Iteration takes 2nd element in array and, if less than first, swaps them. 2nd iteration looks at 3rd element and inserts it in correct position with respect to first 2 elements, so all 3 elements in order
1. Merge Sort An efficient sorting algorithm but is conceptually more complex than selection and insertion sort. Sorts an array by splitting it into two equal-sized subarrays, sorting each subarray and merging them in one larger array.
2. Merge Sort With an odd number of elements, the algorithm creates the two subarrays such that one has one more element than the other
Created by: TimC#Programming