Save
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.
focusNode
Didn't know it?
click below
 
Knew it?
click below
Don't know (0)
Remaining cards (0)
Know (0)
0:00
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
 

 



Voices

Use these flashcards to help memorize information. Look at the large card and try to recall what is on the other side. Then click the card to flip it. If you knew the answer, click the green Know box. Otherwise, click the red Don't know box.

When you've placed seven or more cards in the Don't know box, click "retry" to try those cards again.

If you've accidentally put the card in the wrong box, just click on the card to take it out of the box.

You can also use your keyboard to move the cards as follows:

If you are logged in to your account, this website will remember which cards you know and don't know so that they are in the same box the next time you log in.

When you need a break, try one of the other activities listed below the flashcards like Matching, Snowman, or Hungry Bug. Although it may feel like you're playing a game, your brain is still making more connections with the information to help you out.

To see how well you know the information, try the Quiz or Test activity.

Pass complete!

"Know" box contains:
Time elapsed:
Retries:
restart all cards