By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
464,553 Members | 851 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 464,553 IT Pros & Developers. It's quick & easy.

Tell me, did I find a new sort type and is it more optimal than quick sort?

P: 1
Expand|Select|Wrap|Line Numbers
  1. Input:
  2.  
  3. list = [23, 12, 65, 34, 91, 43]
  4.  
  5. print(list)
  6.  
  7. for i in range(len(list)):
  8.     min_index = list.index(min(list[:len(list)-i]))
  9.     list.append(list[min_index])
  10.     list.pop(min_index)
  11.  
  12. print(list)
  13.  
  14. Output:
  15.  
  16. [23, 12, 65, 34, 91, 43]
  17. [12, 23, 34, 43, 65, 91]
1 Week Ago #1
Share this Question
Share on Google+
5 Replies

dev7060
Expert 100+
P: 336
Correct answer by Rabbit

Expand|Select|Wrap|Line Numbers
  1. print(list)
  2.  
  3. for i in range(len(list)):
  4.     min_index = list.index(min(list[:len(list)-i]))
  5.     list.append(list[min_index])
  6.     list.pop(min_index)
  7.  
  8. print(list)
D̶e̶d̶u̶c̶t̶i̶o̶n̶ ̶i̶n̶s̶i̶d̶e̶ ̶t̶h̶e̶ ̶f̶o̶r̶ ̶b̶l̶o̶c̶k̶,̶ ̶O̶(̶n̶^̶2̶)̶ ̶+̶ ̶O̶(̶1̶)̶ ̶+̶ ̶O̶(̶n̶)̶ ̶=̶ ̶ ̶O̶(̶n̶^̶2̶)̶

H̶e̶n̶c̶e̶ ̶f̶o̶r̶ ̶t̶h̶e̶ ̶c̶o̶d̶e̶,̶ ̶O̶(̶n̶^̶3̶)

A̶n̶d̶ ̶q̶u̶i̶c̶k̶s̶o̶r̶t̶ ̶i̶s̶ ̶O̶(̶n̶^̶2̶)̶ ̶i̶n̶ ̶t̶h̶e̶ ̶w̶o̶r̶s̶t̶-̶c̶a̶s̶e̶ ̶s̶c̶e̶n̶a̶r̶i̶o̶,̶ ̶b̶e̶t̶t̶e̶r̶.̶
1 Week Ago #2

Rabbit
Expert Mod 10K+
P: 12,441
That is selection sort, O(n^2)
1 Week Ago #3

dev7060
Expert 100+
P: 336
Correct answer by Rabbit

