Sorting Algorithms and Hash Tables
25 Questions
100 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the best runtime of Bubble Sort?

O(n)

What is the worst runtime of Bubble Sort?

O(n^2)

What is the average runtime of Bubble Sort?

O(n^2)

What is the best runtime of Selection Sort?

<p>O(n^2)</p> Signup and view all the answers

What is the worst runtime of Selection Sort?

<p>O(n^2)</p> Signup and view all the answers

What is the average runtime of Selection Sort?

<p>O(n^2)</p> Signup and view all the answers

What is the best runtime of Insertion Sort?

<p>O(n)</p> Signup and view all the answers

What is the worst runtime of Insertion Sort?

<p>O(n^2)</p> Signup and view all the answers

What is the average runtime of Insertion Sort?

<p>O(n^2)</p> Signup and view all the answers

What are the worst and average runtimes of Linear Probing, Quadratic Probing, and Separate Chaining Insertion?

<p>Worst = O(n), Average = O(1)</p> Signup and view all the answers

What are the worst and average runtimes of Linear Probing, Quadratic Probing, and Separate Chaining Search/Retrieval?

<p>Worst = O(n), Average = O(1)</p> Signup and view all the answers

What is the equation for Linear Probing?

<p>index = (hVal + i) % h-&gt;TABLE_SIZE</p> Signup and view all the answers

What is the equation for Quadratic Probing?

<p>index = (hVal + i * i) % h-&gt;TABLE_SIZE</p> Signup and view all the answers

What are the worst and best runtimes for Trie Insertion?

<p>O(k)</p> Signup and view all the answers

What are the worst and best runtimes for Trie Search?

<p>Worst = O(k), Best = O(1)</p> Signup and view all the answers

What are the worst and best runtimes for Trie Deletion?

<p>Worst = O(k), Best = O(1)</p> Signup and view all the answers

What are the worst case runtimes for AVL Tree Search, Insertion and Deletion?

<p>O(log n)</p> Signup and view all the answers

What are the worst case runtimes for BST Search, Insertion, and Deletion?

<p>O(n)</p> Signup and view all the answers

What is the best case runtime for BST Search, Insertion, and Deletion?

<p>O(log n)</p> Signup and view all the answers

What are the best case runtimes for AVL Tree Search, Insertion and Deletion?

<p>O(log n)</p> Signup and view all the answers

What type of data structure works best for Merge Sort?

<p>Linked Lists</p> Signup and view all the answers

What are the best, average, and worst runtimes for Merge Sort?

<p>O(n log n)</p> Signup and view all the answers

What is the pattern for INORDER tree traversals?

<p>Left, Root, Right</p> Signup and view all the answers

What is the pattern for PREORDER tree traversals?

<p>Root, Left, Right</p> Signup and view all the answers

What is the pattern for POSTORDER tree traversals?

<p>Left, Right, Root</p> Signup and view all the answers

Study Notes

Bubble Sort

  • Best runtime: O(n) - achieved when the input is already sorted.
  • Worst runtime: O(n^2) - occurs with reverse-sorted inputs.
  • Average runtime: O(n^2) - reflects inefficient comparisons in unsorted data.

Selection Sort

  • Best runtime: O(n^2) - selection sort always requires O(n^2) time regardless of input.
  • Worst runtime: O(n^2) - consistent performance under different conditions.
  • Average runtime: O(n^2) - no variation in efficiency across random inputs.

Insertion Sort

  • Best runtime: O(n) - optimal for nearly sorted data, performs minimal shifts.
  • Worst runtime: O(n^2) - occurs with completely unsorted lists, requiring maximum shifts.
  • Average runtime: O(n^2) - generally inefficient for larger data sets.

Hash Table Probing

  • Worst & average runtime for insertion: Worst = O(n), Average = O(1) across Linear Probing, Quadratic Probing, and Separate Chaining.
  • Worst & average runtime for search/retrieval: Worst = O(n), Average = O(1) similarly applies.

Probing Equations

  • Linear probing index equation: index = (hVal + i) % h->TABLE_SIZE.
  • Quadratic probing index equation: index = (hVal + i * i) % h->TABLE_SIZE.

Trie Data Structure

  • Insertion: Worst & Best runtimes are O(k), with k being the length of the key.
  • Search: Worst = O(k), Best = O(1).
  • Deletion: Worst = O(k), Best = O(1).

AVL and Binary Search Trees (BST)

  • AVL Tree operations (search, insertion, deletion): Worst case runtime is O(log n).
  • BST operations: Worst case runtime is O(n) due to potential degenerative structure.
  • Best case for BST operations: O(log n) when tree is balanced.

Merge Sort

  • Best, average, and worst runtimes: O(n log n) - efficient across different scenarios.
  • Best data structure for implementation: Linked Lists, allowing seamless merging.

Tree Traversals

  • Inorder traversal pattern: Traverse Left, then Root, then Right.
  • Preorder traversal pattern: Visit Root, then Left, then Right.
  • Postorder traversal pattern: Traverse Left, then Right, then Root.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Description

Explore the characteristics and performance of various sorting algorithms, including Bubble Sort, Selection Sort, and Insertion Sort. Additionally, the quiz covers hash table probing techniques and their respective runtimes. Test your understanding of these fundamental algorithms and data structures.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser