Skip to main content
Code Review

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach. The module is called bisect because it uses a basic bisection algorithm to do its work.

 

bisect.bisect_left(a, x, lo=0, hi=len(a)) Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach. The module is called bisect because it uses a basic bisection algorithm to do its work.

 

bisect.bisect_left(a, x, lo=0, hi=len(a)) Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach. The module is called bisect because it uses a basic bisection algorithm to do its work.

bisect.bisect_left(a, x, lo=0, hi=len(a)) Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.

Fix my wrong time analysis
Source Link
Angel Luis Blasco
Angel Luis Blasco
  • 86
  • 3

And now it's time to check performance of available solutions for the list of 20 numbers:

According just to this datacase, I can rank current answersimprovement in my machine with Python 3.8 is (compared to my_sort, from original question):

  • Luapulu takes - 9,4% time
  • Roland Illig takes - 16,4% time
  • My proposal takes -61,7% time, What's a real difference for a list of 20
 

BesidesNote: this is a very scalable solution related to list lengthpart has been edited, due to bisect function takes logarithmic time to search for values in sorted listsafter learning from comments received, and normal searching operations onthe way to make a list takes linear time.complexity analysis (please let me know if I am wrong):

 

To answer Roland comment, I am going to compare best two previous answers, withNº steps required for a list of 40 data (double than before)n elements: \$ n \cdot (\frac n2 \cdot \frac 12 + \frac n2) \$ = \$ n^2 \cdot \frac 34 \$

  • Roland's proposalbisect_left takes 0,031 ms ( 2,92 times more than before)\$ \frac 12 \$ of sorted list length \$ \frac n2 \$
  • My proposal takes 0,01 ms (2,14 times more than before), proving than this solutioninsert in sorted list is more scalable.\$ \frac n2 \$

I hopeSo you neither should use this can be helpfulsolution for sorting large data, as for large numbers it has also a time complexity of \$ \mathcal O(n^2) \$

Thanks all for make me see that my previous time analysis was wrong.

And now it's time to check performance of available solutions:

According to this data, I can rank current answers (compared to my_sort, from original question):

  • Luapulu takes - 9,4% time
  • Roland Illig takes - 16,4% time
  • My proposal takes -61,7% time, What's a real difference

Besides this is a very scalable solution related to list length, due to bisect function takes logarithmic time to search for values in sorted lists, and normal searching operations on a list takes linear time.

 

To answer Roland comment, I am going to compare best two previous answers, with a list of 40 data (double than before):

  • Roland's proposal takes 0,031 ms ( 2,92 times more than before)
  • My proposal takes 0,01 ms (2,14 times more than before), proving than this solution is more scalable.

I hope this can be helpful

And now it's time to check performance of available solutions for the list of 20 numbers:

According just to this case, improvement in my machine with Python 3.8 is (compared to my_sort, from original question):

  • Luapulu takes - 9,4% time
  • Roland Illig takes - 16,4% time
  • My proposal takes -61,7% time, What's a real difference for a list of 20
 

Note: this part has been edited, after learning from comments received, the way to make a complexity analysis (please let me know if I am wrong):

Nº steps required for a list of n elements: \$ n \cdot (\frac n2 \cdot \frac 12 + \frac n2) \$ = \$ n^2 \cdot \frac 34 \$

  • bisect_left takes \$ \frac 12 \$ of sorted list length \$ \frac n2 \$
  • insert in sorted list is \$ \frac n2 \$

So you neither should use this solution for sorting large data, as for large numbers it has also a time complexity of \$ \mathcal O(n^2) \$

Thanks all for make me see that my previous time analysis was wrong.

Add how bisect_left works
Source Link
Angel Luis Blasco
Angel Luis Blasco
  • 86
  • 3

bisect is part of standard lib since Python 2.1:

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach. The module is called bisect because it uses a basic bisection algorithm to do its work.

bisect.bisect_left(a, x, lo=0, hi=len(a)) Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.

And then I checked all answersnow it's time to check performance of available solutions:

According to this data, I can rank current answers (compared to my_sort, from original question),:

And then I checked all answers:

According to this data, I can rank current answers (compared to my_sort from question),

bisect is part of standard lib since Python 2.1:

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach. The module is called bisect because it uses a basic bisection algorithm to do its work.

bisect.bisect_left(a, x, lo=0, hi=len(a)) Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.

And now it's time to check performance of available solutions:

According to this data, I can rank current answers (compared to my_sort, from original question):

Answer Roland's comment
Source Link
Angel Luis Blasco
Angel Luis Blasco
  • 86
  • 3
Source Link
Angel Luis Blasco
Angel Luis Blasco
  • 86
  • 3