Week 2 Flashcards
Types of sorting algorithms
*Selection Sort
*Bubble Sort
*Insertion Sort
Selection Sort
*Works by sorting the list one item at a time
*List divided into two parts: Sorted part and Unsorted part
*Initially, sorted part is empty and unsorted part is the entire list
*The smallest element is selected from the unsorted array and swapped with leftmost element, and the element becomes a part of the sorted array
Bubble Sort
*Works by repeatedly passing through the list to be sorted and swapping adjacent items if they are in the wrong order
*If sorting into ascending order the largest item will bubble to the top
Insertion Sort
*Sort a list one item at a time
*The list split into a sorted part and non-sorted part
*With each iteration, it takes the next element waiting to be sorted and inserts it into the sorted part, into its proper location within the sorted items
Efficiency of Sorting Algorithms
*Sequential sorts
*Logarithmic sorts
Types of Searching Algorithms
*Sequential Search
*Binary Search
Sequential Search
*Can be used on a list of objects stored in any order
*Method: Start the search at the beginning of the list -> check every element of the list in turn until either the target is located or you reached the end of the list
Binary Search
*Can be used on a list of objects stored in a SORTED order
*Method: Starts by examining the element in the MIDDLE of the list(The search continues if the target element found at the middle element) -> the process repeated on this half of the list by examining the middle element and then eliminating the list -> either target element found or not in the list
What is a Recursion
A technique whereby a problem is expressed in a similar form to the original problem but smaller in scope
Areas where Recursion can be used
*Stopping case (The solution is easy to specify for certain conditions)
*Recursive steps (There are well defined rules for proceeding to a new state which is either a stopping case or eventually leads to a stopping case)
