Решение задачи Partition с Яндекс Контест

Без пояснения   Просмотров: 1441

Базовым алгоритмом для быстрой сортировки является алгоритм partition, который разбивает набор элементов на две части относительно некоторого предиката.
По сути элементы массива просто меняются местами так, что левее некоторой точки в нем после этой операции лежат элементы, удовлетворяющие заданному предикату, а справа — не удовлетворяющие ему.
В частности, при сортировке можно использовать предикат «меньше опорного», что при оптимальном выборе опорного элемента может разбить массив на две примерно равные части.

В качестве первого шага для написания быстрой сортировки Вам предстоит написать алгоритм partition.

Код 

n = int(input())
a = list(map(int, input().split()))
x = int(input())
less, big = 0, 0
for i in a:
    if x > i:
        less += 1
    else:
        big += 1
print(less)
print(big)

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp