Sorting,searching And Validation Flashcards
What is an algorithm?
A sequence of logical instructions for carrying out a task.
In computing, algorithms are needed to design computer programs.
What are sorts and searches algorithm?
sorts allow a data set to be sorted into order.
searches allow a set of data to be examined and for a specific item to be found.
What are the 2 kinds of sorting?
Definitions
Merge-A sorting algorithm that repeatedly divides a list in half until each has only one item.
The individual lists are then merged.
Bubble-A sorting algorithm that repeatedly passes through a list to be sorted, comparing and swapping items that are in the wrong order.
What are 2 kinds of searching definitions?
Linear-A function designed to search for the presence of an item stored within an array or database.
Binary-A method of searching in which the data being searched is halved with every step.
How does a merge sort algorithm work?
A merge sort uses a technique called divide and conquer.
The list is repeatedly divided into two until all the elements are separated individually.
Pairs of elements are then compared, placed into order and combined.
The process is repeated until the list is recompiled as a whole.
The pairs are then compared, starting with the first number in each pair.
If the left-hand number is smaller than the right-hand number, it is placed in order.
The comparison then moves up to the second number on the left-hand side and the process repeats.
If the right-hand number is smaller, it is placed in order and the comparison moves to the next number on that side.
How does a bubble sort algorithm work?
Start at the beginning of the list.
Compare the first value in the list with the next one up. If the first value is bigger, swap the positions of the two values.
Move to the second value in the list. Again, compare this value with the next and swap if the value is bigger.
Keep going until the there are no more items to compare.
Go back to the start of the list.
What types of validation could a programmer include?
Range check - the input must fall within a specified range. This is usually applied to numbers and dates but can apply to characters. For example, when making a payment to someone, the amount to be entered might be set to be greater than zero and not greater than the funds available.
Length check - the input must not be too long or too short. For example, a surname will require at least one letter but is unlikely to require more than 40.
Presence check - a data value must be entered. For example, entering a quantity when placing an order.
Format check - the data must be in the correct format, such as entering a date in the format DD/MM/YYYY.
Type check - the data must be of a specified data type, such as an integer when specifying a quantity.
Lookup table - this allows the user to pick one item from a specified pre-defined list.
Check digit - often used on identification numbers, such as bank account numbers, to ensure the numbers have been entered correctly.
What examples of validation are there?
presence check - a username must be entered
length check - a password must be at least eight characters long
range check - age restrictions may require the user’s date of birth to be before a certain date
format check - the user’s date of birth must be entered in the specified format
type check - the password may need to have a mixture of upper- and lower-case letters, a number and a special character
look up check - the title must be from a pre-defined list of valid entries
Why might verifies needed?
To check if the data entered is correct, verification is needed. Take, for example, a customer’s email address. A company wants to make sure they get this correct so they might use data verification to ensure it is entered correctly.
A user may accidentally enter a date of birth that is possible and sensible, but incorrect. The program has no way of knowing that the date has been entered incorrectly.
What are the 2 main methods of verification?
Double keying - entering the data twice and comparing the two copies.
Proofreading data - this involves someone checking the data entered against an original document. This is time-consuming and costly and is mainly used only for very important information such as the checking of ID.
How does a linear search work?
Find out the length of the data set.
Set counter to 0.
Examine value held in the list at the counter position.
Check to see if the value at that position matches the value searched for.
If it matches, the value is found. End the search.
If not, increment the counter by 1 and go back to step 3 until there are no more items to search.
How does a binary search work?
Start by setting the counter to the middle position in the list.
If the value held there is a match, the search ends.
If the value at the midpoint is less than the value to be found, the list is divided in half.
The lower half of the list is ignored and the search keeps to the upper half of the list.
Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
The search moves to the midpoint of the remaining items.
Steps 2 through 4 are repeated until a match is made or there are no more items to be searched.
