Bubble Sort Algorithm Lecture

in this video we take a look at how to implement the bubble sort [Music] so for the exam you need to understand the main steps the bubble sort and any prerequisites of it you need to be able to apply the algorithm to a data set you go to identify the algorithm if provided with code you should be able to read and trace the algorithm and also write the code for a bubble sort using pseudocode or high level language of your choice a bubble sort orders an unordered list of items by comparing each item with the next one and swapping the items if they're out of order the algorithm is finished when no more swaps can be made in effect it bubbles the largest or smallest item up to the end of the list the bubble saw is the most inefficient sorting algorithm but very easy to implement so it's a popular choice for very small data sets it's ideal for situations where a simple easy to program sorting algorithm is required here's an illustration to help you visualize a bubble saw here's some pseudo code we start by initializing a couple of variables with their starting states n this variable is used to track how far through the data set we should check for items to swap on each iteration we start by setting it to the length of the entire data set swapped this boolean value is used to indicate whether a swap has taken place each time we go around the inner for loop we start by setting it to true so we'll enter the main while loop at least once to check for unsorted items we then enter a while loop which will continue to execute while the following two conditions are met n is greater than zero and swapped is equal to true in other words this loop will execute until all the items are sorted each time around the while loop assumes there are no items that need to be swapped until we prove otherwise so we set the swapped variable to false now say the length of the data set returned by items.length is 10. most arrays or lists are 0 indexed that means we want to check indexes 0 through 9. so we start by setting n to n minus 1. doing this ensures the entire dataset we checked the first time around four items to swap this value would decrement by one each time around the outer while loop the sorted items will gradually bubble up to the end or top of the dataset so there'll be fewer items to check through each time the program now reaches a nested in a for loop for each pass through the data set represented by the outer while loop we to start at the beginning and work through to the penultimate item of the unsorted data set represented by n minus one in other words we need to work through the current subset of items that still need to be checked and sorted at any point join us in a for loop if we discover that the item at the current location in the data set is greater than the next item in the data set we know they must be out of order in this case we've performed two actions first we need to swap the two items over this has been simplified to a single line in pseudocode here and secondly we need to set the swapped variable to true so when we next check the outer while loop we know we're still in the process of sorting the data set we continue through the data set moving the items up as far as it needs to go until it's in the correct place this process is repeated as many times as necessary until we discover the entire dataset has been sorted once again this is the bare bones of the algorithm in its current form it doesn't have a data set to sort yet it doesn't inform the user if the data set has been sorted successfully and the swap line still needs to be fleshed out we need to implement all of this in our chosen high-level programming language here is some syntactically correct python code that demonstrates the bubble sort algorithm in practice we've added a hard-coded list called items which contains five american states this initial list is deliberately unsorted we've also added a line of code that outputs the contents of the data set once it's been sorted just so we can prove that it's worked we start by initializing the variables n equals length of items that's 5 and swapped equals true we check if we need to enter the while loop n is greater than 0 is true and swapped equals true is true as both parts are true we enter the while loop we now set swap to false and we decrement n by one we enter the inner nested for loop for indexing range naught to n so taking the current value of n this reads as range naught to four in python this means values naught to four but not including four itself effectively this means the for loop will execute four times we now compare the item at items index with the item at items index plus one we're essentially asking the question is the value of items index greater than the value of items index plus one well item zero is florida an item zero plus one is georgia and if florida is greater than georgia is false so these items do not need swapping around they're already in order the for loop increments its internal index from zero to one and we enter the for loop again this time items one is georgia and items one plus one is delaware if georgia is greater than delaware now this is true these items are in the wrong order so they need to be swapped so we enter the if statement the actual swap is performed as a three-stage process in python we copy the value currently held in items index that's georgia and place it into a temporary variable we replace the value of the item in items index with the value of the item currently held in items index plus one that's delaware and now we take the value stored out into our temporary variable that was georgia and copy into items in x plus one we've now swapped the two items over before we exit the if statement we set the boolean variable swap to true to indicate that a swap has take place the for loop increments and its internal index value from 1 to 2 and we enter the for loop again once again we compare the items at items index with the item items index plus one so we're comparing georgia to alabama and saying is georgia greater than alabama well it is these items are in the wrong order we'll need to swap them again so we enter the if statement we follow the same through stages as we did before for the swap and we're currently swapping the contents of georgia with alabama we also set the swap value to true again now technically speaking this doesn't have any effect because it's already true but it still happens the for loop increments its internal index value from two to three and we enter the for loop again once again we compare the item at index with the item index plus one so now we're comparing the item uh at item three that's georgia with three plus one that's california if georgia is greater than california well that's true so these items are in the wrong order and they need to be swapped we enter the if statement again we follow the same three stage process we're now swapping the contents of georgia with california again swap is set to true which has no effect because it's already true georgia has successfully bubbled up to the end of the list and is now in the correct location the for loop increments its index from three to four and we discover when out outside the required range we're done executing the inner for loop for now and fall back to the outer while loop we check if we need to enter the while loop once more n is greater than zero still true swapped equals true is true we've made a swap at least once during the last trip through the while loop as both parts are true we enter the while loop again we now set swap back to force once more remember each time around the outer while loop we're going to assume there's nothing that needs to be swapped until we prove otherwise we decrement m by one we do this for efficiency when we hit the inner for loop we don't need to check the whole data set as we know the items that we're currently showing in green are already in their correct place we enter our inner nested for loop for index and range naught to n so taking the current value of n this reads as range naught to three so in python that means zero to three but not including three effectively meaning the inner for loop will now execute three times last time i executed four times now that you should be getting the hang of this algorithm we'll streamline our explanations so once again we ask is the value of items index greater than the value of items index plus one is florida greater than delaware what it is these items are the wrong order so we enter the if statement to swap them we swap florida and delaware over using the temporary variable and we also set the boolean variable swap to true to indicate that a swap has taken place the for loop increments its internal value from 0 to 1 and we enter the for loop again again we ask is the item in item index greater than the item in itunes index plus one is florida greater than alabama it is so these items are the wrong order so we enter the if statement to swap them we swap florida and alabama over using our temporary variable the for loop increments its internal index from 1 to 2 and we enter the for loop again we ask the question again and this time we find that florida is greater than california so these items are in the wrong order so we enter the if statement to swap them we swap florida and california over using the temp variable and florida has successfully bubbled up to the end of the list and is now in the correct location the for loop increments its internal value from two to three we discover when out outside the required range we're done executing this in a for loop for now and fall back to our outer while loop we check if we need to enter the while loop again n is greater than zero is still true and swapped equals true is true as we made a swap at least once during our last trip through the while loop as both parts are true we enter the while loop again as before we start the while loop by setting swap back to false and we decrement m by one remember we're doing this for efficiency when we hit the inner for loop we don't need to check the whole data set both the items in green now are in the correct place we enter the inner nested for loop for index and range naught to n so that's zero to two basically meaning we're going to run this inner for loop only twice this time you should be pretty comfortable with the algorithm by this point so delaware and alabama are in the wrong order so we enter the if statement and swap them remember we also set swap to true to indicate a swap's occurred the for loop increments this eternal index from 0 to 1 and we enter the for loop again delaware and california are in the wrong order so we enter the if statement and swap them delaware has now successfully bubbled up to the end of the list and is now in the correct location the for loop increments its internal index value from one to two we're outside the range so we're done executing the inner for loop again and once more fall back to our outer for loop we check if we need to enter the while loop n is greater than zero that's still true because n is two swapped is true as we did make a swap during our last trip around the while loop so both parts are true we enter the while loop one more time as before we start by setting swapped back to false and we decrement m by one we enter the in a nested for loop and this time we're just going to execute the for loop once this in a for loop is becoming slightly more efficient each time as more the list is being sorted the items we're comparing is alabama and california they're in the correct order so we can skip the code inside the if statement for loop increments its index from zero to one we discover we're outside the required range we're already done with executing the in a for loop and once again we fall back to the outer for loop we check if we need to enter the while loop n is greater than zero is still true swapped equals true is now false as no swaps were made during our last trip through the while loop the while loop requires both conditions to be true so we're now done with the while loop and the data set is sorted the algorithm is complete we finish off by printing out the contents of the sorted list to the user just to prove that it's worked so let's consider a few final thoughts as of our previous videos what presented you here is not the single correct version of a bubble sort it's simply our implementation it's quite possible you'll come across slight variations in textbooks exam papers and other videos let's consider a few possible alterations to the original pseudocode that we presented here at the start of the video in this version we've replaced the outer while loop with a for loop we've also removed any reference to setting updating or tracking of a swatch variable this is a much less efficient than our previous version as it will perform the maximum number of passes through the data set and check all the items regardless of how sorted the data already is however it's still a bubble sort in our pseudo code we assume the data set is implemented using a zero indexed array or list however you may be programming a language that supports a data set or structure that doesn't start at a zero index for the first element and instead starts at one they've also been attempts to improve the efficiency of the bubble saw including the reverse in the direction of the algorithm after each iteration this is known as a cocktail sort having watched this video you should be able to answer following key questions can you successfully implement a bubble sort using a high level programming language your choice and do you understand how a bubble sort works and can you trace its code in the exam we know that getting to grips with data structures and all the algorithms associated with them is a very tricky area of the course and so we've produced a book called essential algorithms for a level computer science that's available on amazon it covers all the data structures you need to know about along with the algorithms you need to perform on them and it covers all the exam boards we overview each data structure discussing its typical applications and the operations you can perform in it we provide a qr code that jumps off to a useful page of additional resources we then take each data structure and the algorithms you need to perform and present them first in simple structured english then in a diagrammatic format then in pseudocode and finally we present you with fully coded algorithms which you need to cover on the data structures in both python and vb so you can actually code them up and practice them yourselves you

