Selection sort - Arrays and Linked list Flashcards
How is computer memory conceptually organized?
Like a giant set of drawers, where each drawer (memory slot) has an address and can hold one element.
What are the two basic ways to store multiple items in memory?
- Arrays
- Linked lists
How are items stored in an array?
Contiguously (right next to each other) in memory.
How are items stored in a linked list?
Items can be anywhere in memory, with each item storing the address of the next item.
What happens when you need to add an item to an array that’s full?
You need to request a new, larger chunk of memory and move all existing items there.
What is a common workaround for the array expansion problem?
“Holding seats” by requesting more memory slots than initially needed.
What are the downsides of “holding seats” in arrays?
- Memory may be wasted if extra slots aren’t used
- You may still need to move if you exceed the extra capacity
Why are linked lists better for insertions?
You can place the new item anywhere in memory and update the previous item to point to it.
What does “random access” mean?
The ability to jump directly to any element by its index (like arrays provide).
What does “sequential access” mean?
Reading elements one by one starting from the first element (as in linked lists).
Which data structure is better for reading random elements?
Arrays, because you can calculate the exact memory address of any element immediately.
Which data structure is better for insertions and deletions in the middle?
Linked lists, because you only need to update the pointers of adjacent elements.
How does selection sort work?
Find the smallest/largest element, add it to a new list, and repeat with the remaining elements.
What is the time complexity of selection sort?
O(n²) time.
