Trying to create a sorting algorithm from scratch in Python

Question

I'm taking a course on programming (I'm a complete beginner) and the current assignment is to create a Python script that sorts a list of numbers in ascending order without using built-in functions like "sorted".

The script I started to come up with is probably laughably convoluted and inefficient, but I'd like to try to make it work eventually. In other words, I don't want to just copy someone else's script that's better.

Also, as far as I can tell, this script (if it ever functioned) would probably just put things in a NEW order that wouldn't necessarily be ascending. This is just a start, though, and hopefully I'll fix that later.

Anyway, I've run in to several problems with the current incarnation, and the latest is that it just runs forever without printing anything.

So here it is (with hashes explaining what I was trying to accomplish). If someone could look over it and tell me why the code does not match my explanations of what each block is supposed to do, that would be great!

# The numbers to be inputted, could be anything
numList = [1, 25, 5, 6, 17, 4]                     

# The final (hopefully sorted) list
numSort = []

# The index
i = 0

# Run the loop until you run out of numbers
while len(numList) != 0:                                       

    # If there's only one value left in numList,
    # attach it to the end of numSort.
    # (Variable 'basket' is just for transporting numbers)
    if len(numList) == 1:                                       
        basket = numList.pop()
        numSort.append(basket)

    # The rest of the elifs are supposed to compare values
    # that sit next to each other.

    # If there's still a number in numList after 'i'
    # and 'i' is smaller than that next number
    # then pop 'i' and attach it to the end of numSort
    elif numList[i+1] != numList[-1] and numList[i] < numList[i+1]:   
        basket = numList.pop(i)                                 
        numSort.append(basket)

    # If there's NOT a number after 'i'
    # then compare 'i' to the first number in the list instead.
    elif numList[i+1] == numList[-1] and numList[i] < numList[0]:      
        basket = numList.pop(i)                                 
        numSort.append(basket)

    # If 'i' IS the last number in the list
    # and has nothing to compare itself to,
    # Then start over and go through it again
    # from the beginning
    elif numList [i+1] == numList[-1]:
        i = 0

    # If 'i' is not at the end of numList yet
    # and 'i' is NOT smaller than the next number
    # and there are still numbers left
    # then move on to the next pair
    # and continue comparing and moving numbers
    else:                                                       
        i = i+1

# Hopefully these will be in ascending order eventually.
print(numSort)

already, you can replace while len(numList) != 0: by while numList: — DevLounge
– DevLounge, Commented Apr 21, 2016 at 20:47
The first semantic error I see is numList [i+1] == numList[-1]. This does not check whether the number at position i is the last number of the list, it checks whether the number at position i+1 is equal to the last number of the list. — timgeb
– timgeb, Commented Apr 21, 2016 at 20:50
May be work with arrays first, and try understanding what numList[-1] does. — Sharif Mamun
– Sharif Mamun, Commented Apr 21, 2016 at 20:53
Is there any kind of problem with implementing other algorithms? like bubble sort, selection sort, etc... those are simple and implementing them is really easy and it would take much less code. — Eekan
– Eekan, Commented Apr 21, 2016 at 20:53
When you use pop the index again starts from zero so here you will get an index error on this line elif numList[i+1] != numList[-1] and numList[i] < numList[i+1] — python
– python, Commented Apr 21, 2016 at 20:59

Nisamrine · Accepted Answer · 2021-01-07 14:09:15Z

1

Here is a simple way to sort your list with a classic loop :

myList = [2,99,0,56,8,1]
for i,value in enumerate(myList):
     for j,innerValue in enumerate(myList):
         if value < innerValue: #for order desc use '>'
             myList[j],myList[i]=myList[i],myList[j]
 print(myList)

The Algorithm behind this code is :

fix one value of the list and compare it with the rest
if it is smallest then switch the index of two values

I hope this will help you

answered Jan 7, 2021 at 14:09

Nisamrine

851 silver badge3 bronze badges

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

1 Comment

Jagdish Singh Over a year ago

Hi @Nisamrine, the code will fail for some cases like if mylist=[21,99,0,156,21,11], it will return [0, 21, 11, 21, 99, 156].check this post: codereview.stackexchange.com/questions/252860/…

jessi · Accepted Answer · 2016-04-21 21:22:00Z

Your conditions are essentially:

If there is only one number in the list
The current number is less than the next, which is not equal to the last number
The current number is less than the first number, and the next number is equal to the last number
The next number is equal to the last number

If you trace out the code by hand you will see how in many cases, none of these will evaluate to true and your "else" will be executed and i will be incremented. Under these conditions, certain numbers will never be removed from your original list (none of your elifs will catch them), i will increment until the next number is equal to the last number, i will be reset to zero, repeat. You are stuck in an infinite loop. You will need to update your if-statement in such a way that all numbers will eventually be caught by a block other than your final elif.

On a separate note, you are potentially comparing a number to only one number in the current list before appending it to the "sorted" list. You will likely need to compare the number you want to add to your "sorted" list and find its proper place in THAT list rather than merely appending.

You should also consider finding the end of list using a method more like

if i == len(numList) - 1

This will compare the index to the length of the list rather than comparing more values in the list which are not necessarily relevant to the order you are trying to create.

Collectives™ on Stack Overflow

Trying to create a sorting algorithm from scratch in Python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related