Data Structure 6

  1. What is selection sort? 
    which element do you find first and where do you put it? 
    how many times? 
    what is the time complexity?
    • Find the smallest element, put it in the right place.
    • Find the smallest remaining element, put it in the right place.
    • Repeat until everything is in place.
    • Time complexity: O(n2)
  2. what is bubble sort? 

    what is the time complexity?
    BubbleUp the smallest element to the first slot in the array.

    BubbleUp the smallest remaining element to the second slot in the array.

    Repeat until everything is in place.

    BubbleUp operation changes the locations of other elements in the array.

    Time complexity: O(n2)
  3. What is insertion sort?
    when does it stop? 
    what is the time complexity?
    what is the worst case scenario?
    An array is divided into a sorted part and an unsorted part.

    The insertion sort algorithm moves elements one at a time from the unsorted part into the correct position of the sorted part.

    This process continues until all the elements have been sorted.

    Time complexity: O(n2) for the general case, O(n)for the best case where all the elements are already sorted in the correct order.

    The worst case scenario is when the elements in the array are in reverse order.
  4. What is merge sort?
    what is the name of this algorithm?

    what does it need? 
    what is the time complexity?
    • A divide-and-conqueralgorithm.
    • Divide the unsorted array into n subarrays, each containing 1 element (remember that an array of 1 element is considered sorted).
    • Repeatedly merge subarrays to produce new subarrays until there is only 1 subarray remaining.
    • This will be the sorted array.Merge sort is a recursive algorithm:
    •     The base case is an array of only one element.
    •     At the recursive step, the merge sort is applied to each half problem, recursively sorting each half and putting them back together.
    •     Requires an auxiliary array.
    •     Time complexity: O(nlogn)
  5. what kind of algorithm is quick sort? 
    what happens at every stage?

    when does it stop? 

    what is the time complexity?
    • Also a divide-and-conqueralgorithm.
    • At each stage the part of the array being sorted is divided into two subarrays, with everything in the left subarray less than or equal to the split value (pivot) and everything in the right subarray greater than the split value.
    • The same approach is used to sort each of the smaller subarrays (a smaller case).
    • This process goes on until the small subarrays do not need to be further divided (the base case).
    • Time complexity: O(nlogn) if the splits divide the segment of the array approximately in half.
    • It could be as bad as O(n2) if the splits are very lopsided.
  6. what is heap sort? 
    what is it used for? 
    what is reheap?
    what is the time complexity?
    • Building a heap for the unsorted sequence.
    • Take the root (maximum) element off the heap, and put it into its place.
    • reheap the remaining elements. (This puts the next-largest element into the root position.)
    • Repeat until there are no more elements.
    • Time complexity: O(nlogn)
  7. what is a stable sort?
    • A sorting algorithm that preserves the order of
    • duplicates.
  8. what sorts are unstable?
    quicksort and heapsort
  9. what is linear search?

    what is its complexity?
    • A linear search examines all values in a sequence until it finds
    • a match or reaches the end.
    • Time complexity: O(n)
  10. What is a binary search? how does it work?

    how must the elements in the array already be? 

    what is the time complexity?
    • Binary search cuts the search in half each time.
    • We do not visit every element.
    • This is only possible when the values in the array are already sorted.
    • Time complexity: O(logn)
  11. what is hashing?
    • The technique for ordering and accessing elements in a list in
    • a relatively constant amount of time by manipulating the key to
    • identify its location in the list.
  12. what is hash function?
    A function used to manipulate the key of an element in a list to identify its location in the list.
  13. what is hash table?
    A data structure used to store and retrieve elements using hashing.
  14. what is collision?
    The condition resulting when two or more keys produce the same hash location
  15. what is linear probing?
    resolving a hash collision by sequentially searching a has table beginning at the location returned by the hash function.
  16. what is bucket?
    collection of elements associated with a particular hash location.
  17. what is chaining strategies?
    A linked list of elements that share the same hash location.
Card Set
Data Structure 6
final test