Python lists - codes & algorithem

Question

I need some help with python, a new program language to me. So, lets say that I have this list:

list= [3, 1, 4, 9, 8, 2]

And I would like to sort it, but without using the built-in function "sort", otherwise where's all the fun and the studying in here? I want to code as simple and as basic as I can, even if it means to work a bit harder. Therefore, if you want to help me and to offer me some of ideas and code, please, try to keep them very "basic".

Anyway, back to my problem: In order to sort this list, I've decided to compare every time a number from the list to the last number. First, I'll check 3 and 2. If 3 is smaller than 2 (and it's false, wrong), then do nothing.

Next - check if 1 is smaller than 2 (and it's true) - then change the index place of this number with the first element. On the next run, it will check again if the number is smaller or not from the last number in the list. But this time, if the number is smaller, it will change the place with the second number (and on the third run with the third number, if it's smaller, of course).

and so on and so on. In the end, the ()function will return the sorted list. Hop you've understand it. So I want to use a ()recursive function to make the task bit interesting, but still basic. Therefore, I thought about this code:

def func(list):
if not list:
    for i in range(len(list)):
        if list[-1] > lst[i]:
           #have no idea what to write here in order to change the locations
            i = i + 1
        #return func(lst[i+1:])?
    return list

2 questions: 1. How can I change the locations? Using pop/remove and then insert? 2. I don't know where to put the recursive part and if I've wrote it good (I think I didn't). the recursive part is the second "#", the first "return".

What do you think? How can I improve this code? What's wrong?

Thanks a lot!

Answer 1

Oh man, sorting. That's one of the most popular problems in programming with many, many solutions that differ a little in every language. Anyway, the most straight-forward algorithm is I guess the bubble sort. However, it's not very effective, so it's mostly used for educational purposes. If you want to try something more efficient and common go for the quick sort. I believe it's the most popular sorting algorithm. In python however, the default algorithm is a bit different - read here. And like I've said, there are many, many more sorting algorithms around the web.

Now, to answer your specific questions: in python replacing an item in a list is as simple as

list[-1]=list[i]

or

tmp=list[-1]
list[-1]=list[i]
list[i]=tmp

As to recursion - I don't think it's a good idea to use it, a simple while/for loop is better here.

Answer 2

maybe you can try a quicksort this way :

def quicksort(array, up, down):
    # start sorting in your array from down to up :
    # is array[up] < array[down] ? if yes switch
    # do it until up <= down 
    # call recursively quicksort 
    #        with the array, middle, up
    #        with the array, down, middle
    # where middle is the value found when the first sort ended

you can check this link : Quicksort on Wikipedia It is nearly the same logic.

Hope it will help !

Answer 3

1. The easiest way to swap the two list elements is by using “parallel assignment”:

   list[-1], list[i] = list[i], list[-1]
   

2. It doesn't really make sense to use recursion for this algorithm. If you call func(lst[i+1:]), that makes a copy of those elements of the list, and the recursive call operates on the copy, and then the copy is discarded. You could make func take two arguments: the list and i+1.

But your code is still broken. The not list test is incorrect, and the i = i + 1 is incorrect. What you are describing sounds a variation of selection sort where you're doing a bunch of extra swapping.

Here's how a selection sort normally works.

1. Find the smallest of all elements and swap it into index 0.
2. Find the smallest of all remaining elements (all indexes greater than 0) and swap it into index 1.
3. Find the smallest of all remaining elements (all indexes greater than 1) and swap it into index 2.
4. And so on.

To simplify, the algorithm is this: find the smallest of all remaining (unsorted) elements, and append it to the list of sorted elements. Repeat until there are no remaining unsorted elements.

We can write it in Python like this:

def func(elements):
    for firstUnsortedIndex in range(len(elements)):
        # elements[0:firstUnsortedIndex] are sorted
        # elements[firstUnsortedIndex:] are not sorted
        bestIndex = firstUnsortedIndex
        for candidateIndex in range(bestIndex + 1, len(elements)):
            if elements[candidateIndex] < elements[bestIndex]:
                bestIndex = candidateIndex
        # Now bestIndex is the index of the smallest unsorted element
        elements[firstUnsortedIndex], elements[bestIndex] = elements[bestIndex], elements[firstUnsortedIndex]
        # Now elements[0:firstUnsortedIndex+1] are sorted, so it's safe to increment firstUnsortedIndex
    # Now all elements are sorted.

Test:

>>> testList = [3, 1, 4, 9, 8, 2]
>>> func(testList)
>>> testList
[1, 2, 3, 4, 8, 9]

If you really want to structure this so that recursion makes sense, here's how. Find the smallest element of the list. Then call func recursively, passing all the remaining elements. (Thus each recursive call passes one less element, eventually passing zero elements.) Then prepend that smallest element onto the list returned by the recursive call. Here's the code:

def func(elements):
    if len(elements) == 0:
        return elements
    bestIndex = 0
    for candidateIndex in range(1, len(elements)):
        if elements[candidateIndex] < elements[bestIndex]:
            bestIndex = candidateIndex
    return [elements[bestIndex]] + func(elements[0:bestIndex] + elements[bestIndex + 1:])