Agfdhyk

I am learning selection sort algorithms

from typing import List

def find_smallest(arr:List) -> int:

    smallest = arr[0] #set pivot

    smallest_index = 0

    for i in range(1, len(arr)):

        if arr[i] < smallest:

            smallest = arr[i]

            smallest_index = i

    return smallest_index



def selection_sort(arr) -> List:

    new_arr = 

    for i in range(len(arr)):

        smallest = find_smallest(arr)

        new_arr.append(arr.pop(smallest))

    return new_arr

I am curious about the function find_smallest,

it firstly presume arr[0] as the smallest and initiate the loop.

I know the complete code is called selection sort algorithms,

How about the presume and update its value in the loop, is there an terminology for it?

I think bubble sort is the answer. I've never think about the bubble loop as an assumption about the smallest, until I see your question :D

def sort(arr):

    for i in range(len(arr)):

        # we presume a[i] is the smallest one. Then we update by compare it with the rest of the list

        for j in range(i + 1, len(arr)):

            if arr[i] > arr[j]: # if our assumption is wrong (arr[i] is not the smallest), update it with arr[j] (which is smaller than arr[i])

                swap(arr[i], arr[j])



        # After this `for j` loop, arr[i] will be the smallest value of the list

No.There is no terminology for it unlike quick sort where we choose a pivot and compare elements.
Out of the topic but a interesting fact on selection sort is

The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

It presumes the first index of the list to be the smallest value, and runs down the list to see if there are any smaller values, and when it does find a smaller value, it updates the smallest, it does this till the end of the list to make sure you find the smallest value in the entire list, in the example you provided it returns the index of smallest value in the list.

I added 2 print statements which should give you an idea on how its working:

from typing import List

def find_smallest(arr:List) -> int:

    smallest = arr[0] #set pivot

    smallest_index = 0

    print("presumed smallest {}".format(smallest)) #print presumed

    for i in range(1, len(arr)):

        if arr[i] < smallest:

            smallest = arr[i]

            smallest_index = i

            print("updated smallest {}".format(smallest)) #print updates to smallest

    return smallest_index

And the results:

find_smallest([7,6,1,3,8,9,0])



>>presumed smallest 7

updated smallest 6

updated smallest 1

updated smallest 0



6