464,553 Members | 851 Online
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 Input:   list = [23, 12, 65, 34, 91, 43]   print(list)   for i in range(len(list)):     min_index = list.index(min(list[:len(list)-i]))     list.append(list[min_index])     list.pop(min_index)   print(list)   Output:   [23, 12, 65, 34, 91, 43] [12, 23, 34, 43, 65, 91] 1 Week Ago #1
5 Replies

 Expert 100+ P: 336 Correct answer by Rabbit Expand|Select|Wrap|Line Numbers print(list)   for i in range(len(list)):     min_index = list.index(min(list[:len(list)-i]))     list.append(list[min_index])     list.pop(min_index)   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

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

 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

 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

 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