That is selection sort, O(n^2)
I̶n̶ ̶s̶e̶l̶e̶c̶t̶i̶o̶n̶ ̶s̶o̶r̶t̶,̶ ̶t̶h̶e̶ ̶t̶a̶s̶k̶ ̶o̶f̶ ̶f̶i̶n̶d̶i̶n̶g̶ ̶t̶h̶e̶ ̶m̶i̶n̶i̶m̶u̶m̶ ̶v̶a̶l̶u̶e̶ ̶a̶n̶d̶ ̶i̶t̶s̶ ̶i̶n̶d̶e̶x̶ ̶a̶r̶e̶ ̶h̶a̶n̶d̶l̶e̶d̶ ̶i̶n̶ ̶a̶ ̶s̶i̶n̶g̶l̶e̶ ̶b̶l̶o̶c̶k̶ ̶h̶e̶n̶c̶e̶ ̶t̶h̶i̶s̶ ̶p̶a̶r̶t̶ ̶d̶e̶d̶u̶c̶e̶s̶ ̶t̶o̶ ̶o̶n̶l̶y̶ ̶O̶(̶n̶)̶ ̶c̶o̶m̶p̶l̶e̶x̶i̶t̶y̶.̶ ̶T̶h̶e̶ ̶a̶p̶p̶r̶o̶a̶c̶h̶ ̶b̶y̶ ̶t̶h̶e̶ ̶O̶P̶ ̶i̶s̶ ̶t̶h̶e̶ ̶s̶a̶m̶e̶,̶ ̶b̶u̶t̶ ̶t̶h̶e̶ ̶f̶a̶c̶t̶ ̶t̶h̶a̶t̶ ̶a̶ ̶s̶e̶p̶a̶r̶a̶t̶e̶ ̶n̶e̶s̶t̶e̶d̶ ̶c̶a̶l̶l̶ ̶i̶s̶ ̶m̶a̶d̶e̶ ̶t̶o̶ ̶m̶i̶n̶(̶)̶ ̶i̶n̶s̶i̶d̶e̶ ̶i̶n̶d̶e̶x̶(̶)̶ ̶m̶a̶k̶e̶s̶ ̶t̶h̶e̶ ̶c̶o̶m̶p̶l̶e̶x̶i̶t̶y̶ ̶o̶f̶ ̶t̶h̶e̶ ̶s̶t̶a̶t̶e̶m̶e̶n̶t̶ ̶O̶(̶n̶^̶2̶)̶ ̶s̶i̶n̶c̶e̶ ̶b̶o̶t̶h̶ ̶m̶i̶n̶(̶)̶ ̶a̶n̶d̶ ̶i̶n̶d̶e̶x̶(̶)̶ ̶h̶a̶s̶ ̶t̶h̶e̶ ̶c̶o̶m̶p̶l̶e̶x̶i̶t̶y̶ ̶o̶f̶ ̶O̶(̶n̶)̶ ̶e̶a̶c̶h̶.̶ ̶A̶n̶d̶ ̶s̶i̶n̶c̶e̶ ̶O̶(̶n̶^̶2̶)̶ ̶i̶s̶ ̶p̶r̶e̶s̶e̶n̶t̶ ̶i̶n̶s̶i̶d̶e̶ ̶t̶h̶e̶ ̶b̶o̶d̶y̶ ̶o̶f̶ ̶f̶o̶r̶,̶ ̶t̶h̶e̶ ̶d̶e̶d̶u̶c̶e̶d̶ ̶c̶o̶m̶p̶l̶e̶x̶i̶t̶y̶ ̶w̶o̶u̶l̶d̶ ̶b̶e̶ ̶O̶(̶n̶^̶3̶)̶ ̶w̶h̶i̶c̶h̶ ̶k̶i̶n̶d̶ ̶o̶f̶ ̶a̶l̶t̶e̶r̶s̶ ̶t̶h̶e̶ ̶c̶o̶r̶e̶ ̶d̶e̶f̶i̶n̶i̶t̶i̶o̶n̶ ̶o̶f̶ ̶t̶h̶e̶ ̶a̶l̶g̶o̶r̶i̶t̶h̶m̶ ̶t̶h̶a̶t̶ ̶i̶s̶ ̶t̶o̶ ̶h̶a̶v̶e̶ ̶n̶^̶2̶ ̶c̶o̶m̶p̶a̶r̶i̶s̶o̶n̶s̶ ̶i̶n̶ ̶w̶o̶r̶s̶t̶-̶c̶a̶s̶e̶ ̶p̶e̶r̶f̶o̶r̶m̶a̶n̶c̶e̶.
1 Week Ago #4

Rabbit
Expert Mod 10K+
P: 12,441
Just because the functions are nested doesn't automatically make it polynomial. Yes, both functions run a loop, and yes, the functions are nested. But each loop runs one after the other, they're not truly nested loops. At worst, the inside block is 2n.
1 Week Ago #5

dev7060
Expert 100+
P: 336
Just because the functions are nested doesn't automatically make it polynomial. Yes, both functions run a loop, and yes, the functions are nested. But each loop runs one after the other, they're not truly nested loops. At worst, the inside block is 2n.
Thanks. This makes complete sense.
1 Week Ago #6

Post your reply

Sign in to post your reply or Sign up for a free account.