Select sort in python

Selection Sort Python

This may seem like a simple question but when I attempted to implement selection sort in Python, I do not get a sorted list. Is there something wrong with my implementation? The subsetting may be a problem.

source = [4,2,1,10,5,3,100] for i in range(len(source)): mini = min(source[i:]) #find minimum element min_index = source[i:].index(mini)-1 #find index of minimum element source[i:][min_index]= source[i:][0] #replace element at min_index with first element source[i:][0] = mini #replace first element with min element print source 

14 Answers 14

I think there were a couple issues.

First, when your do source[i:], I believe that returns a new array of the sub-elements requested and not part of the original array, thus if you modify it, your don’t modify the original. Second, you were subtracting 1 from an index when you shouldn’t.

source = [4,2,1,10,5,3,100] for i in range(len(source)): mini = min(source[i:]) #find minimum element min_index = source[i:].index(mini) #find index of minimum element source[i + min_index] = source[i] #replace element at min_index with first element source[i] = mini #replace first element with min element print source 

instead of finding min_index from source[1:].index try finding by source.index, this would simplify your next step of swap, just swap using source[i],source[min_index] = source[min_index], source[i].

Here is how I would rewrite your code. Of course in Python I would just use list.sort() to sort a list, but here is a selection sort in Python.

We make a generator expression that returns tuples of (value, i) for a value and its index from the list. Then when min() evaluates to find minimum, it finds the lowest tuple value; since the value comes first in the tuple before the index, the value will be the important part, and min() will find the lowest value. (If there is a tie, min() will use the second part of the tuple, the index, as a tie-breaker. But for sort we don’t care how ties are broken.)

Now, instead of searching through the sub-list to find the min value, and then searching through it again to figure out the index, we search through it once and get both min value and index.

But we don’t actually care about the min value; we care about the index. So after min() is done, we just throw away the actual value but keep the index. Adjust the index to be correct in the whole list (not in the slice of the list) and then we can swap.

We use the standard Python idiom for swapping two values. Python will build a tuple object to be the intermediate, then unpack this tuple into the left-hand-side.

lst = [4,2,1,10,5,3,100] for i_sortpos in range(len(lst)): # Make a generator expression to return (value, i) pairs. genexp = ((n, i) for i, n in enumerate(lst[i_sortpos:])) # Use genexp with min() to find lowest and its index. # (Use '_' for variable name for the actual value; we don't use it.) _, i_min = min(genexp) # Adjust index to be correct in full list. i_min += i_sortpos # Swap the number at i_sortpos with the lowest found. lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos] print(lst) 

EDIT: And here is a refinement of the above. A slice from a list actually allocates a new list; our code here doesn’t need a new list, it just needs a convenient way to examine a sublist. The itertools module offers a function, islice() , that returns an iterator that iterates over a slice of a list. This avoids repeatedly creating and destroying lists as we examine each sublist.

I believe this is the most efficient way to do selection sort in Python. (You could get rid of the part where we bind the generator expression to the name genexp and save a few microseconds. just make the call to min() a long one-liner. But it’s not really worth the loss of readability.)

import itertools as it lst = [4,2,1,10,5,3,100] for i_sortpos in range(len(lst)): # Make a generator expression to return (value, i) pairs. # Use it.islice() for to look at sublist. genexp = ((n, i) for i, n in enumerate(it.islice(lst, i_sortpos, len(lst)))) # Use genexp with min() to find lowest and its index. # (Use '_' for variable name for the actual value; we don't use it.) _, i_min = min(genexp) # Adjust index to be correct in full list. i_min += i_sortpos # Swap the number at i_sortpos with the lowest found. lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos] print(lst) 

Источник

Сортировка выбором на Python

Статьи

Введение

В данной статье познакомимся с сортировкой выбором, и реализуем её на Python.

Алгоритм работы сортировки выбором

Допустим у нас есть следующий список: [5, 7, 2, 10, 1, 8]

