Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Learn Merge Sort in 13 minutes đȘ
Das Wichtigste aus dem Video
Tipp auf eine Zeit â das Video springt genau dorthin.
Transkriptautomatisch erstellt · 77 Zeilen
- hey what's going on everybody it's you bro hope you're doing well and in this video we're going to discuss the merge sword algorithm in computer
- science so sit back relax and enjoy the show all right what's going on people merge sword merge sword is
- a divide and conquer algorithm basically what we do is that we will pass an array as an argument to a
- merge sort function this function is going to divide our array in two we have a left array and a right array these will be sub-arrays and we will
- copy the elements over from our original array to our two new sub-arrays and merge sword is a recursive function
- so at the end of merge sort we will call merge sword again and pass in our subarrays that we create and again the merge sort function is
- going to divide our arrays in two by creating a two new sub arrays and then copy the elements over and we will stop when our arrays only
- have a size of one and that's where sorting then merging come in and with the process of merging and sorting we will create a
- second helper function named merge merge will accept a total of three arguments our left subarray our right subarray and the original subarray in which
- these elements came from merge is going to take these elements and put them back into their original array which they came from
- in order and we will do the same thing with the next grouping of arrays until all of these elements are merged back into their original array in which
- they came from all in order now in practice when we do execute this merge sort function instead of tackling all of these
- sub-arrays like one layer at a time we will tackle them by one branch at a time so it's going to look a little something
- like this where we will start with the leftmost branch and then work our way towards the right so i'll speed up the footage and just give you a
- rundown of how this works in practice [Music] [Music]
- you [Music] [Music]
- [Music] [Music]
- [Music] me [Music]
- and that ladies and gentlemen is the merge sort algorithm the merge sort algorithm has a runtime complexity
- of big o of n log n it runs in quasi-linear time along with quick sort and heap sort which we still need to talk about
- so when working with large data sets merge sort is faster than insertion sort selection sort and bubble sort
- but on the other hand the emerge sword algorithm uses more space than a bubble sword selection sword and insertion sort because we need to create
- new subarrays to store elements whereas bubble sort selection sword and insertion sort can sort in place so they use a constant amount of space
- to do their sorting unlike with merge sort now let's move on to the hands-on portion of this video and create a merge sort function in code
- now all right well let's get started we'll need an array to work with make up some numbers make sure that
- they're not in order as well as a for loop to iterate over the elements of our array so currently our array is not in order
- but that's going to change soon let's invoke a merge sort method that we still need to declare this is going to be a recursive method
- and we will pass in an array and each time that we invoke this method we will split our array in half create two sub-arrays and
- then copy the elements over so let's create and declare this method private static void merge sort and we'll need a helper method
- too and we'll name this merge a helper method is just a method that helps another method basically so private static void merge
- and there's going to be three parameters within our merge method int left array
- int right array and int array remember that these are arrays of integers the first thing that we're
- going to do within our merge sort method is that we need to get the length of our array so let's cache that within a local
- variable named length int length equals array.length and we'll need a base case too when do we stop recursion
- if length is less than or equal to one then we shall return and this is our base case basically with
- this merge sort method we're dividing our ray in two each time if the length is one there's no longer a need to divide our array further
- and we'll need to find the middle position of our ray int middle equals length divided by two and we'll create two new sub arrays
- int array left array equals new integer array and the size is middle and we'll create a right array
- integer array right array the size is length minus middle okay now we need to copy the elements of our original array to our left and right
- arrays so we'll need two indices int i equals zero this will be for our left array
- and int j equals zero and this is for our right array then let's create a for loop we don't necessarily need to declare a new
- index here we can just use i so i'm going to add a semicolon our condition is i is less than length then increment
- i by 1 during each iteration so our condition is with an if statement if i is less than
- middle then we will copy an element from our original array to our left array left array at index of i
- equals array at index of i else we will copy that element to our right array
- else right array at index of j remember that this index is for the right array equals array at index of i
- then let's increment j by one okay this is where recursion comes in so outside of this for loop we will call merge sword again
- and pass in our left array so we'll consistently divide our array in half we'll begin by dividing the left array
- then the right array with a separate recursive call so left array then right array and then call merge
- so with merge we have to pass in our left array right array and our original array because we'll put the elements back in order
- left array right array and our original array that we received as an argument so that is it for the
- merge sort function let's work on merge next first thing that we're going to do within the merge method is cache the size of our left array and right
- array within some local variables int left size equals array dot length divided by 2 and right size equals
- array dot length minus left size and then we'll need three indices int i equals zero this is for our original array to keep
- track of the position l will be in charge of our left array and r will be in charge of our right array
- and these will be the indices that we're using okay the next part we're going to check
- the conditions for merging and we can do this with a while loop so our condition is going to be while l
- is less than left size and r is less than right size so basically while there's elements within
- both our left array and right array we will continue adding elements to our original array and we'll need to check to see which
- element is smaller if left array at index of l is less than right array
- at index of r then we will copy the element from our left array to our original array so we're basically comparing the
- number on the left to the right and adding whatever number is smaller back to our original array so array at index of i
- equals left array at index of l then we can increment i increment l
- so if the number on the left is not smaller than the number on the right we have to copy the element in our right array
- to our original array and we can use an else statement else array at index of i equals right array at index
- of our increment i increment r so there's probably going to be one element remaining that we cannot compare to another element because there's only
- one left so let's write a while loop for that condition while l is less than left size
- then we will take array at index of i equals left array at index of l increment i increment l
- then we'll need a another while loop if r is less than right size we will copy the last right element over
- array at index of i equals right array at index of r increment i increment r and that should be it let's run this
- and our array is now sorted in conclusion everybody the merge sort algorithm recursively divides an array in two
- sorts them and then recombines them the merge sort algorithm has a runtime complexity of big o of n log n and a space complexity
- of big o of n so that is the merge sort algorithm if you would like a copy of this code i will post this to the comment section
- down below and well yeah that is the merge sword algorithm in computer science hey you
- yeah i'm talking to you if you learned something new then help me help you in three easy steps by smashing that like button
- drop a comment down below and subscribe if you'd like to become a fellow bro [Music]
- you