4271214
Description
Flashcards by Ruth Hyndman, updated more than 1 year ago
|
Created by Ruth Hyndman
over 8 years ago
|
|
| Question | Answer |
| Name 3 types of array. | > Any value type eg int, decimal, double > String > Objects |
| Name some ways we sort Arrays. | > Selection Sort > Bubble sort > Insertion sort > Merge sort > Quick sort |
| What is a selection sort? | Selection sort is one of the basic algorithms for sorting data, its simplicity proves useful for sorting small amounts of data. Selection sort works by first starting at the beginning array (index 0) and traverses the entire array comparing each value with the current index, if it is smaller than the current index than that index is saved. Once the loop has traversed all the data and if a smaller value than the current index was found a swap is made between the current index in the index where the smaller value was found. The current index is then incremented, now to index 1, the algorithm repeats. Of course, a visual representation is usually more useful. Take an unsorted array that holds five integers.There are three main variables in selection sort, the variable 'i' keeps the index that may be potentially switched if a smaller value is found. The variable 'j' traverses through the array searching for a value smaller than 'min'. The variable 'min' is the current smallest value in the array, it's updated only if a value smaller than it is found. Since 'min' always receives the v |
| more + time complexity | The time complexity of selection sort is O(n2), for best, average, and worst case scenarios. Because of this selection sort is a very inefficient sorting algorithm for large amounts of data, it's sometimes preferred for very small amounts of data such as the example above. The complexity is O(n2) for all cases because of the way selection sort is designed to traverse the data. The outer loops first iteration has n comparisons (where n is the number of elements in the data) the second iteration would have n-1 comparisons followed by n-2, n-3, n-4...thus resulting in O(n2) time complexity. |
| Pseudocode of Selection Sort | SELECTION-SORT(A) 1. for j ← 1 to n-1 2. smallest ← j 3. for i ← j + 1 to n 4. if A[ i ] < A[ smallest ] 5. smallest ← i 6. Exchange A[ j ] ↔ A[ smallest ] |
| Selection Sort: Example 2 | static void Main(string[] args) { int[] arr= new int[5]{23,2,3,34,6}; //output list before sorting outputArray(arr); selectsort(arr,5); //call sorting method outputArray(arr); } for(int i=0; i<5; i++) { Console.Write(arr[i]+"\t"); }//print list |
| What is a Bubble sort? | Bubble Sort is a sorting algorithm (an algorithm that puts elements of a list in a certain order). The simplest sorting algorithm is Bubble Sort. The Bubble Sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted. |
| Bubble sort Algorithm | int[] number = { 89, 76, 45, 92, 67, 12, 99 }; bool flag = true; int temp; //sorting an array for (int i = 1; (i <= (number.Length - 1)) && flag; i++) { flag = false; for (int j = 0; j < (number.Length - 1); j++) { if (number[j + 1] > number[j]) { temp = number[j]; number[j] = number[j + 1]; number[j + 1] = temp; flag = true; } } } //Sorted array foreach (int num in number) { Console.Write("\t {0}",num); } |
| Name methods for searching an array. | - Sequential search (Linear Search) - Binary search |
| What is a Sequential Search (Linear)? | Sequential search(Linear search) is the simplest search algorithm. A sequential (linear) search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search - the time taken to search the list gets bigger at the same rate as the list does. |
| What is a Binary Search? | A binary search is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you're looking for, which determines whether the value is in the first or second half of the list. In complexity terms this is an O(log n) search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation. |
| Linear vs. Binary Search | Binary search requires the input data to be sorted; linear search doesn't Binary search requires an ordering comparison; linear search only requires equality comparisons Binary search has complexity O(log n); linear search has complexity O(n) as discussed earlier in the notes Binary search requires random access to the data; linear search only requires sequential access (this can be very important - it means a linear search can stream data of arbitrary size) |
Want to create your own Flashcards for free with GoConqr? Learn more.