Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 01.11.2020, 23:04   #1
Smuchok
Новичок
Джуниор
 
Регистрация: 01.11.2020
Сообщений: 1
Вопрос QuickSort с опорным первым элементом

У меня есть задание подсчитать счетчиком count в быстрой сортировке, НО опорный элемент должен быть первым, а не последним, как обычно. Счетчик count должен выдать в конце число 20.
К тому же была еще подсказка от преподавателя:
Цитата:
Эта задача отличается тем, что в качестве опорного элемента в процедуре Partition всегда избирается первый элемент текущего массива.Для этого достаточно поменять местами первый и последний элементы и вызвать основную версию процедуры Partition, которая работает с последним элементом в качестве опорного.
Мой код сортирует, но выдает значение счетчика 22, вместо 20. Что я сделал не так?

Код:
def Partition(A, p, r, count):
    i= p
    x= A[p]
    #print(' p=',p, ' r=',r, ' i=',i, ' x=',x, sep='')
    for j in range(p+1, r+1):
        count= count + 1
        if A[j]<=x:
            i= i+1
            A[i], A[j]= A[j], A[i]
    
    A[i], A[p]= A[p], A[i]
    return i, count

def QuickSort(A, p, r, count):
    if p<r:
        q, count= Partition(A, p, r, count)
        count= QuickSort(A, p, q-1, count)[1]
        count= QuickSort(A, q+1, r, count)[1]
    return A, count

A= [6, 10, 2, 4, 1, 3, 5, 7, 9, 8]
print(A)

p= 0
r= len(A)-1
print(QuickSort(A, p, r, 0))    #Должен быть отсортированный список и число 20 (count)
Smuchok вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Массив. Получить сумму всех элементов, следующих за первым таким элементом А Rarrih Общие вопросы Delphi 5 14.01.2018 18:24
Матрица, каждой строке найти макс. и мин. элементы и поменять их с первым и последним элементом строки (Паскаль) тина222 Помощь студентам 0 02.11.2011 22:01
в массиве все максимальные элементы заменить первым элементом, а все минимальные элементы заменить последним элементом Валерия2701 Паскаль, Turbo Pascal, PascalABC.NET 1 12.10.2011 15:49