Possibly bubble sort algorithm The 2019 Stack Overflow Developer Survey Results Are InHow can I speed up my shell sort?Stable Sort in C#Bubble sort a list of integers for a number of iterationsMerge Sort algorithmExact sort - sorting with few move operationsBubble Sort in Objective-CRobust Bubble Sort in VBAMeasuring the time for the bubble sort algorithmCustom sorting algo / optimized bubble sortBubble and Cocktail sort

How to notate time signature switching consistently every measure

Geography at the pixel level

Why didn't the Event Horizon Telescope team mention Sagittarius A*?

Delete all lines which don't have n characters before delimiter

Button changing it's text & action. Good or terrible?

Loose spokes after only a few rides

What do hard-Brexiteers want with respect to the Irish border?

Why can Shazam fly?

For what reasons would an animal species NOT cross a *horizontal* land bridge?

How to check whether the reindex working or not in Magento?

How technical should a Scrum Master be to effectively remove impediments?

How to save as into a customized destination on macOS?

"as much details as you can remember"

Why do we hear so much about the Trump administration deciding to impose and then remove tariffs?

Does the shape of a die affect the probability of a number being rolled?

Are there any other methods to apply to solving simultaneous equations?

Ubuntu Server install with full GUI

If I score a critical hit on an 18 or higher, what are my chances of getting a critical hit if I roll 3d20?

Interpreting the 2019 New York Reproductive Health Act?

Can we generate random numbers using irrational numbers like π and e?

What is the motivation for a law requiring 2 parties to consent for recording a conversation

How come people say “Would of”?

Reference request: Oldest number theory books with (unsolved) exercises?

Why isn't airport relocation done gradually?



Possibly bubble sort algorithm



The 2019 Stack Overflow Developer Survey Results Are InHow can I speed up my shell sort?Stable Sort in C#Bubble sort a list of integers for a number of iterationsMerge Sort algorithmExact sort - sorting with few move operationsBubble Sort in Objective-CRobust Bubble Sort in VBAMeasuring the time for the bubble sort algorithmCustom sorting algo / optimized bubble sortBubble and Cocktail sort



.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;








4












$begingroup$


I'm trying to figure out what to call this sorting algorithm:






function sort(array) 
array = array.slice();

for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
//swap
[array[i], array[j]] = [array[j], array[i]]




return array;


console.log(sort([8, 4, 5, 2, 3, 7]));





