Запуск последовательности

В информатике прогон последовательности — это неубывающий диапазон последовательности, который не может быть расширен. Количество запусков последовательности — это количество возрастающих подпоследовательностей последовательности. Это мера предварительной сортировки , которая, в частности, определяет, сколько подпоследовательностей необходимо объединить для сортировки последовательности.

Определение

Позволять $X=\langle x_{1},\dots ,x_{n}\rangle$ быть последовательностью элементов из полностью упорядоченного множества . Пробег  $X$ — максимальная возрастающая последовательность $\langle x_{i},x_{i+1},\dots ,x_{j-1},x_{j}\rangle$ . То есть, $x_{i-1}>x_{i}$ и $x_{j}>x_{j+1}$ ^{[ нужны разъяснения ]} предполагая, что $x_{i-1}$ и $x_{j+1}$ существует. Например, если $n$ — натуральное число , последовательность $\langle n+1,n+2,\dots ,2n,1,2,\dots ,n\rangle$ имеет два пробега $\langle n+1,\dots ,2n\rangle$ и $\langle 1,\dots ,n\rangle$ .

Позволять ${\mathtt {runs}}(X)$ определяться как количество позиций $i$ такой, что $1\leq i<n$ и $x_{i+1}<x_{i}$ . Это эквивалентно определяется как количество запусков $X$ минус один. Это определение гарантирует, что ${\mathtt {runs}}(\langle 1,2,\dots ,n\rangle )=0$ , то есть ${\mathtt {runs}}(X)=0$ тогда и только тогда, когда последовательность $X$ сортируется. В качестве другого примера: ${\mathtt {runs}}(\langle n,n-1,\dots ,1\rangle )=n-1$ и ${\mathtt {runs}}(\langle 2,1,4,3,\dots ,2n,2n-1\rangle )=n$ .

Сортировка последовательностей с небольшим количеством запусков

Функция ${\mathtt {runs}}$ является мерой предварительной сортировки . Естественная слиянием сортировка ${\mathtt {runs}}$ -оптимально . То есть, если известно, что последовательность имеет небольшое количество повторов, ее можно эффективно отсортировать, используя естественную сортировку слиянием.

Длинные пробежки

Длинный период определяется аналогично бегу, за исключением того, что последовательность может быть как неубывающей, так и невозрастающей. Количество длинных прогонов не является мерой предварительной сортировки. Последовательность с небольшим количеством длинных серий можно эффективно отсортировать, сначала обращая уменьшающиеся серии, а затем используя естественную сортировку слиянием.

Ссылки

Пауэрс, Дэвид М.В.; МакМахон, Грэм Б. (1983). «Сборник интересных программ на прологе». Технический отчет DCS 8313 (Отчет). Департамент компьютерных наук Университета Нового Южного Уэльса.
Маннила, Х. (1985). «Меры предварительной сортировки и оптимальные алгоритмы сортировки». IEEE Транс. Вычислить. (С-34): 318–325. дои : 10.1109/TC.1985.5009382 .