Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
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
Normal Size Small Size show me how
Chapter 18
Searching and Sorting
| Term | Definition |
|---|---|
| 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
Popular Engineering sets