Optimizing Selection Sort Algorithm for Randomly Generated 5-Digit Numbers

[zak100]

TL;DR

I am trying to write a program for selection sort. I got an example program:

https://www.geeksforgeeks.org/selection-sort/

Hi,

import random

class SSSort:
   arr = [] # class var access by className.arr
   def __init__(self, n):
      self.n = n

   def generate1000_5digit_RandomNum(self):
      for i in range(self.n):
         num = random.randint(10000, 99999)
         SSSort.arr.append(num)

      for j in range(self.n):
         print("random {0}".format(SSSort.arr[j]))

   def find_the_min_element(self, i):
      min = i
      for j in range(i+1, self.n-1):
         if (SSSort.arr[j] < SSSort.arr[min]):
            min = j

      return SSSort.arr[min]

   def selectionSort(self):
      for i in range(self.n-1):
         min = self.find_the_min_element(i)
         #swap min and ith element of array
         temp = min
         min = SSSort.arr[i]
         SSSort.arr[i] = temp
 
      for i in enumerate(SSSort.arr):
         print(i)   def main(self):
      self.generate1000_5digit_RandomNum()
      self.selectionSort()

if __name__ == "__main__":
   objSSSort = SSSort(20)
   objSSSort.main()

I am getting the following output:

random 98046
random 21192
random 50964
random 81034
random 87750
random 50619
random 32092
random 52373
random 70434
random 61962
random 67618
random 87543
random 91959
random 25470
random 13246
random 37841
random 87932
random 40889
random 64008
random 94949(0, 13246)
(1, 13246)
(2, 13246)
(3, 13246)
(4, 13246)
(5, 13246)
(6, 13246)
(7, 13246)
(8, 13246)
(9, 13246)
(10, 13246)
(11, 13246)
(12, 13246)
(13, 13246)
(14, 13246)
(15, 37841)
(16, 40889)
(17, 40889)
(18, 64008)
(19, 94949)

Somebody please guide me how to correct the above program.Zulfi.

 

[jedishrfu]

From your data 13246 looks to be the minimum value and so maybe in doing the swapping vs the finding of the minimum. One thing I see is that you are placing the min value in the ith location but aren't placing the ith location back to the jth location where you found min. Perhaps your find should return the index not the value

j=find_min(i)

temp = aaa(i)    // had to use parens because square brackets mess up with italics
aaa(i) = aaa(j)
aaa(j) = temp

Why not place print statements in the swapping method to see what is getting swapped. At each swap you could also print the whole list to see what happened and if that made sense.

Are you using the Pycharm IDE, it has a decent python code debugger which would allow you to step through the code and find your error faster.

 

[pbuk]

Somebody please guide me how to correct the above program.

Why? If you want a Python selection sort that works, there is one on the site you linked. If you want to learn how to write code, then you will only do this by working out where your code is going wrong and fixing it yourself.

I believe this has been mentioned to you before: work through your code line by line, working out what is happening to the state of your variables in each line, either using the facilities of an IDE or in your head (this becomes easier with practice), or on paper or if none of these works, by printing variables at key points.

But before you do any of that, learn properly how to write code in Python. You can do this from a book or from an online tutorial such as CodeAcademy. After working through the basics, you will start to learn about classes, why we break code up into class methods and the difference between static properties of the class like SSort.arr and properties of a object instance of the class like self.n.

 

[zak100]

Hi,

Thanks I solved this problem. It was mainly the swapping problem.

Zulfi.