3 Types of Algorithms Every Programmer Needs to Know

hey my name is Forest welcome back so there are three types of algorithms you should know as a programmer we actually go over nine algorithms in this video what they are how they work rare world use cases complete with code examples and explanations but they fall under three categories three types of algorithms you should know sorting algorithms used to rearrange elements in a list or an array in a certain order searching algorithms used to find or retrieve an element from a data structure or to determine its existence and location in the data set and graph algorithms used to solve problems related to graph Theory where data is represented as a collection of nodes or vertices connected by edges you probably know these as trees and just as I did in my Ford data structures video I want to say I'm proud of you for clicking on this video because this isn't the glitz and glamour where you can watch this video and dream about being a software engineer this is the getting into the nitty-gritty the stuff that you do that will actually make you a software engineer so why are these algorithms you should know because they form the foundation of efficient problem solving in computer science studying these not only enhances programming skills but deepens analytical thinking and their instrumental and optimizing software performance among a wide array of real world applications it's like the difference between building something with a hammer versus a nail gun and this is a quick analogy I promise they both get the job done but the nail gun is clearly more efficient for most projects but sometimes the hammer would actually be a better choice because it could be more efficient due to the scope of the task same with algorithms some may be better for most tasks but not all tasks and you need to know these different algorithms exist to know which one to use because if you never knew a nail gun exist did well good luck trying to frame your entire house using just a hammer it may take you a while so sorting algorithms a sorting algorithm is a method of process used to rearrange elements in a list or an array in a certain order whether it be ascending descending or even based on some complex rules the purpose of sorting is to organize data in a way that makes it easier to use easier to search analyze and display information efficiently if you wanted another analogy it's like if you take a shuffle deck of cards and you want to put it in order here are actually eight different sorting algorithms working on four different initial condition conditions random nearly sorted reversed and few unique it's a beautiful representation of how these algorithms are great at sorting some initial conditions but bad at sorting others but I want to break it down even further let's take a look at bubble sword helping programmers learn how not to sort things since the 1950s but a great representation of showing how sorting algorithms work bubble sort is a simple sorting algorithm that repeatedly steps through the array element by element comparing the current element with the one after it swapping their values that the former is larger than ladder repeating again and again until the array is finally sorted the code works as such first it determines the length of the array the outer for Loop represents each iteration through the entire array but along the way the inner for Loop iterates over the unsorted part of the array where the if statement Compares adjacent elements bubbling the larger elements all the way to the top that's the infamous bubble sword it has an average and worst case time complexity of Bigos squared which means it's not a very good choice for sorting things insertion sort however is a little bit better most the time insertion sord is a simple sorting algorithm again that builds the final sorted array one element at a time the code works as such the for Loop sequentially selects each element of the array starting at index one which is the second element in the array for each selected element which is key the while loop Compares it with the elements in the sorted section of the array so all the elements before the current position while key is smaller than the sorted elements those sorted elements are shifted to the right to make space until the correct position for key is found where it is then in inserted this process repeats until each element has been correctly placed resulting in a sorted array like bubble sort it does have an average in worst case time complexity of Big O squared however its best case time complexity is Big O making it aine choice in situations where the data set is nearly sorted but a poor choice when the data set is reversed now that we've seen some not so great yet simple and good representations of sorting algorithms let's take a look at one of the more efficient sorting algorithms merge sort merge sort is an efficient stable and comparison-based dividing conquer sorting algorithm and it's recursive it divides the input array into two halves calls itself for the two halves recursion sorting them and then merges the two sorted halves the code works as such the merge sort function checks if the array has more than one element since a single element is already sorted it then splits the array into two halves recursively the function is called for each half once these halves are sorted the merg function then takes these two sorted halves and merges them into a single sorted array this merging is done by comparing the elements of both halves one by one and placing this smaller element into the new array continuing this process until all elements are sorted and merged merged sort has a Time complexity of Big O of in log in in all cases however it requires additional space for those temporary arrays used during the merge process which can be an issue in memory constrained environments whereas an algorithm like quick sort which is almost or often times equally as good as merge sort is an in place sort which requires very little memory and there are many more sorting algorithms like selection sort shell sort Heap Sort and so on the Sorting algorithm you use depends on your use case system capabilities and the specific characteristics of the data you're dealing with like size or whether or not it's partially sorted already sorting algorithms are fundamental in computer science and are used in many real world applications from organizing files on a computer to arranging database records for easy retrievable now I don't have any actual sponsors for this video but if you ever wish to support the channel there are three things that you could do if you find them beneficial to yourself one is subscribe to the channel two is subscribe to my free software engineering newsletter devotes at devotes daily.com or three if you're student consider purchasing studious for notion at notion student.com now searching algorithms a searching algorithm is a method or process used to find or retrieve an element from a data structure the goal is to find whether an item exists in the data set and often times to determine its location it's akin to open in the Yellow Pages to look for a specific phone number but you have to do it thousands of times so you better make sure your searching algorithm is correct you know how much I love these real analogies one way to do it is via a sequential search algorithm like linear search which is exactly what it sounds like each element is checked in sequence until you find what you're looking for or the list inss and if the current element equals what we're looking for which is X return it the average in worst case time complexity is Big O of in where n is the number of elements in the array so in other words if the element is found in the first index well then this is a pretty good searching algorithm to use but if the last index maybe not so much an interval search like binary search would be a more efficient approach assuming that this is a sort of data set it works by dividing the search interval in half repeatedly so if we wanted to use that analogy of the Yellow Pages in this example which is alphabetical order so already sorted it would be like opening the book directly in half and based on the name let's say it starts with a T well you eliminate the first half then you take the second half split that one in half check the middle element there and then see which side of that middle element that it's on eliminate that half so on and so forth until you find that element or it's not in the list the code works as such you start by passing in the sorted array in the element you're looking forward into the binary search function initialize the left and right boundaries to represent the current search interval the while loop accesses the middle of the current search interval compares the middle element of the array with the target value and if they are not equal eliminates the half of the array that doesn't contain the target it then repeats this process on the remaining half until you find the Target or the array can't be divided any further meaning the target isn't there the time complexity of binary search is Big O of log in in the worst and average cases making it significantly faster than linear search for sorted AR raay and of course there are many other searching algorithms like jump or exponential or Fibonacci or you could just use a hash tail search and just look up the key in the hash table with the Big O of one time complexity but you know that's not always the case so we got to actually discuss these other ones because searches utilizing tasks such as querying databases or searching for something in your files I'm pointing to my computer here by the way and many other applications where quick retrieval is crucial graph algorithms are another type of algorithm you should know graph algorithms are a set of instructions used to solve problems related to graph Theory where data is represented as a collection of nodes connected by edges like trees graph algorithms are pretty dang crucial for handling and analyzing relationships between Elements which are used in numerous real world applications like computer networks social networks and literal roadmap you know how you type in an address in maps and get directions or maybe you you know type it in a map quest and print it out if you're living in 2005 well this is an example of a graph algorithm at work remember the data you use graph algorithms on is a collection of nodes connected by edges you get to get the nodes as intersections and the edges as roads a rather inefficient way to go about this would be to utilize DFS or depth first search which I have quite a bit of experience with but depth first search is exactly what it sounds like you go as deep as possible in a single way see if it works then backtrack if it doesn't so it basically just keeps trying different routes at each intersection to see if it gets to where you need to go checking every possible turn and road to reach your destination not exactly the best way to go about it but but it's recursive yes it's recursive you can see how it works in the code here the DFS function gets past the graph it needs to Traverse its starting node and nodes that it has already visited during each recursive call the function marks the current node is visited then iteratively explores each of the nodes unvisited neighbors and if a neighbor is not visited this process continues until all reachable nodes from the starting point have been visited and I would discuss the time complexity of DFS here but it really depends on how you go about it if the graph is represented using adjacency lists then this is a Time complexity but if the graph is represented using an adjacency Matrix this is the time complexity however we could talk about space complexity whereas most of the time DFS will have a big O of V Space complexity which v stands for vertices otherwise known as nodes they're interchangeable now when talking about DFS you always got to talk about BFS breadth first search which again is exactly how it sounds breadth first so expanding wide simultaneously instead of singular depth like DFS BFS is a layer by layer approach casting a wide net from your starting point and gradually widening it so basically if you're standing in the middle of an intersection with four options or four roads you take all four of those rows to their next intersection one at a time that's the first layer and if you aren't at your final destination at any of these intersections or again no then you start the next layer by checking all remaining roads or edges at each one of those intersections you are now at 12 nodes simultaneously and checking all edges from there to the next nodes until you find your destination that's all this is it's like your kids in the back seat are we there yet are we there yet are we there yet we will turn this van around Mister he started it but instead it's you asking yourself that at each layer and because BFS keeps track of the paths taken you're now able to trace back the route taken which will be the shortest path but only in terms of of layers traversed yeah again not the best way to go about it and has the same space and time complexity of DFS as well instead we'll use deer's algorithm this is quite literally the algorithm that Google Maps uses or at least a modified and enhanced version of D algorithm which is a star algorithm and then they also modify and advance that algorithm in order to get their proprietory thing that works way better than Apple Maps all the time we can talk about both DX's algorithm finds the shortest path between a given node which is called The Source node in all other nodes in a graph not only that it also uses the weights of the edges again roads to find the path that minimizes the total weight or distance between the source node and all other nodes so in short it takes into account the distance and cost of each road which is akin to considering factors like Road length traffic conditions and speed limits to determine the quickest route this is the only algorithm of these three that's actually thinking ahead recalculating the best route as you move from node to node and of course AAR I had to talk about it AAR is a graft IAL and pathf finding algorithm used in many fields of computer science due to its completeness optimality and optimal efficiency like deer's algorithm a star is a sophisticated algorithm used to find the shortest path between point a and point B it's broadly the same thing except it uses a heuristic function giving priority to nodes that are supposed to be better than the others so estimating the cost from the current node all the way to the destination at every node prioritizing nodes that are believed to be closer to the goal making it more efficient DX's algorithm does not have this heuristic and there are so many more algorithms I want to discuss like dynamic programming using the Fibonacci sequence or the napsack problem hint hint dynamic programming by the way is just breaking down problems into smaller sub problems but also hashing algorithms to efficiently map data of any size to data of a fixed size that is a fun one and so many more so if you want to see more you want me to do that just let me know I love this stuff I'd make nothing but these videos if I could so just if you do like it make sure you subscribe again leave a comment to let me know and turn on the Bell notification so you get notified when I upload my next algorithm video again I'm Forest I'll see you in the next one

Channel: ForrestKnight

Views: 455,684

Keywords: algorithms, data structure and algorithms, graph algorithm, sorting algorithm, searching algorithm, bfs, dfs, breadth first search, depth first search, dijkstra's algorithm, a*, a* algorithm, linear search, binary search, bubble sort, insertion sort, merge sort

Id: Uym4-KhP3Lc

Length: 13min 11sec (791 seconds)

Published: Mon Jan 22 2024