Реализация быстрой сортировки

@PG94 · Регистрация: 15.01.2012

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

Добрый вечер. Есть код, который на мой взгляд должен работать верно:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def qsort(list, left, right):
    l, r = left, right
    mid = list[(right - left + 1)//2]
    while l < r:
        print("loop")
        while list[l] < mid:
            l+=1
        while list[r] > mid:
            r-=1
        if l <= r:
            if list[l] > list[r]:
                list[l], list[r] = list[r], list[l]
            l+=1
            r-=1
    if l<right:
        qsort(list,l,right)
    if r>left:
        qsort(list,left,r)

Однако, например на входе [-1,0,1,1,0,-1], рекурсия не останавливается. Подскажите, в чём проблема?
Спасибо.

@Zarex · 26.03.2014, 22:59

я не шарю в алгоритмах, но для начала я бы загуглил и сунулся бы сюда и сюда

@ilnurgi · 27.03.2014, 07:40

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

mid = list[(right - left + 1)//2]

скажите пожалуйста, какую роль здесь играет list?

@dondublon · 27.03.2014, 12:25

Если отсортировать надо числа, то есть numpy.sort.

@PG94 · 27.03.2014, 12:51 **[ТС]**

Спасибо, что откликнулись.
Внесу уточнения:
1) Алгоритм нужно написать собственноручно: без исп. библиотек
2) list - это список, его и нужно отсортировать
3) Другие реализации я видел, но мне важно найти ошибку именно в этом варианте
4) Ограничений на тип элементов вообще говоря нет. Сейчас нужно, чтобы хотя бы работало для чисел.

@alex925 · 27.03.2014, 12:53

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

2) list - это список, его и нужно отсортировать

list это зарезервированное слово и его нельзя использовать как переменную

@PG94 · 27.03.2014, 20:44 **[ТС]**

Проблема не в этом.

@alex925 · 27.03.2014, 22:36

PG94, я не утверждал, что проблема в этом, но это недопустимая ошибка, которая в дальнейшем может привести к неожиданному для вас результату.
Вам Zarex, подкинул 2 толковые ссылки, с помощью которых можно разобраться в проблеме, разбирайтесь.

@Zarex · 27.03.2014, 23:35

всё я решил - надо из управдомов переквалифицироваться в программисты

PG94, нашёл ваш алгоритм здесь. Кое-что поменял и вуаля:

Кликните здесь для просмотра всего текста

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def qsort(list, left, right):
    l, r = left, right
    mid = list[(right - left + 1)//2]
    while l <= r:
        while list[l] < mid:
            l+=1
        while list[r] > mid:
            r-=1
        if l <= r:
            if list[l] > list[r]:
                list[l], list[r] = list[r], list[l]
            l+=1
            r-=1
    if left<r:
        qsort(list,left,r)
    if right>l:
        qsort(list,l,right-l)
    return list

@PG94 · 28.03.2014, 11:03 **[ТС]**

Спасибо, ваш код не запускал, исправил свой: поправил вычисление mid.

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@Zarex 55 / 55 / 16 Регистрация: 25.03.2013 Сообщений: 178
	26.03.2014, 22:59
	я не шарю в алгоритмах, но для начала я бы загуглил и сунулся бы сюда и сюда 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	27.03.2014, 12:25
	Если отсортировать надо числа, то есть numpy.sort. 0

@PG94 2 / 2 / 0 Регистрация: 15.01.2012 Сообщений: 181
	27.03.2014, 12:51 [ТС]
	Спасибо, что откликнулись. Внесу уточнения: 1) Алгоритм нужно написать собственноручно: без исп. библиотек 2) list - это список, его и нужно отсортировать 3) Другие реализации я видел, но мне важно найти ошибку именно в этом варианте 4) Ограничений на тип элементов вообще говоря нет. Сейчас нужно, чтобы хотя бы работало для чисел. 0

@PG94 2 / 2 / 0 Регистрация: 15.01.2012 Сообщений: 181
	27.03.2014, 20:44 [ТС]
	Проблема не в этом. 0

@alex925 2742 / 2341 / 620 Регистрация: 19.03.2012 Сообщений: 8,830
	27.03.2014, 22:36
	PG94, я не утверждал, что проблема в этом, но это недопустимая ошибка, которая в дальнейшем может привести к неожиданному для вас результату. Вам Zarex, подкинул 2 толковые ссылки, с помощью которых можно разобраться в проблеме, разбирайтесь. 0

@PG94 2 / 2 / 0 Регистрация: 15.01.2012 Сообщений: 181
	28.03.2014, 11:03 [ТС]
	Спасибо, ваш код не запускал, исправил свой: поправил вычисление mid. 0