Наглядный пример сортировки чисел методом Черпака?

using System;
using System.Collections.Generic;
using System.Text;

namespace BucketSort
{
class BucketSort
{
private void Sort(int[] integers)
{
//Verify input
if (integers == null || integers.Length == 0)
return;

//Find the maximum and minimum values in the array
int maxValue = integers[0]; //start with first element
int minValue = integers[0];

//Note: start from index 1
for (int i = 1; i < integers.Length; i++)
{
if (integers > maxValue)
maxValue = integers;

if (integers < minValue)
minValue = integers;
}

//Create a temporary “bucket” to store the values in order
//each value will be stored in its corresponding index
//scooting everything over to the left as much as possible (minValue)
//e.g. 34 => index at 34 – minValue
List<int>[] bucket = new List<int>[maxValue — minValue + 1];

//Initialize the bucket
for (int i = 0; i < bucket.Length; i++)
{
bucket = new List<int>();
}

//Move items to bucket
for (int i = 0; i < integers.Length; i++)
{
bucket[integers – minValue].Add(integers);
}

//Move items in the bucket back to the original array in order
int k = 0; //index for original array
for (int i = 0; i < bucket.Length; i++)
{
if (bucket.Count > 0)
{
for (int j = 0; j < bucket.Count; j++)
{
integers[k] = bucket[j];
k++;
}
}
}
}
}
}

Посмотреть тему на форуме

Данная статья раскрывает некоторые тонкости алгоритма одного из элементов форматирования исходных текстов программ. Рассчитана на широкий круг программистов и не требует специальных знаний.

Автор:  Utkin www.programmersforum.ru

Краткий экскурс…

Прежде всего, как советуют классики, нужно определиться со структурами данных, в которых будет проводиться основная работа по форматированию. Большинство языков программирования имеют поддержку массивов различных типов данных. Поэтому будем представлять входящий текст программы как массив строк. Теперь рассмотрим вопрос о представлении отступа. В зависимости от реализации это может быть задание отступа отрисовки символов в компоненте вывода текста на экран, либо задание символа табуляции (в случае если транслятор позволяет использовать табуляцию в программах), либо просто определенное количество символов пробела в качестве заменителя символа табуляции. Теперь о самих отступах – все, что нам требуется, это либо добавление в начало строки определенного символа (или группы символов, в случае если символ табуляции будет заменен на пробелы), либо передача информации компоненту отрисовки текста программы о величине отступа от левого края для конкретной строки. Важное условие – величина отступа меняется в зависимости от уровня вложенности логических блоков программы.

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

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

Таблица. Условное представление логических блоков:

В общем, имеющейся информации уже достаточно для построения алгоритма установки отступов для логических блоков программы.

Итак, приступим

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

1. Получим очередную строку программы из массива строк.

2. Удалим из левой ее части все пробелы и символы табуляции (если они там имеются).

3. Получим первую лексему языка программирования из нашей строки. Это может быть символ или ключевое слово.

4. Сверим наше слово с маркерами

5. Если слово является маркером начала логического блока, то

5.1. В зависимости от особенностей реализации – добавим в начало строки символы табуляции (или  символы пробела) либо передадим информацию в компонент по отрисовке строк программы в соответствии с текущим отступом.

5.2. Увеличим отступ на величину шага отступа.

5.3. Закончим текущую итерацию цикла

6. Если слово является маркером конца логического блока, то

6.1. Если разница между отступом и шагом отступа будет больше или равно нулю, то уменьшим отступ на величину шага отступа.

7. В зависимости от особенностей реализации – добавим в начало строки символы табуляции (или символы пробела) либо передадим информацию в компонент по отрисовке строк программы в соответствии с текущим отступом.

Некоторые комментарии по пунктам алгоритма*

Второй пункт алгоритма нацелен на удаление существовавшего до этого форматирования. Программист или какая–либо другая программа могли использовать другие принципы форматирования кода, и если бы данного пункта не было, то возникла–бы путаница: отступы наложились друг на друга и результат отличался от ожидаемого.

Реализация третьего пункта зависит от конкретного языка программирования программу, на котором предстоит форматировать. Для многих языков программирования лексему можно определить как последовательность символов (или одиночный символ) отделенный от другой лексемы разделителем, в качестве которого могут выступать пробелы, символы табуляции и другие лексемы – спецсимволы, скобки т.д.

Пункты 5 и 6 могут быть изменены в зависимости от языка программирования. Это связано с тем, что некоторые из языков воспринимают регистр введенных лексем, а некоторые его игнорируют. Если программа, которую нужно форматировать составлена на языке программирования не чувствительного к регистру, то перед проверкой первой лексемы на равенство маркерам начала и конца логического блока их необходимо преобразовать к одному регистру.

Пункт 5.3 предназначен для того, чтобы сразу не сдвигался маркер начала логического блока.

Пункт 6.1 нужен для того, чтобы отступ не получил отрицательного значения (не стал выступом). По сути, программа рассматривается как некий поток команд для стека. Итак, перед нами стек – это текущая величина отступа. Каждый маркер начала логического блока увеличивает его на величину шага отступа, а каждый маркер конца логического блока уменьшает его на ту же величину. Т.е. пункт 6.1. ответственен за защиту от опустошения стека: нельзя брать из стека больше, чем там имеется. В тоже время как в самой программе такие ошибки вполне возможны – к примеру, программист при наборе программы мог забыть поставить одну (или несколько) из открывающих операторных скобок.

* такой способ весьма прост, но имеет один недостаток – его нельзя использовать для языков

программирования, в которых отступы влияют на процесс вычисления программы – это Питон,

некоторые версии Хаскела и т.д.

Заключение

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

Реализация рассмотренного алгоритма на Дельфи 7 прилагается в ресурсах к статье на http://www.programmersforum.ru в разделе «Журнал клуба программистов.  Первый выпуск».

Статья из первого выпуска “журнала ПРОграммистов”.
Скачать этот номер можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Установка отступов для логических блоков программы

Предположим, у вас есть картинка, и еще  много других.  Как же их сравнить между собой (например, для обхода капчи)?

(читать всё…)

(читать всё…)