What algorithm does this sorting method use?

Question

import sys
final_set = []
init_set = []
for i in range(1,len(sys.argv)):
    init_set.append(sys.argv[i])
for i in range(len(init_set)):
    cur_min = min(init_set)
    final_set.append(cur_min)
    init_set.remove(cur_min)
print final_set

This fairly basic sorting algorithm must already have a name. Can anyone identify it and its time complexity?

Note that those are lists, not sets.

jamylak
– jamylak

2012-05-27 05:42:05 +00:00
Commented May 27, 2012 at 5:42 — jamylak
– jamylak, Commented May 27, 2012 at 5:42
Yeah, I wasn't really thinking when I named them.

user1419802
– user1419802

2012-05-27 05:46:06 +00:00
Commented May 27, 2012 at 5:46 — user1419802
– user1419802, Commented May 27, 2012 at 5:46

lvc · Accepted Answer · 2012-05-27 05:40:22Z

5

This appears to be a Selection sort, which has quadratic complexity.

answered May 27, 2012 at 5:40

lvc

35.3k10 gold badges76 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

user1419802 Over a year ago

On all counts of operations that I performed the operation count was less than n^2. Why is this? Is n^2/2 considered the same thing as n^2 in algorithmic complexity?

jamylak Over a year ago

@user1419802 Checking the minimum has to go through each element.

user1419802 Over a year ago

Since one item of the list is removed each time the set becomes one smaller meaning that the first iteration takes n operations, the next takes n-1 operations and so on. That would presumably be less than n^2.

lvc Over a year ago

@user1419802 The mathematical definition of big-o complexity doesn't consider an exact count of operations, but rather how the number of operations grows. So, to estimate it empirically, you need to look at the operation count across several (preferably as many as practical) ns. But yes, an algorithm which always has n^2/2 operations is order n^2.

lvc Over a year ago

@user1419802 likewise, an algorithm that always has exactly twelve operations is called O(1) rather than O(12). Multiplying or dividing by a constant factor doesn't change the complexity (which is something you can prove if you decide to look at the math behind it), so we tend to just leave those out.

|

Collectives™ on Stack Overflow

What algorithm does this sorting method use?

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related