1. Сначала нужно найти наименьшее значение в заданном списке. В нашем случае это элемент 1;
2. Поменять местами самый первый элемент списка и самый наименьший. В итоге мы получим такой список: [1, 7, 2, 10, 5, 8];
3. Найти следующий наименьший элемент исключив из поиска самый первый элемент. У нас это 2;
4. Поменять местами второй элемент списка и найденный элемент. Получим [1, 2, 7, 10, 5, 8];
5. Проделывать все те же действия, пока не будет отсортирован весь список.

Как менялся наш список по итерациям:

Сортировка выбором на Python используя цикл while

Для начала сгенерируем неупорядоченный список неповторяющихся элементов и выведем его в консоль:

from random import sample my_lst = sample(range(10), 5) print(my_lst)

Создадим переменную N, в которую сохраним длину нашего списка:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst)

Также создадим переменную i, в которой будет храниться индекс ячейки, в которую запишется следующий минимальный элемент:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst) i = 0

Создадим цикл while, который не закончится пока не пройдётся по всем элементам списка my_lst:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst) i = 0 while i < N - 1:

Теперь нам нужно найти минимальный элемент списка как было показано в алгоритме работы сортировки выбором. Создадим переменную m, в которой будет храниться индекс ячейки минимального элемента. Изначально приравниваем её к i, предполагая что там находится минимальный элемент:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst) i = 0 while i < N - 1: m = i

Создадим переменную j, которая понадобится для поиска минимального элемента. Она будет равна ячейке идущей после i:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst) i = 0 while i < N - 1: m = i j = i + 1

Создадим вложенный цикл while, в котором пройдёмся по списку. Внутри цикла сравним значение ячейки j и значение в m:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst) i = 0 while i < N - 1: m = i j = i + 1 while j < N: if my_lst[j] < my_lst[m]:

Если же по индексу j хранится значение меньше, чем по индексу m, то сохраняем в m индекс найдённого на данный момент минимального элемента:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst) i = 0 while i < N - 1: m = i j = i + 1 while j < N: if my_lst[j] < my_lst[m]: m = j

После условия добавим j += 1 для перехода к следующей ячейке:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst) i = 0 while i < N - 1: m = i j = i + 1 while j < N: if my_lst[j] < my_lst[m]: m = j j += 1

После вложенного цикла запишем в ячейку с индексом i найденный минимальный элемент, а бывшее значение по индексу i передадим m. В конце выведем отсортированный список:

from random import sample my_lst = sample(range(10), 5) print(my_lst) N = len(my_lst) i = 0 while i < N - 1: m = i j = i + 1 while j < N: if my_lst[j] < my_lst[m]: m = j j += 1 my_lst[i], my_lst[m] = my_lst[m], my_lst[i] i += 1 print(my_lst)

Сортировка выбором на Python используя цикл for

Для сортировки выбором также можно использовать цикл for. Для начала как и в предыдущем способе сгенерируем несортированный список, выведем его в консоль, и сохраним его длину в переменную N:

from random import sample my_lst = sample(range(10), 5) N = len(my_lst) print(my_lst)

Создадим цикл for, в котором пройдёмся по длине списка my_lst – 1. Внутри цикла для начала создадим переменную m, в которой будет храниться индекс ячейки минимального элемента:

from random import sample my_lst = sample(range(10), 5) N = len(my_lst) print(my_lst) for i in range(N - 1): m = i

Теперь создадим вложенный цикл, в котором пройдёмся по индексам от i + 1, до N:

from random import sample my_lst = sample(range(10), 5) N = len(my_lst) print(my_lst) for i in range(N - 1): m = i for j in range(i + 1, N):

Во вложенном цикле добавим условие, что если по индексу j хранится значение меньше, чем по индексу m, то сохраняем в m индекс найдённого на данный момент минимального элемента:

from random import sample my_lst = sample(range(10), 5) N = len(my_lst) print(my_lst) for i in range(N - 1): m = i for j in range(i + 1, N): if my_lst[j] < my_lst[m]: m = j

После вложенного цикла поменяем местами значение по индексу i со значением по индексу m:

