DjangoBB LoFi version

Полная версия: что не так с этой пузырьковой сортировкой ?

Начало » Центр помощи » что не так с этой пузырьковой сортировкой ?

1 2

oleksii.animation

Июль 18, 2016 00:29:15

те я только разбираюсь с Python и хотелось бы понять как должна грамотно выглядеть пузырьковая сортировка (пайтоник?)

 import random
numbers = [random.randint(0,100) for x in range(1,10)]
def xsort(numbers):
    counter = 0
    for i in numbers:
        try:
            if numbers[counter] > numbers[counter + 1]:
                numbers[counter], numbers[counter + 1] = numbers[counter + 1], numbers[counter]
            counter = counter + 1
                        
        except IndexError:
            counter = 0
            try:
                for i in numbers:
                    null = numbers[counter + 1]
                    counter = counter + 1
                   
                    if i > null:
                        xsort(numbers)
                            
            except IndexError:
                
                return numbers
                
        
xsort(numbers)
print(numbers)

py.user.next

Июль 18, 2016 03:01:22

На питоне она будет выглядеть точно так же, как и на другом языке. Использование IndexError - глупая идея (безграмотно, но в то же время претенциозно).

oleksii.animation

Июль 18, 2016 08:29:21

я конечно понимаю что что может быть и такой вариант без рекурсий, но хотелось добавить какие то именно Python конструкции, это все ради тренировки.

 import random
numbers = [random.randint(0,100) for x in range(100)]
n = 1
while n < len(numbers):
     for i in range(len(numbers)-n):
          if numbers[i] > numbers[i+1]:
              numbers[i],numbers[i+1] = numbers[i+1],numbers[i]
     n += 1
print(numbers)

py.user.next

Июль 18, 2016 11:51:27

Исключение IndexError вообще никогда возникать не должно, поэтому если ты его отлавливаешь, то уже что-то неправильно, значит.
Выбери другое задание, никак ты не напишешь пузырьковую сортировку по-питоновски, она практически на всех языках одинаковая и везде только учебная (в реале не применяется).

doza_and

Июль 18, 2016 20:29:01

py.user.next
и везде только учебная (в реале не применяется).

Не совсем так. На последовательностях размерности от 2 до 6-7 элементов она выигрывает в производительности у других способов сортировки. Поэтому и в реальных проектах используется.

JOHN_16

Июль 18, 2016 22:54:31

doza_and
На последовательностях размерности от 2 до 6-7 элементов

это что значит, например список int длиной 6 элементов ?

py.user.next

Июль 19, 2016 02:39:08

JOHN_16
это что значит, например список int длиной 6 элементов ?

В qsort() у gcc было такое, если длина массива до десяти элементов, то применяется не quicksort, а простая квадратная сортировка. А ещё goto потом делается в конец функции, там вообще много goto.

doza_and
На последовательностях размерности от 2 до 6-7 элементов она выигрывает в производительности у других способов сортировки.

На счёт других не знаю. Там, наверное, не очень важно, какой алгоритм. Если shellsort взять, то у неё сложность O(n^1.2), почему бы её не заюзать?

Вот с вики

Эффективность сортировки Шелла, — в определённых случаях, — обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, — например, пузырьковой, — каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла — это число может быть больше).

oleksii.animation

Июль 19, 2016 08:00:55

вот еще вариант с enumerate и откусыванием списка

 import random
numbers = [random.randint(0,10) for x in range(0,10)]
counter = 1
while counter < len(numbers):
    for i in [x[0] for x in enumerate(numbers[:-1])]:
        if numbers[i] > numbers[i + 1]:
            numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
    counter += 1
print(numbers)

oleksii.animation

Июль 19, 2016 08:08:57

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

= 0.37903809547424316 sec # вариант с [x for x in enumerate(numbers)]
= 0.404041051864624 sec # вариант с except IndexError:
= 0.20402097702026367 sec # классика

 import random
import time
class Time:
    def __enter__(self):
        self.start = time.time()
        return self
    def __exit__(self, *args):
        self.end = time.time()
        print(' = ',self.end - self.start,'sec')
with Time() as t:
    numbers = [random.randint(0,10) for x in range(0,1000)]
    counter = 1
    while counter < len(numbers):
        for i in [x[0] for x in enumerate(numbers[:-1])]:
            if numbers[i] > numbers[i + 1]:
                numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
        counter += 1
    print(numbers)
with Time() as t:
    numbers = [random.randint(0, 100) for x in range(1, 1000)]
    def xsort(numbers):
        counter = 0
        for i in numbers:
            try:
                if numbers[counter] > numbers[counter + 1]:
                    numbers[counter], numbers[counter + 1] = numbers[counter + 1], numbers[counter]
                counter = counter + 1
            except IndexError:
                counter = 0
                try:
                    for i in numbers:
                        null = numbers[counter + 1]
                        counter = counter + 1
                        if i > null:
                            xsort(numbers)
                except IndexError:
                    return numbers
    xsort(numbers)
    print(numbers)
with Time() as t:
    numbers = [random.randint(0, 100) for x in range(1000)]
    n = 1
    while n < len(numbers):
        for i in range(len(numbers) - n):
            if numbers[i] > numbers[i + 1]:
                numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
        n += 1
    print(numbers)

py.user.next

Июль 19, 2016 13:35:45

Для замеров используй модуль timeit. Его можно запускать даже просто из командной строки.