Insert a number in a sorted list and return the list with the number at the correct index











up vote
3
down vote

favorite












I feel like the title is a bit wordy. What I have defined here is a function that takes two parameters:




  • a list that contains valued sorted from smallest to biggest

  • a number to insert at the right index so that the returned list print its values from smallest to biggest


NOTE: Recursion is mandatory



def insert(lst, to_insert):
"""
parameters : lst of type list, that contains values sorted from smallest to largest;
to_insert : represents a value
returns : same list with the to_insert value positioned at the right index
in order for the list to remain sorted from smallest to largest;
"""
if len(lst) == 1:
return
if lst[0] < to_insert and to_insert < lst[1]:
lst[3] = to_insert
return [lst[0]] + [lst[3]] + insert(lst[1:], to_insert)
else:
return [lst[0]] + insert(lst[1:], to_insert)

print(insert([1,2,3,4,5,7,8,9], 6))


The list outputs the following :



[1,2,3,4,5,6,7,8]   #not sure where 9 got left


How do I optimize this function, using only simple functions.










share|improve this question




























    up vote
    3
    down vote

    favorite












    I feel like the title is a bit wordy. What I have defined here is a function that takes two parameters:




    • a list that contains valued sorted from smallest to biggest

    • a number to insert at the right index so that the returned list print its values from smallest to biggest


    NOTE: Recursion is mandatory



    def insert(lst, to_insert):
    """
    parameters : lst of type list, that contains values sorted from smallest to largest;
    to_insert : represents a value
    returns : same list with the to_insert value positioned at the right index
    in order for the list to remain sorted from smallest to largest;
    """
    if len(lst) == 1:
    return
    if lst[0] < to_insert and to_insert < lst[1]:
    lst[3] = to_insert
    return [lst[0]] + [lst[3]] + insert(lst[1:], to_insert)
    else:
    return [lst[0]] + insert(lst[1:], to_insert)

    print(insert([1,2,3,4,5,7,8,9], 6))


    The list outputs the following :



    [1,2,3,4,5,6,7,8]   #not sure where 9 got left


    How do I optimize this function, using only simple functions.










    share|improve this question


























      up vote
      3
      down vote

      favorite









      up vote
      3
      down vote

      favorite











      I feel like the title is a bit wordy. What I have defined here is a function that takes two parameters:




      • a list that contains valued sorted from smallest to biggest

      • a number to insert at the right index so that the returned list print its values from smallest to biggest


      NOTE: Recursion is mandatory



      def insert(lst, to_insert):
      """
      parameters : lst of type list, that contains values sorted from smallest to largest;
      to_insert : represents a value
      returns : same list with the to_insert value positioned at the right index
      in order for the list to remain sorted from smallest to largest;
      """
      if len(lst) == 1:
      return
      if lst[0] < to_insert and to_insert < lst[1]:
      lst[3] = to_insert
      return [lst[0]] + [lst[3]] + insert(lst[1:], to_insert)
      else:
      return [lst[0]] + insert(lst[1:], to_insert)

      print(insert([1,2,3,4,5,7,8,9], 6))


      The list outputs the following :



      [1,2,3,4,5,6,7,8]   #not sure where 9 got left


      How do I optimize this function, using only simple functions.










      share|improve this question















      I feel like the title is a bit wordy. What I have defined here is a function that takes two parameters:




      • a list that contains valued sorted from smallest to biggest

      • a number to insert at the right index so that the returned list print its values from smallest to biggest


      NOTE: Recursion is mandatory



      def insert(lst, to_insert):
      """
      parameters : lst of type list, that contains values sorted from smallest to largest;
      to_insert : represents a value
      returns : same list with the to_insert value positioned at the right index
      in order for the list to remain sorted from smallest to largest;
      """
      if len(lst) == 1:
      return
      if lst[0] < to_insert and to_insert < lst[1]:
      lst[3] = to_insert
      return [lst[0]] + [lst[3]] + insert(lst[1:], to_insert)
      else:
      return [lst[0]] + insert(lst[1:], to_insert)

      print(insert([1,2,3,4,5,7,8,9], 6))


      The list outputs the following :



      [1,2,3,4,5,6,7,8]   #not sure where 9 got left


      How do I optimize this function, using only simple functions.







      python sorting recursion






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Nov 12 at 20:04









      200_success

      128k15149412




      128k15149412










      asked Nov 12 at 16:49









      Mister Tusk

      454




      454






















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          4
          down vote



          accepted










          if len(lst) == 1:
          return


          This is incorrect, as it crops one number off and produces the 9 bug you have seen. Instead, you can do:



          if not lst:
          return [to_insert]


          Similarly, the remaining of the function is overly complicated, and can return false results in some edge cases. You would have problems calling for lst[3] if the list is not of four elements or more, and I believe it's incorrect too when inserting 1 in [2, 3, 4, 5].



          if lst[0] > to_insert:
          return [to_insert] + lst
          return [lst[0]] + insert(lst[1:], to_insert)


          Would be more correct, although not optimal.






          share|improve this answer























          • What does the line return [to_insert] + lst do?
            – Mister Tusk
            Nov 12 at 17:14










          • @MisterTusk It returns the list prepended with the element to_insert. For example if to_insert is 1 and lst is [2, 3, 4], it will return [1, 2, 3, 4].
            – Arthur Havlicek
            Nov 12 at 19:02




















          up vote
          5
          down vote













          Recursion is usually a poor choice in Python. Non-tail recursion is usually a poor choice in any language (and this is non-tail because we apply + to the result before returning it).



          It's better to use the standard bisect module to find (once) the correct index at which to insert. This module provides the bisect() function to locate the correct index, and also the insort() function that calls bisect and then inserts, exactly as we want:



          insert = bisect.insort


          This will insert in place, rather than creating a new list, so not exactly equivalent to the existing code.





          As you say "using only simple functions", let's suppose you can't use the Standard Library (that's a bad assumption in general - Python philosophy is that it "includes batteries" to make your code simpler). Then we can use a similar method to write our own non-recursive version.



          def insert(lst, to_insert):
          """
          parameters : lst: sorted list (smallest to largest)
          to_insert: value to add
          returns : copy of lst with the to_insert value added in sorted position
          """

          # binary search
          left = 0
          right = len(lst)

          while left != right:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid

          # now copy the list, inserting new element
          return lst[:left] + [to_insert] + lst[left:]




          Since the question states (without justification) that "recursion is mandatory", I recommend making the search recursive, but performing the insertion just once:



          #! untested
          def insert(lst, to_insert, left=0, right=None):
          if right is None:
          right = len(lst)

          if left == right:
          return lst[:left] + [to_insert] + lst[left:]

          else:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid
          # move left or right, then
          return insert(lst, to_insert, left, right)


          This is now tail-recursive, at least, and only reallocates the list elements once, rather than every level of recursion.






          share|improve this answer























          • I suppose this is a programming exercise.
            – Arthur Havlicek
            Nov 12 at 17:05






          • 1




            Could be - that said, looking at how they work might be instructive.
            – Toby Speight
            Nov 12 at 17:06











          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
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207488%2finsert-a-number-in-a-sorted-list-and-return-the-list-with-the-number-at-the-corr%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








          up vote
          4
          down vote



          accepted










          if len(lst) == 1:
          return


          This is incorrect, as it crops one number off and produces the 9 bug you have seen. Instead, you can do:



          if not lst:
          return [to_insert]


          Similarly, the remaining of the function is overly complicated, and can return false results in some edge cases. You would have problems calling for lst[3] if the list is not of four elements or more, and I believe it's incorrect too when inserting 1 in [2, 3, 4, 5].



          if lst[0] > to_insert:
          return [to_insert] + lst
          return [lst[0]] + insert(lst[1:], to_insert)


          Would be more correct, although not optimal.






          share|improve this answer























          • What does the line return [to_insert] + lst do?
            – Mister Tusk
            Nov 12 at 17:14










          • @MisterTusk It returns the list prepended with the element to_insert. For example if to_insert is 1 and lst is [2, 3, 4], it will return [1, 2, 3, 4].
            – Arthur Havlicek
            Nov 12 at 19:02

















          up vote
          4
          down vote



          accepted










          if len(lst) == 1:
          return


          This is incorrect, as it crops one number off and produces the 9 bug you have seen. Instead, you can do:



          if not lst:
          return [to_insert]


          Similarly, the remaining of the function is overly complicated, and can return false results in some edge cases. You would have problems calling for lst[3] if the list is not of four elements or more, and I believe it's incorrect too when inserting 1 in [2, 3, 4, 5].



          if lst[0] > to_insert:
          return [to_insert] + lst
          return [lst[0]] + insert(lst[1:], to_insert)


          Would be more correct, although not optimal.






          share|improve this answer























          • What does the line return [to_insert] + lst do?
            – Mister Tusk
            Nov 12 at 17:14










          • @MisterTusk It returns the list prepended with the element to_insert. For example if to_insert is 1 and lst is [2, 3, 4], it will return [1, 2, 3, 4].
            – Arthur Havlicek
            Nov 12 at 19:02















          up vote
          4
          down vote



          accepted







          up vote
          4
          down vote



          accepted






          if len(lst) == 1:
          return


          This is incorrect, as it crops one number off and produces the 9 bug you have seen. Instead, you can do:



          if not lst:
          return [to_insert]


          Similarly, the remaining of the function is overly complicated, and can return false results in some edge cases. You would have problems calling for lst[3] if the list is not of four elements or more, and I believe it's incorrect too when inserting 1 in [2, 3, 4, 5].



          if lst[0] > to_insert:
          return [to_insert] + lst
          return [lst[0]] + insert(lst[1:], to_insert)


          Would be more correct, although not optimal.






          share|improve this answer














          if len(lst) == 1:
          return


          This is incorrect, as it crops one number off and produces the 9 bug you have seen. Instead, you can do:



          if not lst:
          return [to_insert]


          Similarly, the remaining of the function is overly complicated, and can return false results in some edge cases. You would have problems calling for lst[3] if the list is not of four elements or more, and I believe it's incorrect too when inserting 1 in [2, 3, 4, 5].



          if lst[0] > to_insert:
          return [to_insert] + lst
          return [lst[0]] + insert(lst[1:], to_insert)


          Would be more correct, although not optimal.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Nov 12 at 19:04

























          answered Nov 12 at 17:00









          Arthur Havlicek

          3635




          3635












          • What does the line return [to_insert] + lst do?
            – Mister Tusk
            Nov 12 at 17:14










          • @MisterTusk It returns the list prepended with the element to_insert. For example if to_insert is 1 and lst is [2, 3, 4], it will return [1, 2, 3, 4].
            – Arthur Havlicek
            Nov 12 at 19:02




















          • What does the line return [to_insert] + lst do?
            – Mister Tusk
            Nov 12 at 17:14










          • @MisterTusk It returns the list prepended with the element to_insert. For example if to_insert is 1 and lst is [2, 3, 4], it will return [1, 2, 3, 4].
            – Arthur Havlicek
            Nov 12 at 19:02


















          What does the line return [to_insert] + lst do?
          – Mister Tusk
          Nov 12 at 17:14




          What does the line return [to_insert] + lst do?
          – Mister Tusk
          Nov 12 at 17:14












          @MisterTusk It returns the list prepended with the element to_insert. For example if to_insert is 1 and lst is [2, 3, 4], it will return [1, 2, 3, 4].
          – Arthur Havlicek
          Nov 12 at 19:02






          @MisterTusk It returns the list prepended with the element to_insert. For example if to_insert is 1 and lst is [2, 3, 4], it will return [1, 2, 3, 4].
          – Arthur Havlicek
          Nov 12 at 19:02














          up vote
          5
          down vote













          Recursion is usually a poor choice in Python. Non-tail recursion is usually a poor choice in any language (and this is non-tail because we apply + to the result before returning it).



          It's better to use the standard bisect module to find (once) the correct index at which to insert. This module provides the bisect() function to locate the correct index, and also the insort() function that calls bisect and then inserts, exactly as we want:



          insert = bisect.insort


          This will insert in place, rather than creating a new list, so not exactly equivalent to the existing code.





          As you say "using only simple functions", let's suppose you can't use the Standard Library (that's a bad assumption in general - Python philosophy is that it "includes batteries" to make your code simpler). Then we can use a similar method to write our own non-recursive version.



          def insert(lst, to_insert):
          """
          parameters : lst: sorted list (smallest to largest)
          to_insert: value to add
          returns : copy of lst with the to_insert value added in sorted position
          """

          # binary search
          left = 0
          right = len(lst)

          while left != right:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid

          # now copy the list, inserting new element
          return lst[:left] + [to_insert] + lst[left:]




          Since the question states (without justification) that "recursion is mandatory", I recommend making the search recursive, but performing the insertion just once:



          #! untested
          def insert(lst, to_insert, left=0, right=None):
          if right is None:
          right = len(lst)

          if left == right:
          return lst[:left] + [to_insert] + lst[left:]

          else:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid
          # move left or right, then
          return insert(lst, to_insert, left, right)


          This is now tail-recursive, at least, and only reallocates the list elements once, rather than every level of recursion.






          share|improve this answer























          • I suppose this is a programming exercise.
            – Arthur Havlicek
            Nov 12 at 17:05






          • 1




            Could be - that said, looking at how they work might be instructive.
            – Toby Speight
            Nov 12 at 17:06















          up vote
          5
          down vote













          Recursion is usually a poor choice in Python. Non-tail recursion is usually a poor choice in any language (and this is non-tail because we apply + to the result before returning it).



          It's better to use the standard bisect module to find (once) the correct index at which to insert. This module provides the bisect() function to locate the correct index, and also the insort() function that calls bisect and then inserts, exactly as we want:



          insert = bisect.insort


          This will insert in place, rather than creating a new list, so not exactly equivalent to the existing code.





          As you say "using only simple functions", let's suppose you can't use the Standard Library (that's a bad assumption in general - Python philosophy is that it "includes batteries" to make your code simpler). Then we can use a similar method to write our own non-recursive version.



          def insert(lst, to_insert):
          """
          parameters : lst: sorted list (smallest to largest)
          to_insert: value to add
          returns : copy of lst with the to_insert value added in sorted position
          """

          # binary search
          left = 0
          right = len(lst)

          while left != right:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid

          # now copy the list, inserting new element
          return lst[:left] + [to_insert] + lst[left:]




          Since the question states (without justification) that "recursion is mandatory", I recommend making the search recursive, but performing the insertion just once:



          #! untested
          def insert(lst, to_insert, left=0, right=None):
          if right is None:
          right = len(lst)

          if left == right:
          return lst[:left] + [to_insert] + lst[left:]

          else:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid
          # move left or right, then
          return insert(lst, to_insert, left, right)


          This is now tail-recursive, at least, and only reallocates the list elements once, rather than every level of recursion.






          share|improve this answer























          • I suppose this is a programming exercise.
            – Arthur Havlicek
            Nov 12 at 17:05






          • 1




            Could be - that said, looking at how they work might be instructive.
            – Toby Speight
            Nov 12 at 17:06













          up vote
          5
          down vote










          up vote
          5
          down vote









          Recursion is usually a poor choice in Python. Non-tail recursion is usually a poor choice in any language (and this is non-tail because we apply + to the result before returning it).



          It's better to use the standard bisect module to find (once) the correct index at which to insert. This module provides the bisect() function to locate the correct index, and also the insort() function that calls bisect and then inserts, exactly as we want:



          insert = bisect.insort


          This will insert in place, rather than creating a new list, so not exactly equivalent to the existing code.





          As you say "using only simple functions", let's suppose you can't use the Standard Library (that's a bad assumption in general - Python philosophy is that it "includes batteries" to make your code simpler). Then we can use a similar method to write our own non-recursive version.



          def insert(lst, to_insert):
          """
          parameters : lst: sorted list (smallest to largest)
          to_insert: value to add
          returns : copy of lst with the to_insert value added in sorted position
          """

          # binary search
          left = 0
          right = len(lst)

          while left != right:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid

          # now copy the list, inserting new element
          return lst[:left] + [to_insert] + lst[left:]




          Since the question states (without justification) that "recursion is mandatory", I recommend making the search recursive, but performing the insertion just once:



          #! untested
          def insert(lst, to_insert, left=0, right=None):
          if right is None:
          right = len(lst)

          if left == right:
          return lst[:left] + [to_insert] + lst[left:]

          else:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid
          # move left or right, then
          return insert(lst, to_insert, left, right)


          This is now tail-recursive, at least, and only reallocates the list elements once, rather than every level of recursion.






          share|improve this answer














          Recursion is usually a poor choice in Python. Non-tail recursion is usually a poor choice in any language (and this is non-tail because we apply + to the result before returning it).



          It's better to use the standard bisect module to find (once) the correct index at which to insert. This module provides the bisect() function to locate the correct index, and also the insort() function that calls bisect and then inserts, exactly as we want:



          insert = bisect.insort


          This will insert in place, rather than creating a new list, so not exactly equivalent to the existing code.





          As you say "using only simple functions", let's suppose you can't use the Standard Library (that's a bad assumption in general - Python philosophy is that it "includes batteries" to make your code simpler). Then we can use a similar method to write our own non-recursive version.



          def insert(lst, to_insert):
          """
          parameters : lst: sorted list (smallest to largest)
          to_insert: value to add
          returns : copy of lst with the to_insert value added in sorted position
          """

          # binary search
          left = 0
          right = len(lst)

          while left != right:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid

          # now copy the list, inserting new element
          return lst[:left] + [to_insert] + lst[left:]




          Since the question states (without justification) that "recursion is mandatory", I recommend making the search recursive, but performing the insertion just once:



          #! untested
          def insert(lst, to_insert, left=0, right=None):
          if right is None:
          right = len(lst)

          if left == right:
          return lst[:left] + [to_insert] + lst[left:]

          else:
          mid = left + (right-left) // 2
          if lst[mid] == to_insert:
          left = right = mid
          elif lst[mid] < to_insert:
          left = mid + 1
          else:
          right = mid
          # move left or right, then
          return insert(lst, to_insert, left, right)


          This is now tail-recursive, at least, and only reallocates the list elements once, rather than every level of recursion.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Nov 12 at 19:31

























          answered Nov 12 at 16:56









          Toby Speight

          23.3k639111




          23.3k639111












          • I suppose this is a programming exercise.
            – Arthur Havlicek
            Nov 12 at 17:05






          • 1




            Could be - that said, looking at how they work might be instructive.
            – Toby Speight
            Nov 12 at 17:06


















          • I suppose this is a programming exercise.
            – Arthur Havlicek
            Nov 12 at 17:05






          • 1




            Could be - that said, looking at how they work might be instructive.
            – Toby Speight
            Nov 12 at 17:06
















          I suppose this is a programming exercise.
          – Arthur Havlicek
          Nov 12 at 17:05




          I suppose this is a programming exercise.
          – Arthur Havlicek
          Nov 12 at 17:05




          1




          1




          Could be - that said, looking at how they work might be instructive.
          – Toby Speight
          Nov 12 at 17:06




          Could be - that said, looking at how they work might be instructive.
          – Toby Speight
          Nov 12 at 17:06


















          draft saved

          draft discarded




















































          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.





          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


          Please pay close attention to the following guidance:


          • 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.


          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%2f207488%2finsert-a-number-in-a-sorted-list-and-return-the-list-with-the-number-at-the-corr%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

          Guess what letter conforming each word

          Port of Spain

          Run scheduled task as local user group (not BUILTIN)