Алгоритм сортировки массивов уникальных чисел

Question

Алгоритм предназначен для сортировки массивов длиной n, состоящих из уникальных чисел в диапазоне от 0 до n-1. Иными словами, массив должен содержать целые положительные числа от 0 до n-1, перемешанные как угодно. Например, если n = 8, то массив может быть таким:

Массив длиной 8 элементов
3 1 0 2 6 5 4 7 # В массиве содержатся все целые числа в диапазоне от 0 до 7. Суть алгоритма: исходный массив разделяется на блоки так, чтобы каждый блок можно было отсортировать и при слиянии отсортированных блоков получился отсортированный массив. Менять блоки местами нельзя.

Делим исходный массив на блоки, которые можно отсортировать:
Так нельзя:после сортировки блоков их не объединить в отсортированный массив. 3 1 | 0 2 | 6 | 5 4 | 7

И так нельзя.
3 | 1 0 2 | 6 5 4 7

3 1 0 2 | 6 5 4 | 7 # А вот такое деление - в самый раз!

Сортируем блоки:
0 1 2 3 | 4 5 6 | 7

Объединяем блоки:
0 1 2 3 4 5 6 7

Получили отсортированный массив!
Алгоритм сортировки состоит из трёх шагов:

Разбить исходную последовательность на k блоков. Блоки могут иметь разные размеры. Первый блок обязательно должен содержать 0. Если длина первого блока — r элементов, то максимальным значением в первом блоке должно быть число r - 1. А следующий блок (если он вообще будет) должен содержать число r. Этот принцип должен соблюдаться и в последующих блоках. Отсортировать каждый из блоков. Объединить блоки в единый массив. Такая сортировка выгодна в том случае, если разбить исходный массив на максимально возможное число блоков.

В этом задании вам предстоит реализовать только первый шаг: разбить массив на блоки и вернуть их количество.

Задание: написать программу, которая получает на вход массив и возвращает максимальное число блоков, на которое можно разбить этот массив так, чтобы сортировка отработала корректно.

Ещё один пример:

3 2 0 1 4 6 5 Минимальный размер первого блока — 4.

Если взять лишь первые два элемента, то отсортированная последовательность будет начинаться с двойки, а это неправильно. Если взять первые три элемента, то последовательность будет начинаться с нуля, но после него сразу же пойдёт двойка. Опять нехорошо.

А вот первые четыре элемента гарантируют, что первая часть результирующего массива будет корректной.

Четвёрку можно взять как отдельный блок из одного элемента.

Последние два элемента составят третий блок. Таким образом:

первый блок: 3, 2, 0, 1; второй блок: 4; третий блок: 6, 5. В этом примере ответ равен 3: чтобы сортировка блоками отработала корректно, полученный массив можно разделить максимум на три блока.

Формат ввода В первой строке задано n — количество чисел для сортировки (n ≤ 1000). В следующей строке записаны числа от 0 до n - 1, которые надо разбить на блоки.

Формат вывода Выведите максимальное число блоков, на которое можно разбить данные при использовании метода частичной сортировки. Вот мой нерабочий код:

def sorting_blokcs(r):
    
    blok1 = []
    blok2 = []
    blok3 = []
    blok_count  = 0
    
    for i, item in enumerate(r):
        while (0 and 1) not in blok1:
            blok1.append(r[i])
            r.pop(i)
   #         print(blok1, r)
        if item == sum(blok1) or item == sum(blok1) + r[i-1]:
            blok2.append(r[i])
            r.pop(i)
       #     print(blok2, r)
   
        if len(r) > 1:
            blok3.append(r[i: len(r) // 2])
            blok3.append(r[len(r) // 2: len(r)])
            r.pop(i)    
            #print(blok3, r)
        if len(r) == 1:
           blok1.append(r[i])
           r.pop(i)
 #          print(blok1, r)
        if blok1:
           blok_count += 1
        if blok2:
           blok_count += len(blok2)
        if blok3:
           blok_count += len(blok3)
    #       print(blok1, blok2, blok3, r)        
        return blok_count
        #blok1, blok2, blok3
            
            
if __name__ == '__main__':
    u = int(input())
    r = [int(i) for i in input().split()]
    print(sorting_blokcs(r))

Answer 1

Конец блока - это позиция самого большого элемента в нём. То есть перебираем элементы слева направо, сохраняя самый большой элемент. Если он равен текущей позиции, то это конец блока. Инкрементируем счётчик блоков и переходим к следующему элементу массива и к новому блоку.

using System;
static class Programm {
    static void Main() {
        var ia = new int[] { 3, 1, 0, 2, 6, 5, 4, 7 };
        int nob = 0; int mx = 0;
        for (int i = 0; i < ia.Length; i++) {
            if (ia[i] > mx) mx = ia[i];
            if (mx == i) nob++;
        }
        Console.WriteLine(nob.ToString());
    }
}

Тоже взял идею у Станислава.

Answer 2

Вы не задали вопрос в вашем вопросе. Отвечать мне нечего. Но задача интересная:

a - список чисел.
i - текущая длина префикса списка.
flags - для всех элементов a[:i + 1] установлены флаги.
below - количество чисел в первой i + 1 ячейке списка a, которые меньше или равны i (sum(a[:i + 1] <= i)).
blocks - число блоков в a[:i]. Если below равен i + 1 можно объявить новый блок.

Первоначально below = 0. В цикле с приходом нового числа ai значение below может увеличится на единицу двумя способами: если ai < i и если flags[i] - истина:

input()  # skip n
a = tuple(map(int, input().split()))
flags = [False] * len(a)

blocks = 0
below = 0
for i, ai in enumerate(a):
    flags[ai] = True
    if ai < i:
        below += 1
    if flags[i]:
        below += 1
    if below == i + 1:
        blocks += 1

print(blocks)

P.S. Предыдущий код слишком сложен. Вот, украдено из ответа rotabor: блок объявляется когда максимум префикса равен его длине. Всё:

input()  # skip n
blocks = 0
max_so_far = 0
for i, ai in enumerate(map(int, input().split())):
    max_so_far = max(max_so_far, ai)
    if max_so_far == i:
        blocks += 1
print(blocks)

БЛОГ НА HUSL

Алгоритм сортировки массивов уникальных чисел

Ответы (2 шт):