CS Flashcards
Sequential Search
Also known as linear search
Considered to be simplest search algorithm
It works by iterating through a set of data sequentially until you find the item you are looking for.
The pseudocode is as simple as a for loop containing an if statement.
Things to note about sequential search
Data does not need to be sorted
On one hand it can save a lot of processing time
On another hand
you would need to go through the whole or most of the array in some cases
If the data was sorted you could put a test to see if we are at a stage where we are past where the number would be and stop the search and return not found.
Binary Search
Divides a range of values into halves ( divide and conquer)
Continues to narrow down the field of search by half until the value being searched is found.
Data must be presorted
Very efficient for large arrays
Ideal when resorting is not required
High level algorithm of binary search
Compare the search value with the value of the middle element of the array
If the values match
then the value is found
If the search value is less than the middle element
then the right half of the array is discarded
The new array becomes the left sub array and the algorithm is repeated on it.
If the search value is greater than the middle element’s value
then the left side of the array is discarded.
The new array becomes the right subarray and the algorithm is repeated on it
If the remaining array to be searched is empty then the value was not found.
Bubble sort
Simple sorting algorithm
Repeatedly steps through the array to be sorted
It compares adjacent elements and exchanges them if they are not in the correct order
After each loop
one less element needs to be compared
The algorithm is very slow and impractical for most cases
Selection Sort
Simple and inefficient sorting algorithm
Divides array into two sections
First section contains already sorted elements
The second contains the unsorted elements
At the beginning the section that contains the sorted elements is empty
And the section with the unsorted elements is the entire array
The algorithm finds the smallest element ( or largest depending on sorting order) in the unsorted section and exchanges it with the leftmost element in the unsorted section
uggest a suitable algorithm to solve a specific problem
Efficiency: amount of the computer resources required to perform its functions. Minimizing the use of various resources such as the CPU and memory is important.
Correctness: the extent to which the algorithm satisfies its specification
free from fault
Reliability: refers to the capability of the algorithm to maintain a predefined level of performance
Flexibility: effort required to modify the algorithm for other purposes
Sequential Search
Also known as linear search
Considered to be simplest search algorithm
It works by iterating through a set of data sequentially until you find the item you are looking for.
The pseudocode is as simple as a for loop containing an if statement.
Things to note about sequential search
Data does not need to be sorted
On one hand it can save a lot of processing time
On another hand
you would need to go through the whole or most of the array in some cases
If the data was sorted you could put a test to see if we are at a stage where we are past where the number would be and stop the search and return not found.
Binary Search
Divides a range of values into halves ( divide and conquer)
Continues to narrow down the field of search by half until the value being searched is found.
Data must be presorted
Very efficient for large arrays
Ideal when resorting is not required
High level algorithm of binary search
Compare the search value with the value of the middle element of the array
If the values match
then the value is found
If the search value is less than the middle element
then the right half of the array is discarded
The new array becomes the left sub array and the algorithm is repeated on it.
If the search value is greater than the middle element’s value
then the left side of the array is discarded.
The new array becomes the right subarray and the algorithm is repeated on it
If the remaining array to be searched is empty then the value was not found.
Bubble sort
Simple sorting algorithm
Repeatedly steps through the array to be sorted
It compares adjacent elements and exchanges them if they are not in the correct order
After each loop
one less element needs to be compared
The algorithm is very slow and impractical for most cases
Selection Sort
Simple and inefficient sorting algorithm
Divides array into two sections
First section contains already sorted elements
The second contains the unsorted elements
At the beginning the section that contains the sorted elements is empty
And the section with the unsorted elements is the entire array
The algorithm finds the smallest element ( or largest depending on sorting order) in the unsorted section and exchanges it with the leftmost element in the unsorted section
uggest a suitable algorithm to solve a specific problem
Efficiency: amount of the computer resources required to perform its functions. Minimizing the use of various resources such as the CPU and memory is important.
Correctness: the extent to which the algorithm satisfies its specification
free from fault
Reliability: refers to the capability of the algorithm to maintain a predefined level of performance
Flexibility: effort required to modify the algorithm for other purposes
