Сортировка выбором (поиск минимума и перестановка)

Описание алгоритма

  1. Найти наименьшее значение в исходном множестве.
  2. Записать его в начало множества, а первый элемент - на место наименьшего.
  3. Снова найти наименьший элемент в оставшемся множестве и переместить его на второе место. Второй элемент при этом перемещается на освободившееся место.
  4. Продолжать выполнять поиcк и обмен, пока не будет достигнут конец множества.

Исходный код на Python

Как найти наименьшее значение в списке?

s = [2,4,1,3]  #подопытный список 
 
m = 0   #индекс первого элемента
i = 1     #индекс второго элемента 
 
while i < len(s): #пока индекс меньше длины строки
   if s[i] < s[m]: # если значение под индексом i меньше, чем под m,
        m = i # то присвоить m индекс i
    i += 1 # увеличить i на единицу 
 
print (s[m]) # вывести значение элемента под индексом m

Обратите внимание на строку while i < len(s):. Не нужно писать <=, т.к. индексация начинается с нуля. Это значит, что когда i равен 3, то мы обращаемся к 4-му элементу списка (в примере, это как раз конец строки).
Как поменять два значения в списке местами?

s = [2,4,9,1,3,7,5]  #подопытный список
# требуется поменять местами первый и четвертый элементы
m = 0   #индекс первого элемента
i = 3   #индекс четвертого элемента 
 
t = s[m] # сохраняется значение под индексом m
s[m] = s[i] # на его место записывается значение под индексом i
s[i] = t # на место значения под индексом i записывается ранее сохраненное значение под индексом m 

Полный алгоритм сортировки выбором

s = [2,4,8,1,0,3,9,5,7,6]
print (s) 
 
#в переменной k хранится индекс элемента, подлежащего обмену (двигаемся слева на право)
k = 0
while k < len(s) - 1: #-1, т.к. последний элемент обменивать уже не надо
    m = k #в m хранится минимальное значение
    i = k + 1 #откуда начинать поиск минимума (элемент следующий за k)
    while i < len(s):
        if s[i] < s[m]:
            m = i
        i += 1
    t = s[k]
    s[k] = s[m]
    s[m] = t
    k += 1 #переходим к следующему значению для обмена 
 
print(s) 

Оформление алгоритма в виде функции и пример использования цикла for

def mymin(mylist):
    for k in range(len(mylist) - 1):
        m = k
        i = k + 1
        while i < len(mylist):
            if mylist[i] < mylist[m]:
                m = i
            i += 1
        t = mylist[k]
        mylist[k] = mylist[m]
        mylist[m] = t

уходим от while

for i in range(len(s)-1):
    for j in range(i+1,len(s)):
        if s[i]>s[j]: 
            s[i],s[j]=s[j],s[i]

Производительность

Извиняюсь, я вот все никак не пойму, а почему сортировка выбором работает медленнее пузырька?
Примеры брал ваши.
Во всех источниках говорится, что в среднем быстрее должна быть выбором, а не пузырек.
Это какая то особенность работы Python с list или что?

А как вы определили, что

А как вы определили, что сортировка выбором работает медленнее?

По-идее, в обоих случаях изменяется исходный список. Так что, "тормознутость" бы проявилась в обоих случаях.

# -*- coding: utf-8

# -*- coding: utf-8 -*-
import profile
import random
from heapq import sort
 
s = [x for x in xrange(1000)]
random.shuffle(s)
print (s) 
arr=[]
 
 
def SortOption(mylist):#Сортировка выборкой
    for k in range(len(mylist) - 1):#-1, т.к. последний элемент обменивать уже не надо
        m = k #в m хранится минимальное значение
        i = k + 1#откуда начинать поиск минимума (элемент следующий за k)
        while i < len(mylist):
            if mylist[i] < mylist[m]:
                m = i
            i += 1
        t = mylist[k]
        mylist[k] = mylist[m]
        mylist[m] = t
    return mylist
 
profile.run('arr=SortOption(s)')
print(arr)
 
