Here is with chapter 2 of Grokking Algorithms.
• Computer memory is like a giant set of drawers, each drawer has an address. Each time we want to store an item we ask computer for some space and it gives us an address where we can store the item.
• Storing multiple items requires an array or a list
“Array Vs Linked List”
Arrays
• using array means our items will be stored contiguously in memory.
• Every time we add an item to the array we need to check if there is an empty place in the array it is added successfully else we need to ask if there is an empty place in memory that fits all our items right next to each other.
• The place of an item in array is known because items are stored contiguously so to read an item from array it takes O(1).
• To insert in an array it takes O(n) as if we want to insert item at the beginning of an array we will need to shift all other items in the array.
• To delete from an array it also takes O(n) as every thing needs to be moved up when we delete an item.
• Elements in array should be of the same type (int, string...etc,)
“Let’s say we created an array with 10 slots but used only 5 slots in this case we won’t need to move to a new place in memory but here we wasted 5 places in memory.”
Linked Lists
• using linked lists allow items to be stored anywhere in memory.
• Each item in the list stores the address of the next item.
• insertion takes O(1) in linked list as we only need to change what a previous element points to.
• deletion takes O(1) as well .
• Reading from a linked list takes O(n) as reading needs to go one by one to read the required element.
“Selection Sort”
• sorting items according to certain criteria like:
1. sorting list of songs from most liked to least.
2. travel dates
3. emails ( newest to oldest)
4. names in a phone book
• time complexity of selection sort is O(n2) as we loop through list items 2 times (n x n).
# Here is an example of selection sort to find the smallest number in an array.
Top comments (0)