from random import sample my_lst = sample(range(10), 5) N = len(my_lst) print(my_lst) for i in range(N - 1): m = i for j in range(i + 1, N): if my_lst[j] < my_lst[m]: m = j my_lst[i], my_lst[m] = my_lst[m], my_lst[i]

После основного цикла выведем итоговый результат:

from random import sample my_lst = sample(range(10), 5) N = len(my_lst) print(my_lst) for i in range(N - 1): m = i for j in range(i + 1, N): if my_lst[j] < my_lst[m]: m = j my_lst[i], my_lst[m] = my_lst[m], my_lst[i] print(my_lst)

Заключение

В ходе статьи мы с Вами разобрались с тем, как работает сортировка выбором, и смогли её реализовать на Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂

Источник

Selection Sort in Python

Today we will learn a simple and easy to visualize sorting algorithm called the Selection Sort in Python. Let’s get started.

The Selection Sort Algorithm

Similar to Insertion Sort, the insertion sort algorithm divides the list into two parts. The first part at the beginning of the list is the sorted part and the second part at the end of the list is unsorted.

Initially, the entire list is unsorted but with every iteration, the smallest item in the list is searched (for ascending list) and added to the sorted section.

How this happens is that one by one, we find the smallest item in the unsorted section and swap it with the item at its correct position.

So in the first iteration, the smallest item is swapped with the item at the first position. In the second iteration, the second smallest item is swapped with the item at the second position. And so on…

Implementing Selection Sort in Python

Below is a simple implementation of selection sort in Python.

def selection_sort(lst): n = len(lst) for i in range(n - 1): min = i for j in range(i + 1, n): if(lst[j] < lst[min]): min = j lst[i], lst[min] = lst[min], lst[i]

Notice that the function takes in a list and performs the sorting in-place, it is fairly simple to alter the algorithm to return a sorted list instead.

Explaining the Steps of the Selection Sort Algorithm

This algorithm sorts the list in increasing order, let us see how it works.

• The variable n is the number of items in the list.
• Now, i goes from 0 to n - 2 , which means that i points from the first item to the second-last item. The role of i is that it will always point to where the next smallest item will go, so we will find the smallest item from i to the end of the list, and it will be placed at i .
• We are considering the item at i to be the smallest one for now, because if we fail to find a smaller element after i , then i holds the correct item.
• Inside, j goes from i + 1 to n - 1 , which means that j will point to all the items after i , and it will be responsible to find the smallest item in that range.
• Now we compare the item at j to the smallest item we have found yet, and if the item at j is smaller, then it becomes the smallest item we have found yet.
• After the inner loop, we have found the smallest item from i to n - 1 , and it is swapped with the item at i so that it goes to its correct position.
• The outer loop will continue to select and place the next smallest items one after the other until the entire list is sorted.

Now we will try to dry-run this algorithm on an example and see how it affects the sequence.

Let’s consider the sequence as 12, 16, 11, 10, 14, 13.
Size of the given list (n): 6

12, 16, 11, 10 , 14, 13
10 , 16, 11 , 12, 14, 13
10 , 11 , 16, 12 , 14, 13
10 , 11 , 12 , 16, 14, 13
10 , 11 , 12 , 13 , 14 , 16
10 , 11 , 12 , 13 , 14 , 16

• The numbers in green are the ones that have been sorted.
• The numbers in blue are the smallest ones from the ones that are not sorted.
• The uncolored ones are to be sorted.

It can be seen that the algorithm finds the smallest items and then swaps them with the item at their correct place.

The Output

Running the same list on the algorithm will produce the following result:

Conclusion

In this tutorial, we saw how Selection Sort works, we implemented the algorithm in Python and verified the dry-run of an example using the actual output of the code.

Selection Sort, similar to Bubble and Insertion Sort, has a complexity of O(n 2 ). This means that if the input size is doubled, the time it takes to execute the algorithm increases by four times, and so, it is an inefficient sorting algorithm.

It is generally less efficient than Insertion Sort but it is much simpler to understand and implement. I hope you enjoyed learning about Selection Sort and see you in the next tutorial.

Источник