This week's book giveaway is in the Agile and Other Processes forum.
We're giving away four copies of Real-World Software Development: A Project-Driven Guide to Fundamentals in Java and have Dr. Raoul-Gabriel Urma & Richard Warburton on-line!
See this thread for details.
Win a copy of Real-World Software Development: A Project-Driven Guide to Fundamentals in Java this week in the Agile and Other Processes forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Bear Bibeault
  • Liutauras Vilda
  • Devaka Cooray
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • Henry Wong
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • salvin francis
  • Frits Walraven
  • Piet Souris

Python: Selection Sort Problem (Not correct sorting)

 
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
I am trying to write a program for selection sort. I got an example program:



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



I have written the following code:


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)




I think there is problem with swapping.

Somebody please guide me how to correct the above program;

Zulfi.
 
Greenhorn
Posts: 11
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Zulfi,

First a few comments:
* Why is arr a class variable instead of an instance variable? Having it as a class variable will cause conflicts when you have m,ultiple instances of SSSSort. It would be better to use an instance variable (initialized with self.arr = [] in the __init__ method)
* A better name for  generate1000_5digit_RandomNum would be  generateN_5digit_RandomNum
* In generate1000_5digit_RandomNum, a simpler way to iterate through the array would be to use a simple for elt in arr loop
* The parenthesis in if (SSSort.arr[j] < SSSort.arr[min]): are unnecessary
* Using slightly longer variable names would make it clearer to understand if a variable contains an index or an element.
* You are doing a pretty good following PEP8 (The Python coding guidelines) except in a couple of places (selectionSort instead of selection_sort and objSSSort instead of obj_SSSort)

The problem lies with lines 3 and 6 of the selectionSort method:

At line 3, find_the_min_element returns the value of the minimum element from i. What you need instead is the index of the minimum element from i.
At line 6, min is overwritten but it not used anymore in the current iteration. This line can be deleted without changing the behaviour of your program.

In general the pattern for swapping elements i and j in an array is:


There is also a fence post error in find_the_min_element because the last element is never taken into consideration. This means that it will never stand a chance to be swapped.

Here is the version I ended up with:


Hope this helps.
 
Zulfi Khan
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
Thanks for providing me this explanation.
By now I have corrected my code but your comments are good.

I have not tried to execute your code but I have one question for line#25 of your code:



I actually realized my mistake. Argument of "range" starts from 0 and goes up to "n-1", so there is no need of explicitly doing (self.n-1), so I changed it to (self.n).


You might have better reasons for doing this.

Your help is appreciable.

God bless you.

Zulfi.
 
Nicolas Beney
Greenhorn
Posts: 11
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi again,

range(N) goes from 0 to N-1. A list of length N has indices between 0 and N-1.

The code works correctly with both my range(self.n - 1) and your range(self.n) at line #25.

When using range(self.n - 1), the loop in selection_sort will stop at idx = n-2 (ie the penultimate element) but find_the_min_element_index will go up to n-1 (ie the last element).

When using range(self.n), the loop in selection_sort will stop at idx = n-1 (ie the last element) and the loop in find_the_min_element_index will exit immediately. The end result will be correct but at the (negligible) cost of one unnecessary iteration in the main loop and on unnecessary call to find_the_min_element_index in selection_sort.

Hope this makes sense.

Nicolas
 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I tried to work on given solution it helpful to resolve and learn about python.
Selection Sort is not stable because it swaps non-adjacent elements. Given [2, 2, 1], the '2' values will not retain their initial order. Selection sort first swaps the (1, 0) to the front: And now the (4, 0) and (4, 1) are out of order from where they started in the sort.The selection sort algorithm sorts an array by repeatedly finding the minimum element . order) from the unsorted subarray is picked and moved to the sorted subarray.Python program for implementation of Selection. # Sort. import sys .You want to share more then share now I start to learn online from Cetpa Infotech.
 
First, you drop a couch from the plane, THEN you surf it. Here, take this tiny ad with you:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!