2
\$\begingroup\$

I had the following assignment for the Python 101 course I'm taking in my university.

'''
Modify the naive implementation (see below) of a sorting algorithm so that
the list to be sorted is modified *in place*.

Here is the idea:

1. Iterate over all indices i = 0, 1, 2, ... of the input list

2. Find the index j of the smallest element in the rest of the list (from i on)

3. Replace the elements at indices i and j

If we want to sort the list [5, 3, 1, 4, 8, 2, 7, 6], for instance, a run of
the algorithm would be:

i=0, j=2, list=[5, 3, 1, 4, 8, 2, 7, 6]
i=1, j=5, list=[1, 3, 5, 4, 8, 2, 7, 6]
i=2, j=5, list=[1, 2, 5, 4, 8, 3, 7, 6]
i=3, j=3, list=[1, 2, 3, 4, 8, 5, 7, 6]
i=4, j=5, list=[1, 2, 3, 4, 8, 5, 7, 6]
i=5, j=7, list=[1, 2, 3, 4, 5, 8, 7, 6]
i=6, j=6, list=[1, 2, 3, 4, 5, 6, 7, 8]
'''

In principle, the only two funcions I have to modify are "index_of_smallest_element" and "naive_sort_inplace".

def index_of_smallest_element(some_list):
    '''Returns the index of the smallest element in some_list'''
    guess=some_list[0]    
    for element in some_list:
        if element < guess:
            guess=element
    return some_list.index(guess)


def naive_sort(some_list):
    sorted_list = []
    while len(some_list) > 0:
        # remove smallest element from some_list
        smallest_element = some_list.pop(index_of_smallest_element(some_list))
        # ... and append it to sorted_list
        sorted_list.append(smallest_element)
    return sorted_list


def naive_sort_inplace(some_list):
    def exchange(some_list,x,y):
        some_list[x],some_list[y]=some_list[y],some_list[x]        


    for i in range(0,len(some_list)):        
        remaining_list=some_list[i:(len(some_list)+1)]
        i_rest=index_of_smallest_element(remaining_list)
        j=i+i_rest
        print('i=',i,'j=',j,'list=',some_list)
        exchange(some_list,i,j)
    return some_list


if __name__ == '__main__':
    my_list = [5, 3, 1, 4, 8, 2, 7, 6]
    naive_sort_inplace(my_list)
    print('Test: ', my_list == [1, 2, 3, 4, 5, 6, 7, 8])

Although the code is fully functional, I'm wondering is there would be a better way to do it, especially the "naive_sort_inplace" function.

\$\endgroup\$

bumped to the homepage by Community 18 hours ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

0
\$\begingroup\$

Problems

First of all, your current implementation is not truly in-place, since the slice operation creates a new list of that size, which breaches the required max constant extra space usage.

In addition you perform double work in the index_of_smallest_element when you first find the value you want, and then have to run through the entire list again to find the index (the index call has linear time cost)

Advise

When working in-place you usually have to work with indexes or pointers, and this is also such a case. Most of the work can be put into 3 categories, index work, swapping work, and control flow, if you are doing work outside of those you should think through an extra time on whether you are off in a problematic direction.

This means that you should manually keep track of relevant indexes, and when calling functions the way to work on a subset is to pass the indexes describing this to it.

Solution

there are 2 main changes to be done, both connected to index_of_smallest_element. We first change thats implementation to the following:

def index_of_smallest_element(some_list, start=0):
    smallest = some_list[start]
    for i in range(start+1, len(some_list)):
       value = some_list[I]
       if value < smallest:
           smallest = value
           start = i
    return start

With this it becomes easy to write the naive (and really bad) sorting in-place:

def naive_sort_inplace(some_list, out=None):
    def exchange(some_list,x,y):
        some_list[x],some_list[y]=some_list[y],some_list[x]        


    for i in range(0,len(some_list)):
        j = index_of_smallest_element(remaining_list, i)
        if out is not None:
            out('i=',i,'j=',j,'list=',some_list)
        exchange(some_list,i,j)
    return some_list

I am not quite sure why you want to do all the printing, but I assume it is for testing or proving correctness. For reuse I have changed it so it by default does not print, but if you pass in print (or some other output function such as open(filename,'w').write) then it write those log updates to that output function.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.