in this video we take a look at how to implement the bubble sort [Music] so for the exam you need to understand the main steps the bubble sort and any prerequisites of it you need to be able to apply the algorithm to a data set you go to identify the algorithm if provided with code you should be able to read and trace the algorithm and also write the code for a bubble sort using pseudocode or high level language of your choice a bubble sort orders an unordered list of items by comparing each item with the next one and swapping the items if they&#39;re out of order the algorithm is finished when no more swaps can be made in effect it bubbles the largest or smallest item up to the end of the list the bubble saw is the most inefficient sorting algorithm but very easy to implement so it&#39;s a popular choice for very small data sets it&#39;s ideal for situations where a simple easy to program sorting algorithm is required here&#39;s an illustration to help you visualize a bubble saw here&#39;s some pseudo code we start by initializing a couple of variables with their starting states n this variable is used to track how far through the data set we should check for items to swap on each iteration we start by setting it to the length of the entire data set swapped this boolean value is used to indicate whether a swap has taken place each time we go around the inner for loop we start by setting it to true so we&#39;ll enter the main while loop at least once to check for unsorted items we then enter a while loop which will continue to execute while the following two conditions are met n is greater than zero and swapped is equal to true in other words this loop will execute until all the items are sorted each time around the while loop assumes there are no items that need to be swapped until we prove otherwise so we set the swapped variable to false now say the length of the data set returned by items.length is 10. most arrays or lists are 0 indexed that means we want to check indexes 0 through 9. so we start by setting n to n minus 1. doing this ensures the entire dataset we checked the first time around four items to swap this value would decrement by one each time around the outer while loop the sorted items will gradually bubble up to the end or top of the dataset so there&#39;ll be fewer items to check through each time the program now reaches a nested in a for loop for each pass through the data set represented by the outer while loop we to start at the beginning and work through to the penultimate item of the unsorted data set represented by n minus one in other words we need to work through the current subset of items that still need to be checked and sorted at any point join us in a for loop if we discover that the item at the current location in the data set is greater than the next item in the data set we know they must be out of order in this case we&#39;ve performed two actions first we need to swap the two items over this has been simplified to a single line in pseudocode here and secondly we need to set the swapped variable to true so when we next check the outer while loop we know we&#39;re still in the process of sorting the data set we continue through the data set moving the items up as far as it needs to go until it&#39;s in the correct place this process is repeated as many times as necessary until we discover the entire dataset has been sorted once again this is the bare bones of the algorithm in its current form it doesn&#39;t have a data set to sort yet it doesn&#39;t inform the user if the data set has been sorted successfully and the swap line still needs to be fleshed out we need to implement all of this in our chosen high-level programming language here is some syntactically correct python code that demonstrates the bubble sort algorithm in practice we&#39;ve added a hard-coded list called items which contains five american states this initial list is deliberately unsorted we&#39;ve also added a line of code that outputs the contents of the data set once it&#39;s been sorted just so we can prove that it&#39;s worked we start by initializing the variables n equals length of items that&#39;s 5 and swapped equals true we check if we need to enter the while loop n is greater than 0 is true and swapped equals true is true as both parts are true we enter the while loop we now set swap to false and we decrement n by one we enter the inner nested for loop for indexing range naught to n so taking the current value of n this reads as range naught to four in python this means values naught to four but not including four itself effectively this means the for loop will execute four times we now compare the item at items index with the item at items index plus one we&#39;re essentially asking the question is the value of items index greater than the value of items index plus one well item zero is florida an item zero plus one is georgia and if florida is greater than georgia is false so these items do not need swapping around they&#39;re already in order the for loop increments its internal index from zero to one and we enter the for loop again this time items one is georgia and items one plus one is delaware if georgia is greater than delaware now this is true these items are in the wrong order so they need to be swapped so we enter the if statement the actual swap is performed as a three-stage process in python we copy the value currently held in items index that&#39;s georgia and place it into a temporary variable we replace the value of the item in items index with the value of the item currently held in items index plus one that&#39;s delaware and now we take the value stored out into our temporary variable that was georgia and copy into items in x plus one we&#39;ve now swapped the two items over before we exit the if statement we set the boolean variable swap to true to indicate that a swap has take place the for loop increments and its internal index value from 1 to 2 and we enter the for loop again once again we compare the items at items index with the item items index plus one so we&#39;re comparing georgia to alabama and saying is georgia greater than alabama well it is these items are in the wrong order we&#39;ll need to swap them again so we enter the if statement we follow the same through stages as we did before for the swap and we&#39;re currently swapping the contents of georgia with alabama we also set the swap value to true again now technically speaking this doesn&#39;t have any effect because it&#39;s already true but it still happens the for loop increments its internal index value from two to three and we enter the for loop again once again we compare the item at index with the item index plus one so now we&#39;re comparing the item uh at item three that&#39;s georgia with three plus one that&#39;s california if georgia is greater than california well that&#39;s true so these items are in the wrong order and they need to be swapped we enter the if statement again we follow the same three stage process we&#39;re now swapping the contents of georgia with california again swap is set to true which has no effect because it&#39;s already true georgia has successfully bubbled up to the end of the list and is now in the correct location the for loop increments its index from three to four and we discover when out outside the required range we&#39;re done executing the inner for loop for now and fall back to the outer while loop we check if we need to enter the while loop once more n is greater than zero still true swapped equals true is true we&#39;ve made a swap at least once during the last trip through the while loop as both parts are true we enter the while loop again we now set swap back to force once more remember each time around the outer while loop we&#39;re going to assume there&#39;s nothing that needs to be swapped until we prove otherwise we decrement m by one we do this for efficiency when we hit the inner for loop we don&#39;t need to check the whole data set as we know the items that we&#39;re currently showing in green are already in their correct place we enter our inner nested for loop for index and range naught to n so taking the current value of n this reads as range naught to three so in python that means zero to three but not including three effectively meaning the inner for loop will now execute three times last time i executed four times now that you should be getting the hang of this algorithm we&#39;ll streamline our explanations so once again we ask is the value of items index greater than the value of items index plus one is florida greater than delaware what it is these items are the wrong order so we enter the if statement to swap them we swap florida and delaware over using the temporary variable and we also set the boolean variable swap to true to indicate that a swap has taken place the for loop increments its internal value from 0 to 1 and we enter the for loop again again we ask is the item in item index greater than the item in itunes index plus one is florida greater than alabama it is so these items are the wrong order so we enter the if statement to swap them we swap florida and alabama over using our temporary variable the for loop increments its internal index from 1 to 2 and we enter the for loop again we ask the question again and this time we find that florida is greater than california so these items are in the wrong order so we enter the if statement to swap them we swap florida and california over using the temp variable and florida has successfully bubbled up to the end of the list and is now in the correct location the for loop increments its internal value from two to three we discover when out outside the required range we&#39;re done executing this in a for loop for now and fall back to our outer while loop we check if we need to enter the while loop again n is greater than zero is still true and swapped equals true is true as we made a swap at least once during our last trip through the while loop as both parts are true we enter the while loop again as before we start the while loop by setting swap back to false and we decrement m by one remember we&#39;re doing this for efficiency when we hit the inner for loop we don&#39;t need to check the whole data set both the items in green now are in the correct place we enter the inner nested for loop for index and range naught to n so that&#39;s zero to two basically meaning we&#39;re going to run this inner for loop only twice this time you should be pretty comfortable with the algorithm by this point so delaware and alabama are in the wrong order so we enter the if statement and swap them remember we also set swap to true to indicate a swap&#39;s occurred the for loop increments this eternal index from 0 to 1 and we enter the for loop again delaware and california are in the wrong order so we enter the if statement and swap them delaware has now successfully bubbled up to the end of the list and is now in the correct location the for loop increments its internal index value from one to two we&#39;re outside the range so we&#39;re done executing the inner for loop again and once more fall back to our outer for loop we check if we need to enter the while loop n is greater than zero that&#39;s still true because n is two swapped is true as we did make a swap during our last trip around the while loop so both parts are true we enter the while loop one more time as before we start by setting swapped back to false and we decrement m by one we enter the in a nested for loop and this time we&#39;re just going to execute the for loop once this in a for loop is becoming slightly more efficient each time as more the list is being sorted the items we&#39;re comparing is alabama and california they&#39;re in the correct order so we can skip the code inside the if statement for loop increments its index from zero to one we discover we&#39;re outside the required range we&#39;re already done with executing the in a for loop and once again we fall back to the outer for loop we check if we need to enter the while loop n is greater than zero is still true swapped equals true is now false as no swaps were made during our last trip through the while loop the while loop requires both conditions to be true so we&#39;re now done with the while loop and the data set is sorted the algorithm is complete we finish off by printing out the contents of the sorted list to the user just to prove that it&#39;s worked so let&#39;s consider a few final thoughts as of our previous videos what presented you here is not the single correct version of a bubble sort it&#39;s simply our implementation it&#39;s quite possible you&#39;ll come across slight variations in textbooks exam papers and other videos let&#39;s consider a few possible alterations to the original pseudocode that we presented here at the start of the video in this version we&#39;ve replaced the outer while loop with a for loop we&#39;ve also removed any reference to setting updating or tracking of a swatch variable this is a much less efficient than our previous version as it will perform the maximum number of passes through the data set and check all the items regardless of how sorted the data already is however it&#39;s still a bubble sort in our pseudo code we assume the data set is implemented using a zero indexed array or list however you may be programming a language that supports a data set or structure that doesn&#39;t start at a zero index for the first element and instead starts at one they&#39;ve also been attempts to improve the efficiency of the bubble saw including the reverse in the direction of the algorithm after each iteration this is known as a cocktail sort having watched this video you should be able to answer following key questions can you successfully implement a bubble sort using a high level programming language your choice and do you understand how a bubble sort works and can you trace its code in the exam we know that getting to grips with data structures and all the algorithms associated with them is a very tricky area of the course and so we&#39;ve produced a book called essential algorithms for a level computer science that&#39;s available on amazon it covers all the data structures you need to know about along with the algorithms you need to perform on them and it covers all the exam boards we overview each data structure discussing its typical applications and the operations you can perform in it we provide a qr code that jumps off to a useful page of additional resources we then take each data structure and the algorithms you need to perform and present them first in simple structured english then in a diagrammatic format then in pseudocode and finally we present you with fully coded algorithms which you need to cover on the data structures in both python and vb so you can actually code them up and practice them yourselves you

Transcript for:Bubble Sort Algorithm Lecture

Transcript for:
Bubble Sort Algorithm Lecture