Быстрая сортировка

@eugeny1984 · Регистрация: 10.04.2015

Студворк — интернет-сервис помощи студентам

Добрый день, друзья! Написал быструю сортировку, но выдает ошибку, связанную с рекурсией. Ума не приложу, как исправить, чтобы сортировал.
File "C:/Users/sokes/AppData/Roaming/JetBrains/PyCharmCE2020.1/scratches/fds.py", line 3, in QuickSort
if first >= last:
RecursionError: maximum recursion depth exceeded in comparison

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def QuickSort(a, first, last):
    if first >= last:
        return 
    m = 10
    b, e = first, last
    while b <= e:
        while a [b] < m:
            b = b +1
        while a [e] > m:
            e = e -1
        if b <= e :
            a[b], a[e] = a [e], a [b]
            b, e = b +1, e -1
    QuickSort(a, first, e)
    QuickSort(a, b, last)
    return print(a)
 
a = [3,1,2,10,4,0]
QuickSort(a,0, len(a)-1)

@Garry Galler · 10.10.2020, 13:23

Сообщение от eugeny1984

Написал быструю сортировку,

Зачем?

Сообщение от eugeny1984

но выдает ошибку, связанную с рекурсией.

В Python стек рекурсии ограничен и используется только для неглубоких объектов типа деревьев или вложенных списков.

@eugeny1984 · 10.10.2020, 13:24 **[ТС]**

Garry Galler, Подскажите, пожалуйста, А можно как-то исправить, чтобы без рекурсии или по другому?

@Garry Galler · 10.10.2020, 13:26

Сообщение от eugeny1984

А можно как-то исправить,

Можно. Но это бессмысленно. Просто увеличь стек рекурсии.
Сортировка будет жрать кучу ОЗУ - зато ты сдашь бессмысленный зачет.

@eugeny1984 · 10.10.2020, 13:28 **[ТС]**

Garry Galler, Видимо вы не знаете, как исправить, иначе бы написали, но могу ошибаться.

@Garry Galler · 10.10.2020, 13:32

Сообщение от eugeny1984

иначе бы написали,

Конечно.

@eugeny1984 · 10.10.2020, 13:35 **[ТС]**

Garry Galler, Вот с этого и надо было начинать

@КулХацкеръ · 10.10.2020, 13:52

Python
1
m = 10

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

Добавлено через 2 минуты
Может, так?

Python
1
2
    b, e = first, last
    m = a[(b + e)//2]

Вместо:

Python
1
2
    m = 10
    b, e = first, last

@eugeny1984 · 10.10.2020, 13:56 **[ТС]**

КулХацкеръ, да так быстрей работать в теории должно. Но на практике, там ошибка с рекурсией выходит. Как-то можно исправить, подскажите, пожалуйста?

@Garry Galler · 10.10.2020, 14:27

Сообщение от eugeny1984

Вот с этого и надо было начинать

Ха-ха. С чего начинать?

Запомни: когда я даю совет - я надеюсь (очень надеюсь), что люди умеют гуглить.
google: python reqcursion limit
всегда приводит к

Python
1
2
import sys
sys.setrecursionlimit(свой лимит) # по умолчанию 3000

Но чуда не случилось. Ты даже не попытался сделать элементарный запрос в поисковик.

Кстати, я запустил правильно реализованный quicksort и мне хватило для миллионного списка глубины стека всего в 80
sys.setrecursionlimit(80)

@eugeny1984 · 10.10.2020, 14:32 **[ТС]**

Garry Galler, Я гуглил, но не нашел как исправить это. Жаль, что вы тоже не знаете.

@iSmokeJC · 10.10.2020, 14:45

Не по теме:

Garry Galler, взятие на слабО детектед

@Garry Galler · 10.10.2020, 14:52

Сообщение от eugeny1984

Жаль, что вы тоже не знаете.

Чего не знаю? У меня все отлично работает. А как исправить свою проблему - ну за тебя я это делать не буду. Поэтому просто загляни в википедию - там есть правильный вариант quicksort с разбиением Хоара.
И на будущее - тут тебе никто ничего не должен. А вот ты - создавший тему - должен всем.

@Catstail · 10.10.2020, 16:19

eugeny1984, на, страдалец, свой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def QuickSort(a, first, last):
    if first >= last:
        return 
    m = a[(last+first)//2]
    b, e = first, last
    while b <= e:
        while a [b] < m:
            b = b +1
        while a [e] > m:
            e = e -1
        if b <= e :
            a[b], a[e] = a [e], a [b]
            b, e = b +1, e -1
    QuickSort(a, first, e)
    QuickSort(a, b, last)
 
a = [3,1,2,10,4,0]
QuickSort(a,0, len(a)-1)
print(a)

И слушай, когда тебе советуют. Разделяющий элмент нужно выбирать на каждой итерации. Поэтому

Python
1
m=10

это глупость. Как и последний оператор

Python
1
return print(a)

Добавлено через 8 минут

Сообщение от eugeny1984

КулХацкеръ, да так быстрей работать в теории должно.

-

@eugeny1984 · 10.10.2020, 16:20 **[ТС]**

Catstail, Профи, просто нет слов!

@Catstail · 10.10.2020, 16:41

Не по теме:

eugeny1984, задача-то - не особо сложная...

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

Быстрая сортировка

Решение

Решение

@eugeny1984 3 / 3 / 0 Регистрация: 10.04.2015 Сообщений: 233
	10.10.2020, 13:24 [ТС]
	Garry Galler, Подскажите, пожалуйста, А можно как-то исправить, чтобы без рекурсии или по другому? 0

@eugeny1984 3 / 3 / 0 Регистрация: 10.04.2015 Сообщений: 233
	10.10.2020, 13:28 [ТС]
	Garry Galler, Видимо вы не знаете, как исправить, иначе бы написали, но могу ошибаться. 0

@eugeny1984 3 / 3 / 0 Регистрация: 10.04.2015 Сообщений: 233
	10.10.2020, 13:35 [ТС]
	Garry Galler, Вот с этого и надо было начинать 0

@eugeny1984 3 / 3 / 0 Регистрация: 10.04.2015 Сообщений: 233
	10.10.2020, 13:56 [ТС]
	КулХацкеръ, да так быстрей работать в теории должно. Но на практике, там ошибка с рекурсией выходит. Как-то можно исправить, подскажите, пожалуйста? 0

@eugeny1984 3 / 3 / 0 Регистрация: 10.04.2015 Сообщений: 233
	10.10.2020, 14:32 [ТС]
	Garry Galler, Я гуглил, но не нашел как исправить это. Жаль, что вы тоже не знаете. 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	10.10.2020, 14:45
	Не по теме: Garry Galler, взятие на слабО детектед 0

@eugeny1984 3 / 3 / 0 Регистрация: 10.04.2015 Сообщений: 233
	10.10.2020, 16:20 [ТС]
	Catstail, Профи, просто нет слов! 0

@Catstail
	10.10.2020, 16:41
	Не по теме: eugeny1984, задача-то - не особо сложная... 0