Data Structures - Sorting and Searching

Ruth Hyndman
Flashcards by Ruth Hyndman, updated more than 1 year ago
Ruth Hyndman
Created by Ruth Hyndman over 5 years ago
31
3

Description

Flashcards for the Data Structures - sorting and searching unit of the AS cause for SSD by CCEA.

Resource summary

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)
Show full summary Hide full summary

Similar

Cell Structure
megan.radcliffe16
Exchange surfaces and breathing
megan.radcliffe16
OCR AS Biology
joshbrown3397
AQA AS Biology Unit 2 DNA and Meiosis
elliedee
Biology Unit 1
hannahsanderson1
Cells And Cell Techniques - Flashcards (AQA AS-Level Biology)
Henry Kitchen
PSYA1 - attachment, AQA psychology
T W
Psychology subject map
Jake Pickup
Biological Psychology - Stress
Gurdev Manchanda
AS Biology Unit 1
lilli.atkin
Random German A-level Vocab
Libby Shaw