def SortBubble(mylist):#Сортировка пузырьком
    n = 1 
    while n < len(mylist):
         for i in range(len(mylist)-n):
              if mylist[i] > mylist[i+1]:
                   mylist[i],mylist[i+1] = mylist[i+1],mylist[i]
         n += 1
    return mylist
 
profile.run('arr=SortBubble(s)')
print(arr)

Вот таким методом.

Действительно, загадка

Могу только предположить, что это связано с тем, что в Питоне переменные по сути являются лишь ссылками.

При сортировке списка данные в памяти могут не переставляться, меняются лишь значение указателей на них (ссылок на память, их роль играют индексы). Т.е. если mylist[10] указывает на число 325, то после сортировки на это число может указывать mylist[89], однако само число остается на месте.

По идее, в методе пузырька память данных остается не тронутой. А вот в сортировке выборкой как минимум из-за переменной t происходит копирование значения в другую область памяти.

Проблема решена!

Не стоит ночью править код, не видишь того, что написано черным по белому!
Профайлер писал что вычисление длины списка происхожило 500500, отсюда и проблема!
Ну жно всего лишь заменить

l=len(mylist)

и использовать везде её, а не вычислять длину заново.
К сожалению даже с этим исправлением этот вариант сортировки не обходит пузырек(((
Код на вики работает быстрее(обоих), поэтому предлогаю использовать его, только там ищут макс и соответственно добавляют вверх.
def select_sort(arr):
    i = len(arr)
    while i > 1:
        max = 0
        for j in xrange(i):
            if arr[j] > arr[max]:
                max = j
        arr[i - 1], arr[max] = arr[max], arr[i - 1]
        i -= 1
    return arr

И все же...почему ваш код медленнее???

Потому что длина определяется

Потому что длина определяется - в цикле. Правильный код для исходного варианта:

def SelectionSort(mylist):#Сортировка выбором
    ln=len(mylist) 
    for k in range(ln-1):#-1, т.к. последний элемент обменивать уже не надо
        m = k #в m хранится минимальное значение
        i = k + 1#откуда начинать поиск минимума (элемент следующий за k)
        while i < ln:
            if mylist[i] < mylist[m]:
                m = i
            i += 1
        if k!=m:
          mylist[k],mylist[m] = mylist[m],mylist[k]
    return mylist</code>

Результат:

--------- SELECTION sort:
 
         6 function calls in 0.143 seconds
 
   Ordered by: standard name
 
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 :0(len)
        1    0.000    0.000    0.000    0.000 :0(range)
        1    0.001    0.001    0.001    0.001 :0(setprofile)
        1    0.000    0.000    0.142    0.142 <string>:1(<module>)
        1    0.000    0.000    0.143    0.143 profile:0(arr=SelectionSort(s))
        0    0.000             0.000          profile:0(profiler)
        1    0.142    0.142    0.142    0.142 selection_and_bubble_sort_profile_while_better.py:11(SelectionSort)
 
---------  BUBBLE sort:
 
         3002 function calls in 0.130 seconds
 
   Ordered by: standard name
 
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1999    0.008    0.000    0.008    0.000 :0(len)
      999    0.009    0.000    0.009    0.000 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        1    0.000    0.000    0.130    0.130 <string>:1(<module>)
        1    0.000    0.000    0.130    0.130 profile:0(arr=BubbleSort(s))
        0    0.000             0.000          profile:0(profiler)
        1    0.113    0.113    0.130    0.130 selection_and_bubble_sort_profile_while_better.py:28(BubbleSort)

Если заменить эти строчки t =

Если заменить эти строчки

t = mylist[k]
mylist[k] = mylist[m]
mylist[m] = t

вот так:
mylist[k],mylist[m] = mylist[m],mylist[k]

, то сортировка выбором будет быстрее.

Действительно, с точки зрения Python код выше для сортировки выбором написан не корректно.

Спасибо

Спасибо! Видимо как вы говорили так и происходит, меняются лишь указатели.