I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(










share|improve this question









New contributor




Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$


















    4












    $begingroup$


    I'm trying to figure out what to call this sorting algorithm:






    function sort(array) 
    array = array.slice();

    for (let i = 0; i < array.length; i++)
    for (let j = 0; j < array.length - 1; j++)
    if (array[j] > array[i])
    //swap
    [array[i], array[j]] = [array[j], array[i]]




    return array;


    console.log(sort([8, 4, 5, 2, 3, 7]));





    I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(










    share|improve this question









    New contributor




    Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$














      4












      4








      4


      1



      $begingroup$


      I'm trying to figure out what to call this sorting algorithm:






      function sort(array) 
      array = array.slice();

      for (let i = 0; i < array.length; i++)
      for (let j = 0; j < array.length - 1; j++)
      if (array[j] > array[i])
      //swap
      [array[i], array[j]] = [array[j], array[i]]




      return array;


      console.log(sort([8, 4, 5, 2, 3, 7]));





      I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(










      share|improve this question









      New contributor




      Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      I'm trying to figure out what to call this sorting algorithm:






      function sort(array) 
      array = array.slice();

      for (let i = 0; i < array.length; i++)
      for (let j = 0; j < array.length - 1; j++)
      if (array[j] > array[i])
      //swap
      [array[i], array[j]] = [array[j], array[i]]




      return array;


      console.log(sort([8, 4, 5, 2, 3, 7]));





      I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(






      function sort(array) 
      array = array.slice();

      for (let i = 0; i < array.length; i++)
      for (let j = 0; j < array.length - 1; j++)
      if (array[j] > array[i])
      //swap
      [array[i], array[j]] = [array[j], array[i]]




      return array;


      console.log(sort([8, 4, 5, 2, 3, 7]));





      function sort(array) 
      array = array.slice();

      for (let i = 0; i < array.length; i++)
      for (let j = 0; j < array.length - 1; j++)
      if (array[j] > array[i])
      //swap
      [array[i], array[j]] = [array[j], array[i]]




      return array;


      console.log(sort([8, 4, 5, 2, 3, 7]));






      javascript algorithm sorting






      share|improve this question









      New contributor




      Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|improve this question









      New contributor




      Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|improve this question




      share|improve this question








      edited Apr 7 at 16:49









      200_success

      131k17157422




      131k17157422






      New contributor




      Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked Apr 7 at 15:46









      Ademola AdegbuyiAdemola Adegbuyi

      1235




      1235




      New contributor




      Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Ademola Adegbuyi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.




















          2 Answers
          2






          active

          oldest

          votes


















          4












          $begingroup$

          To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1 elements.



          Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i] with array[j] > array[j+1], you will get Bubblesort.



          This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if).



          A small improvement would be to add a flag in the i loop which records if any swapping happened at all - the outer for loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)






          share|improve this answer











          $endgroup$








          • 1




            $begingroup$
            So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
            $endgroup$
            – Ademola Adegbuyi
            Apr 7 at 16:36







          • 1




            $begingroup$
            No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
            $endgroup$
            – 200_success
            Apr 7 at 16:53










          • $begingroup$
            @200_success you are absolutely right - about to edit my answer :)
            $endgroup$
            – jvb
            Apr 7 at 17:58










          • $begingroup$
            @200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
            $endgroup$
            – Ilmari Karonen
            Apr 7 at 23:32


















          2












          $begingroup$

          It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.



          The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i will be sorted correctly:



          for (let i = 0; i < array.length; i++) 
          for (let j = 0; j < array.length - 1; j++)
          if (array[j] > array[i])
          [array[i], array[j]] = [array[j], array[i]]


          // Invariant: here array[0] to array[i] will be correctly sorted!



          In particular, this invariant will obviously be true at the end of the first iteration, when i == 0. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1, the whole array will be correctly sorted.




          Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1; the iteration with i == j obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i with a larger one from the tail end of the array, which will still leave array[i] greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i:



          for (let i = 0; i < array.length; i++) 
          for (let j = 0; j < i; j++)
          if (array[j] > array[i])
          [array[i], array[j]] = [array[j], array[i]]


          // Invariant: here array[0] to array[i] will be correctly sorted!



          With this optimization, your algorithm can be recognized as a form of insertion sort.




          It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i] into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:



          for (let i = 1; i < array.length; i++) 
          let j = i, temp = array[i];
          while (j > 0 && array[j - 1] > temp)
          array[j] = array[j - 1];
          j--;

          if (j < i) array[j] = temp;
          // Invariant: here array[0] to array[i] will be correctly sorted!



          By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.



          The if (j < i) part of the code above is not really necessary, since if j == i, assigning temp back to array[i] would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1 instead of let i = 0; the iteration with i == 0 does nothing anyway, so we can safely skip it!






          share|improve this answer









          $endgroup$













            Your Answer





            StackExchange.ifUsing("editor", function ()
            return StackExchange.using("mathjaxEditing", function ()
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            );
            );
            , "mathjax-editing");

            StackExchange.ifUsing("editor", function ()
            StackExchange.using("externalEditor", function ()
            StackExchange.using("snippets", function ()
            StackExchange.snippets.init();
            );
            );
            , "code-snippets");

            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "196"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader:
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            ,
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );






            Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.









            draft saved

            draft discarded


















            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217017%2fpossibly-bubble-sort-algorithm%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            4












            $begingroup$

            To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1 elements.



            Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i] with array[j] > array[j+1], you will get Bubblesort.



            This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if).



            A small improvement would be to add a flag in the i loop which records if any swapping happened at all - the outer for loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)






            share|improve this answer











            $endgroup$








            • 1




              $begingroup$
              So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
              $endgroup$
              – Ademola Adegbuyi
              Apr 7 at 16:36







            • 1




              $begingroup$
              No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
              $endgroup$
              – 200_success
              Apr 7 at 16:53










            • $begingroup$
              @200_success you are absolutely right - about to edit my answer :)
              $endgroup$
              – jvb
              Apr 7 at 17:58










            • $begingroup$
              @200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
              $endgroup$
              – Ilmari Karonen
              Apr 7 at 23:32















            4












            $begingroup$

            To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1 elements.



            Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i] with array[j] > array[j+1], you will get Bubblesort.



            This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if).



            A small improvement would be to add a flag in the i loop which records if any swapping happened at all - the outer for loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)






            share|improve this answer











            $endgroup$








            • 1




              $begingroup$
              So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
              $endgroup$
              – Ademola Adegbuyi
              Apr 7 at 16:36







            • 1




              $begingroup$
              No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
              $endgroup$
              – 200_success
              Apr 7 at 16:53










            • $begingroup$
              @200_success you are absolutely right - about to edit my answer :)
              $endgroup$
              – jvb
              Apr 7 at 17:58










            • $begingroup$
              @200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
              $endgroup$
              – Ilmari Karonen
              Apr 7 at 23:32













            4












            4








            4





            $begingroup$

            To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1 elements.



            Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i] with array[j] > array[j+1], you will get Bubblesort.



            This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if).



            A small improvement would be to add a flag in the i loop which records if any swapping happened at all - the outer for loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)






            share|improve this answer











            $endgroup$



            To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1 elements.



            Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i] with array[j] > array[j+1], you will get Bubblesort.



            This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if).



            A small improvement would be to add a flag in the i loop which records if any swapping happened at all - the outer for loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)







            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Apr 7 at 18:05

























            answered Apr 7 at 16:11









            jvbjvb

            899210




            899210







            • 1




              $begingroup$
              So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
              $endgroup$
              – Ademola Adegbuyi
              Apr 7 at 16:36







            • 1




              $begingroup$
              No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
              $endgroup$
              – 200_success
              Apr 7 at 16:53










            • $begingroup$
              @200_success you are absolutely right - about to edit my answer :)
              $endgroup$
              – jvb
              Apr 7 at 17:58










            • $begingroup$
              @200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
              $endgroup$
              – Ilmari Karonen
              Apr 7 at 23:32












            • 1




              $begingroup$
              So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
              $endgroup$
              – Ademola Adegbuyi
              Apr 7 at 16:36







            • 1




              $begingroup$
              No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
              $endgroup$
              – 200_success
              Apr 7 at 16:53










            • $begingroup$
              @200_success you are absolutely right - about to edit my answer :)
              $endgroup$
              – jvb
              Apr 7 at 17:58










            • $begingroup$
              @200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
              $endgroup$
              – Ilmari Karonen
              Apr 7 at 23:32







            1




            1




            $begingroup$
            So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
            $endgroup$
            – Ademola Adegbuyi
            Apr 7 at 16:36





            $begingroup$
            So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
            $endgroup$
            – Ademola Adegbuyi
            Apr 7 at 16:36





            1




            1




            $begingroup$
            No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
            $endgroup$
            – 200_success
            Apr 7 at 16:53




            $begingroup$
            No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
            $endgroup$
            – 200_success
            Apr 7 at 16:53












            $begingroup$
            @200_success you are absolutely right - about to edit my answer :)
            $endgroup$
            – jvb
            Apr 7 at 17:58




            $begingroup$
            @200_success you are absolutely right - about to edit my answer :)
            $endgroup$
            – jvb
            Apr 7 at 17:58












            $begingroup$
            @200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
            $endgroup$
            – Ilmari Karonen
            Apr 7 at 23:32




            $begingroup$
            @200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
            $endgroup$
            – Ilmari Karonen
            Apr 7 at 23:32













            2












            $begingroup$

            It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.



            The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i will be sorted correctly:



            for (let i = 0; i < array.length; i++) 
            for (let j = 0; j < array.length - 1; j++)
            if (array[j] > array[i])
            [array[i], array[j]] = [array[j], array[i]]


            // Invariant: here array[0] to array[i] will be correctly sorted!



            In particular, this invariant will obviously be true at the end of the first iteration, when i == 0. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1, the whole array will be correctly sorted.




            Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1; the iteration with i == j obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i with a larger one from the tail end of the array, which will still leave array[i] greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i:



            for (let i = 0; i < array.length; i++) 
            for (let j = 0; j < i; j++)
            if (array[j] > array[i])
            [array[i], array[j]] = [array[j], array[i]]


            // Invariant: here array[0] to array[i] will be correctly sorted!



            With this optimization, your algorithm can be recognized as a form of insertion sort.




            It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i] into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:



            for (let i = 1; i < array.length; i++) 
            let j = i, temp = array[i];
            while (j > 0 && array[j - 1] > temp)
            array[j] = array[j - 1];
            j--;

            if (j < i) array[j] = temp;
            // Invariant: here array[0] to array[i] will be correctly sorted!



            By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.



            The if (j < i) part of the code above is not really necessary, since if j == i, assigning temp back to array[i] would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1 instead of let i = 0; the iteration with i == 0 does nothing anyway, so we can safely skip it!






            share|improve this answer









            $endgroup$

















              2












              $begingroup$

              It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.



              The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i will be sorted correctly:



              for (let i = 0; i < array.length; i++) 
              for (let j = 0; j < array.length - 1; j++)
              if (array[j] > array[i])
              [array[i], array[j]] = [array[j], array[i]]


              // Invariant: here array[0] to array[i] will be correctly sorted!



              In particular, this invariant will obviously be true at the end of the first iteration, when i == 0. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1, the whole array will be correctly sorted.




              Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1; the iteration with i == j obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i with a larger one from the tail end of the array, which will still leave array[i] greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i:



              for (let i = 0; i < array.length; i++) 
              for (let j = 0; j < i; j++)
              if (array[j] > array[i])
              [array[i], array[j]] = [array[j], array[i]]


              // Invariant: here array[0] to array[i] will be correctly sorted!



              With this optimization, your algorithm can be recognized as a form of insertion sort.




              It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i] into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:



              for (let i = 1; i < array.length; i++) 
              let j = i, temp = array[i];
              while (j > 0 && array[j - 1] > temp)
              array[j] = array[j - 1];
              j--;

              if (j < i) array[j] = temp;
              // Invariant: here array[0] to array[i] will be correctly sorted!



              By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.



              The if (j < i) part of the code above is not really necessary, since if j == i, assigning temp back to array[i] would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1 instead of let i = 0; the iteration with i == 0 does nothing anyway, so we can safely skip it!






              share|improve this answer









              $endgroup$















                2












                2








                2





                $begingroup$

                It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.



                The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i will be sorted correctly:



                for (let i = 0; i < array.length; i++) 
                for (let j = 0; j < array.length - 1; j++)
                if (array[j] > array[i])
                [array[i], array[j]] = [array[j], array[i]]


                // Invariant: here array[0] to array[i] will be correctly sorted!



                In particular, this invariant will obviously be true at the end of the first iteration, when i == 0. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1, the whole array will be correctly sorted.




                Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1; the iteration with i == j obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i with a larger one from the tail end of the array, which will still leave array[i] greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i:



                for (let i = 0; i < array.length; i++) 
                for (let j = 0; j < i; j++)
                if (array[j] > array[i])
                [array[i], array[j]] = [array[j], array[i]]


                // Invariant: here array[0] to array[i] will be correctly sorted!



                With this optimization, your algorithm can be recognized as a form of insertion sort.




                It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i] into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:



                for (let i = 1; i < array.length; i++) 
                let j = i, temp = array[i];
                while (j > 0 && array[j - 1] > temp)
                array[j] = array[j - 1];
                j--;

                if (j < i) array[j] = temp;
                // Invariant: here array[0] to array[i] will be correctly sorted!



                By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.



                The if (j < i) part of the code above is not really necessary, since if j == i, assigning temp back to array[i] would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1 instead of let i = 0; the iteration with i == 0 does nothing anyway, so we can safely skip it!






                share|improve this answer









                $endgroup$



                It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.



                The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i will be sorted correctly:



                for (let i = 0; i < array.length; i++) 
                for (let j = 0; j < array.length - 1; j++)
                if (array[j] > array[i])
                [array[i], array[j]] = [array[j], array[i]]


                // Invariant: here array[0] to array[i] will be correctly sorted!



                In particular, this invariant will obviously be true at the end of the first iteration, when i == 0. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1, the whole array will be correctly sorted.




                Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1; the iteration with i == j obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i with a larger one from the tail end of the array, which will still leave array[i] greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i:



                for (let i = 0; i < array.length; i++) 
                for (let j = 0; j < i; j++)
                if (array[j] > array[i])
                [array[i], array[j]] = [array[j], array[i]]


                // Invariant: here array[0] to array[i] will be correctly sorted!



                With this optimization, your algorithm can be recognized as a form of insertion sort.




                It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i] into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:



                for (let i = 1; i < array.length; i++) 
                let j = i, temp = array[i];
                while (j > 0 && array[j - 1] > temp)
                array[j] = array[j - 1];
                j--;

                if (j < i) array[j] = temp;
                // Invariant: here array[0] to array[i] will be correctly sorted!



                By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.



                The if (j < i) part of the code above is not really necessary, since if j == i, assigning temp back to array[i] would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1 instead of let i = 0; the iteration with i == 0 does nothing anyway, so we can safely skip it!







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered Apr 7 at 23:28









                Ilmari KaronenIlmari Karonen

                1,865915




                1,865915




















                    Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.









                    draft saved

                    draft discarded


















                    Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.












                    Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.











                    Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.














                    Thanks for contributing an answer to Code Review Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid


                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.

                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217017%2fpossibly-bubble-sort-algorithm%23new-answer', 'question_page');

                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Sum ergo cogito? 1 nng

                    三茅街道4182Guuntc Dn precexpngmageondP