Простые методы для повышения уровня безопасности

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

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

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

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

<?php
rand(int $min, int $max);
mt_rand(int $min, int $max);
str_shuffle($str);
uniqid($prefix, more_entropy=);
?>

Две функции rand() и mt_rand() наиболее часто используемые функции для генерации случайных чисел в PHP. Функция rand(), более старая версия генератора, вытесняется mt_rand(), которая быстрее, более надежная и может работать с максимально большим значением типа integer на большинстве платформ. Функция str_shuffle() не совсем точно отражает сущность генератора случайных чисел. Она смешивает строку, которую получает в качестве аргумента.

<?php
//Пример использования mt_rand()
print mt_rand();//По умолчанию
echo "<br />";
print mt_rand(0, 20);//Выводит случайное целое между 0 и 20
echo "<br />";
//Примеры использования rand()
print rand();//По умолчанию
echo "<br />";
print rand(0, 25);//Выводит случайное целое между 0 и 25
echo "<br />";
//Пример использования str_shuffle()
$string = 'abcefghijklmnopqrstuvwxyz';
print str_shuffle($string);//Смешение строки $string
?>

Функции rand() и mt_rand() принимают два параметра, где $min является наименьшим целым, с котрого начинается диапазон случайных чисел, а $max представляет максимальное число, которое ограничивает диапазон случайных чисел сверху. Функция str_shuffle получает один параметр строку и выводит ее смешанный вариант. Функция str_shuffle выполняет действия, похожие на перемешивание колоды карт.

Также для генерирования случайных уникальных значений широко используется функция uniqid(). Функция uniqid() генерирует уникальный идентификатор на основе текущего времени, выраженного в микросекундах (с помощью php.net). Использование данной функции очень удобно при создании идентификаторов сессий и ключей форм.

<?php
//Пример использования uniqid()
print uniqid();//По умолчанию
echo "<br />";
print uniqid("NETTUTS", TRUE);//Добавлен дополнительный префикс и установлено значение TRUE для more_entropy 
?>

Функция uniqid() принимает два параметра. Первый добавляет префикс к результату, а второй, при значении TRUE указывает на то, что нужно сделать конец значения более неопределенным.

Генерирование случайного пароля
Существует огромное количество примеров в интернете, которые демонстрируют генерацию случайных паролей и все отлично работают. Для чего нужно генерировать случайный пароль? Ответ очень прост. Нельзя полагаться на пользователя, что он придумает достаточно надежный пароль. Генерирование случайного пароля также необходимо при регистрации пользователя или в случаях, когда пользователь теряет свой пароль. Такая практика обеспечивает получение надежного пароля сразу с самого знакомства пользователя с вашим сайтом, а также сокращает некоторое количество строк кода, когда пользователю нужно снова получить доступ.

Несколько примеров.

Пример 1

<?php
//Простая функция, которая генерирует случайный пароль
function randompassword($count){
$pass = str_shuffle('abcefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890@#%$*');
return substr($pass,3,$count);//Возвращаем пароль
}
?>

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

Пример 2

<?php
//Другой пример создания случайного пароля
function anorandpass($count) {
$m_rand = mt_rand(); //генерируем случайное целое
$u_id = uniqid("MNO!@#$%^&*=+XYZ", TRUE);//создаем уникальный идентификатор с префиксом, постфиксом и повышенной энтропией
$combine = $m_rand . $u_id;// Комбинируем переменные для формирования строки
$new = str_shuffle($combine);//смешиваем строку
return substr($new, 2, $count);//возвращаем пароль
}
print anorandpass(8);
?>

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

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

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

Почему и как?
Наблюдения показывают, что конечный пользователь старается обеспечить себе как можно более простой способ обеспечения безопасности Обычно используются пароли, которые легко запомнить, и даже используется один пароль для доступа к нескольким сайтам. Легко запоминающиеся пароли обычно представляют собой общеупотребительные слова или некоторые виды значений (например 12345, QWERTY). Разработчики часто смеются над такой практикой, существенно изменить положение в данной ситуации нет возможности.

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

1. Соединение с базой
Здесь описана структура таблицы SQL, которую мы будем использовать.

CREATE TABLE IF NOT EXISTS `users` (
`usr_id` int(11) NOT NULL AUTO_INCREMENT,
`usr_name` varchar(24) NOT NULL,
`usr_pass` varchar(32) NOT NULL,
`usr_email` varchar(255) NOT NULL,
`usr_salt` varchar(255) NOT NULL,
PRIMARY KEY (`usr_id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 ;

<?php
/*db_config.php*/
//Конфигурация базы данных
$db_host ="localhost" ; //располагается на том же сервере, что и сайт
$db_name = "thedbname"; //имя таблицы базы данных
$db_usr = "username"; //имя пользователя базы данных
$db_pass = "password";//пароль пользователя
//Устанавливаем соединение с MySQL и выбираем базу данных для использования
mysql_connect($db_host, $db_usr, $db_pass) or die("MySQL Error: " . mysql_error());
mysql_select_db($db_name) or die("MySQL Error: " . mysql_error());
?>

2. Файл регистрации
<?php
/*registration.php*/
//требуется db_config.php
require ('db_config.php');
//Проверяем, готовность данных в отправленной форме
if(!empty($_POST['username']) && !empty($_POST['email']) && !empty($_POST['password'])) {
//Готовим данные
$username = mysql_real_escape_string($_POST['username']);
$email = mysql_real_escape_string($_POST['email']);
$password = mysql_real_escape_string($_POST['password']);
//Генерируем надежный уникальный шум
$salt_gen = uniqid(mt_rand());
//Комбинируем email, пароль и шум вместе
$combine = $email . $password . $salt_gen;
//md5 вычисляет хэш комбинированного пароля * Примечание: md5 используется как пример
$newpassword = md5($combine);
//Вставляем значения в базу данных
$registerquery = mysql_query("INSERT INTO users (usr_name, usr_pass, usr_email, usr_salt) VALUES ('".$username."', '".$newpassword."', '".$email."', '".$salt_gen."')") or die("MySQL Error: ".mysql_error());
//Обратная связь с пользователем о результате операции
if ($registerquery) {
echo '<h1>Успешно</h1>';
} else {
echo '<h1>Ошибка</h1>';
}
}
?>

Рассмотрим код PHP. Для упрощения мы включили конфигурационный файл нашей базы данных. PHP проверяет готовность данных в отправленной форме по значению переменных $_POST. Если они не пустые, то скрипт подготавливает данные для вставки их в базу. Затем генерируется шум с использованием uniqid() и mt_rand() и сохраняется в переменной $salt_gen. Далее комбинируется $password и шум. А затем вычисляется хэш для скомбинированного значения с помощью md5.

Также в комбинацию пароля и шума добавляется email пользователя. Если злодей получит доступ к базе данных и сумеет прочитать значение шума, то использование email в комбинации является дополнительным препятствием на его пути, потому что нужно дополнительно исследовать код программы. А насколько случаен и уникален email?

В оставшемся коде PHP происходит добавление данных в базу и вывод информационного сообщения для пользователя. Осталось только написать HTML файл для завершения системы.

<!DOCTYPE html>
<html>
<head>
</head>
<body>
<form action="" method="post">
<label for="username">Введите имя пользователя</label>
<input type="text" name="username" /><br />
<label for="email">Email:</label>
<input type="text" name="email" /><br />
<label for="password">Пароль:</label>
<input type="password" name="password" /><br />
<input type="submit" name="submit" value="Отправить" />
</form>
</body>
</html>

Это простая HTML форма, которая предназначена для ввода имени пользователя, email, и пароля. Ничего необычного.

3. Аутентификация пользователя
Итак, у нас есть форма регистрации пользователя, которая сохраняет данные в базе. Нужно создать страницу входа на сервер, которая будет получать данные из базы и проводить аутентификацию пользователя. PHP код:

<?php
/*login.php*/
// требуется db_config.php
require ('db_config.php');
//Проверяется, заполнены ли поля формы
if(!empty($_POST['username']) && !empty($_POST['password'])) {
//Готовятся данные
$username = mysql_real_escape_string($_POST['username']);
$password = mysql_real_escape_string($_POST['password']);
//Получаем строку, которая соответствует имени пользователя в форме
$grab_row = mysql_query("SELECT * FROM users WHERE usr_name = '".$username."'") or die ("MySQL Error: ".mysql_error());
//Если получена только одна строка
if (mysql_num_rows($grab_row) == 1) {
//Создаем массив из полей
$row = mysql_fetch_array($grab_row);
//Сохраняем шум пользователя
$salt = $row['usr_salt'];
//Сохраняем email
$email = $row['usr_email'];
//Комбинируем email, пароль, и шум
$combine = $email . $password . $salt;
//Вычисляем хэш скомбинированного значения
$auth_pass = md5($combine);
//Проверяем базу данных снова на наличие строки, соответствующей имени пользователя и скомбинированного значения
$checklogin = mysql_query("SELECT * FROM users WHERE usr_name = '".$username."' AND usr_pass = '".$auth_pass."'") or die("MySQL Error: ".mysql_error());
//Если получена только одна строка, то аутентификация прошла успешно
if(mysql_num_rows($checklogin) == 1) {
echo '<h1>Вы вошли в систему!</h1>';
} else {
echo '<h1>Извините, но вам отказано во входе в систему!</h1>';
}
} else {
echo '<h1>Ошибка базы данных!</h1>';
}
}
?>

Все что мы делаем в файле login.php - это получаем данные из формы, получаем соответствующие данные из базы, рекомбинируем строку пароля (используя email, пароль и шум) и повторно вычисляем хэш. Затем производится проверка с помощью поиска по базе данных на наличие записи соответствующей имени пользователя и хэша скомбинированного пароля. И сообщается пользователю об успехе или провале операции. А вот код HTML:

<!DOCTYPE html>
<html>
<head>
</head>
<body>
<form action="" method="post">
<label for="username">Введите имя пользователя</label>
<input type="text" name="username" /><br />
<label for="password">Введите пароль<label>
<input type="password" name="password" /><br />
<input type="submit" name="submit" value="Отправить" />
</form>
</body>
</html>

Запутывание кода PHP
Простой пример, который в тоже время достаточно сложен для анализа:

<?php $a1c0_z2='c'.$a91.'tion ';$a91="a";$vly_ti="us".'ed';$j1h_32_a=' to';$z1b_1=$a91." ";$lz32i_4="“O"."bfus";$g1k0p='que ';$lv83="t".'ec'.'hni';$lFa='i'.'s ';if($z1b_1==$a91." ")$rx_b_1='a';$glccUv=" complic".$rx_b_1.'te ';$xl1ttf='code ';$zljal1="in such a";if($z1b_1==$a91." ")$s1b_1='a';$p1x2 =" w".$s1b_1."y ";$il_7x=' '.$b1zE_.'t i'.$l1yes;$b1zE_="i";$l1yes="s";$nltotry_ws='st'.$s1b_1."n";$yl5B_='thαt ';$dlno=' not ';$m1tomanythings="under";if($s1b_1=='a')$bz_1=$s1b_1;$Ozaq="d".$bz_1."ble"";echo base64_decode("JiM4MjIwO09iZnVzY3Rpb24mIzgyMDE7aXMmIzgyMDE7YSYjODIwMTt0ZWNobmlxdWUmIzgyMDE7dXNlZCYjODIwMTt0byYjODIwMWNvbXBsaWNhdGUmIzgyMDE7Y29kZSYjODIwMTtpbiYjODIwMTtzdWNoJiM4MjAxO2EmIzgyMDE7d2F5JiM4MjAxO3RoJmFscGhhO3QmIzgyMDE7aSYjODIwMTt0JiM4MjAxO2kmIzgyMDE7bm90JiM4MjAxO3VuZGVyc3RhbmRhYmxlJnF1b3Q7");?>

Как вы можете видеть, сложно понять, что делает данный код. В нем нет ясных названий переменных, нет комментариев, нет структуры и он размещен в одной строке. Но даже если мы не можем распознать код, то машина продолжает его выполнять. Он работает. Данная одна срока сплошного хаоса просто выводит строку “Obfusction is a technique used to complicate code in such a way that i t i not understandable.” (Запутывание кода - это метод, который используется для того, чтобы усложнить понимание того, что делает код).

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

Как можно запутать код?
Существует два способа запутать код. Первый - сделать все руками. Написание запутанного кода отнимает много времени. Кроме того, даже автору очень сложно выявить и исправить ошибку в таком коде. Второй способ - использовать программное обеспечение, которое сделает это для вас.

Несколько советов по запутыванию кода
Всегда сохраняйте ясный оригинал для себя.
Чем больше случайности в вашей технике кодирования - тем лучше.
Исключайте все пробелы, где они не нужны.
Используйте коды символов и пробелов
Чем сложнее код - тем лучше
Пренебрегайте структурой там, где это не наносит вреда функционированию кода
Не используйте понятных имен переменных, классов и пространств имен
Чем меньше кода вы используете повторно, тем лучше
Запутывать или не запутывать?
Все зависит от ваших планов. Если Вы планируете продавать ваш скрипт PHP (или другое программное обеспечение) нужно его лицензировать. Это первая линия обороны, которая мешает использовать ваше программное обеспечение кому бы то нибыло не по назначению. Однако, вы можете планировать запутать часть, или весь код по другим причинам. Но если вы действительно озадачены безопасностью вашего кода, то может быть стоит использовать шифрование вместо запутывания..

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

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

SHA-1, 2, и 3
Семейство алгоритмов хэширования SHA в настоящее время пользуется популярностью, особенно SHA-1. Даже не смотря на то, что алгоритм SHA-1 имеет ряд недостатков, он активно используется.

<?php
///Однопроходное хэширование SHA-1
$string = "Netuts is Awesome";
$hash = sha1($string);
//или
$hash2 = hash('sha1', $string);
echo $hash."<br />";
echo $hash2."<br /><br />";
//Выведет: 42d2f15c3f92d28d7d58776e5d81b800f662cc6c
?>

В PHP пользуется почетом SHA-2, который требует версии PHP 5.1.2 или новее. SHA-2 более продвинутый алгоритм по сравнению с SHA-1 и может использовать различную длину хэш кода.

<?php
$string_sha256 = "Nettuts is Awesome";
$string_sha384 = "Nettuts is Awesome";
$string_sha512 = "Nettuts is Awesome";
$hash_sha256 = hash('sha256', $string_sha256);
$hash_sha384 = hash('sha384', $string_sha384);
$hash_sha512 = hash('sha512', $string_sha512);
echo $hash_sha256."<br />";
echo $hash_sha384."<br />";
echo $hash_sha512."<br />";
/* Выводят соответственно:
sha256 : 09074adc0d70e15b88494643e29c2836e1ab94a21989691dec594cb0bd742ebc
sha384 : 8535470750df54a78701d4bfe0451f9799057a5bc101944a32480d2436e8b95440bce3bcab3f9ce107b0b92d9595ae32
sha512 : c2e6dce873a71800b862791e56b480b976bb26cd3136c02da510c3905caa49b7b9e9260549976e1e741cc93e4569a611f2030d3b7104c6c6c2ff9e6c9bf0946a
*/
?>

Хэш функция вызывается с помощью hash(algorithm, string). Новая версия PHP функции hash() может быть вызванная с указанием любого однопроходного алгоритма хэширования, который поддерживает PHP (например md5, sha-1, haval, ghost). Если Вы хотите увидеть все зарегистрированные алгоритмы хэширования, то можно использовать:

<?php
//Для PHP5 >= 5.1.2
print_r(hash_algos());
?>

Алгоритм SHA-3 все еще разрабатывается и проходит стандартизацию.

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

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

<?php
$string_hmac = "Nettuts is Awesome";
//hash_hmac(algorithm, string to hash, key)
$hmac = hash_hmac('sha1', $string_hmac, 'secret');
echo $hmac."<br />";
?>

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

Добавлено: 16 Апреля 2018 17:43:21 Добавил: Андрей Ковальчук

Примеры реализации сортировки выбором

C

for (int i = 0; i < size - 1; ++i) {
/* устанавливаем начальное значение минимального индекса */
        int min_i = i;
        /* находим индекс минимального элемента */
        for (int j = i + 1; j < size; ++j) {
                if (array[j] < array[min_i]) {
                        min_i = j;
                }
        }
        /* меняем значения местами */
        int temp = array[i];
        array[i] = array[min_i];
        array[min_i] = temp;
}

C++
template <typename T, typename C = less< typename T::value_type> >
void select_sort( T f, T l, C c = C() )
{
    if (f!= l) {
        while (f != l - 1) {
            T min = f;
            for (T i = f + 1; i != l; ++i) {
                if (c(*i, *min)) {
                    typename T::value_type tmp = *min;
                    *min = *i;
                    *i = tmp;
                }
            }
            ++f;
        }
    }
}

C#
public void SelectionSort(int[] arr)
{
    int min, temp;
            int length = array.Length;
 
            for (int i = 0; i < length - 1; i++)
            {
                min = i;
 
                for (int j = i + 1; j < length; j++)
                {
                    if (array[j] < array[min])
                    {
                        min = j;
                    }
                }
 
                temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
}

Паскаль
for i := 1 to n - 1 do begin
    min := i;
    for j := i + 1 to n do
        if a[min] > a[j] then
            min := j;
    if min<>i then begin
        t := a[i];
        a[i] := a[min];
        a[min] := t;
    end;
end;

Компонентный Паскаль
PROCEDURE SelectionSort (VAR a: ARRAY OF REAL);
  VAR
    i, min: INTEGER;
    t: REAL;
BEGIN
  FOR i := 0 TO LEN(a) - 2 DO
    min := i;
    FOR j := i + 1 TO LEN(a) - 1 DO
      IF a[min] > a[j] THEN min := j END
    END;
    t := a[i]; a[i] := a[min]; a[min] := t
  END
END SelectionSort;

D
void selectionSort(int[] array) {
    int length = array.length;
    for (int i = 0; i < length - 1; ++i) {
        int min = array[i];
        int nmin = i;
        for (int j = i + 1; j < length; ++j) {
            if (array[j] < min) {
                min = array[j];
                nmin = j;
            }
        }
        array[nmin] = array[i];
        array[i] = min;
    }
}

VBA
Sub Sort(Mus() As Long)
    Dim n As Long, i As Long, j As Long, min As Long
 
    n = UBound(Mus)
    For i = LBound(Mus) To n - 1
       min = i
       For j = i + 1 To n
          If Mus(min) > Mus(j) Then min = j
       Next
       Swap Mus(i), Mus(min)
    Next
End Sub

Java
Итерационный алгоритм:

   public static void selectionSort (int[] numbers){
      int min, temp;
 
      for (int index = 0; index < numbers.length-1; index++){
         min = index;
         for (int scan = index+1; scan < numbers.length; scan++)
            if (numbers[scan] < numbers[min])
               min = scan;
 
         // Swap the values
         temp = numbers[min];
         numbers[min] = numbers[index];
         numbers[index] = temp;
      }
   }

Рекурсивный алгоритм:

public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
 
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
 
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
 
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

Ruby
a = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
 
for i in 0..a.length - 1
 
  min = i
 
  for j in i + 1..a.length - 1
 
    min = j if a[min] > a[j]
 
  end
 
  a[i], a[min] = a[min], a[i]
 
end
 
puts "#{a.join(" ")}"
 
# output => 1 3 3 5 8 10 11 12 17 20

Python
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
 
def select_sort(arr):
    i = len(arr)
    while i > 1:
        max = 0
        for j in xrange(i):
            if arr[j] > arr[max]:
                max = j
        swap(arr, i - 1, max)
        i -= 1

Ada
   type arr is array(1..n) of integer;
   i,j,t:integer;
   min:integer;
   mas1:arr;  
begin
   for i in 1..n-1 loop
      min:=i;
      for j in i+1..n loop
         if mas1(min)>mas1(j) then
            min:=j;
         end if;
         end loop;
         t:=mas1(i);
         mas1(i):=mas1(min);
         mas1(min):=t;
   end loop;
end sort;

PHP
$size = count($arr);
 
for ($i = 0; $i < $size; $i++)
{
    $min = $i;
 
    for ($j = $i + 1; $j < $size; $j++)
    {
        if ($arr[$j] < $arr[$min])
        {
            $min = $j;
        }
    }
 
    $temp = $arr[$i];
    $arr[$i] = $arr[$min];
    $arr[$min] = $temp;
}

TurboBasic 1.1
CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456
 
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
 
FOR X = 1 TO N
   Y[X] = X
   PRINT Y[X];
NEXT X:PRINT
 
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
 
PRINT " SLUCHAINYE CHISLA"
 
FOR X = 1 TO N
   YD=Y[X]
   XS=INT(RND*N)+1
   PRINT XS;
   Y[X]=Y[XS]
   Y[XS]=YD
NEXT X:PRINT
 
PRINT " PEREMESHANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
 
'ALGORITM "SORTIROVKA VYBOROM" O(N^2)
 
L=1
R=N
MTIMER
FOR J=1 TO R-1 STEP 1
   MIN=J
   FOR I=J+1 TO R STEP 1
      IF Y[I] < Y[MIN] THEN MIN=I
   NEXT I
   IF MIN<>J THEN SWAP Y[J],Y[MIN]
 
   LOCATE 7,1                            REM
   FOR I=1 TO N:PRINT Y[I];:NEXT I:PRINT REM ANIMATION BLOCK
   DELAY 1                               REM
 
NEXT J
T1=MTIMER
 
PRINT " OTSORTIROVANNYJ MASSIV"
 
FOR X=1 TO N
   'PRINT "Y[X]=";Y[X]
   PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1
PRINT FRE(-1)

Добавлено: 16 Апреля 2018 07:01:19 Добавил: Андрей Ковальчук

Примеры реализации сортировки вставками

Haskell

 insert :: Ord a ⇒ a → [a] → [a]
 insert x [] = [x]
 insert x (y : ys)
   | x ≤ y = x : y : ys
   | otherwise = y : insert x ys

 isort :: Ord a ⇒ [a] → [a]
 isort [ ] = [ ]
 isort (x : xs) = insert x (isort xs)


Си
int i, j, temp;
for (i = 1; i < size; i++)
{
    temp = array[i];
    for (j = i - 1; j >= 0; j--)
    {
        if (array[j] < temp)
            break;
 
        array[j + 1] = array[j];
        array[j] = temp;
    }   
}

C++
#include <algorithm>
 
template <typename Iterator>
void insertion_sort(Iterator first, Iterator last)
{
    for (Iterator i = first + 1; i < last; ++i)
        for (Iterator j = i; first < j && *j < *(j - 1); --j)
            std::iter_swap(j - 1, j);
}

C++ (оптимизирован)
Произведены следующие оптимизации:

нахождение минимального элемента и помещение его в первую позицию (это требуется для правильного функционирования второго пункта);
выход из внутреннего цикла, когда элемент находится на требуемой позиции;
замена операции обмена (swap) операцией присваивания.
template <typename Item>
void exch(Item &A, Item &B)
{ 
    Item t = A; A = B; B = t; 
}
 
template <typename Item>
void compexch(Item &A, Item &B)
{ 
    if (B < A) exch(A, B);
}
 
template <typename Item>
void insertion_sort(Item a[], int L, int R)
{
    for(int i = R; i > L; i--)
        compexch(a[i - 1], a[i]);
 
    for (int i = L + 2; i <= R; i++)
    {
        int j = i;
        Item cur = a[j];
        while (a[j - 1] > cur)
        {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = cur;
    }
}

C# (с возвратом результата)
public int[] InsertionSort(int[] array)
{
    int[] result = new int[array.Length];
    for (int i = 0; i < array.Length; i++)
    {
        int j = i;
        while (j > 0 && result[j - 1] > array[i])
        {
            result[j] = result[j - 1];
            j--;
        }
        result[j] = array[i];
    }
    return result;
}

C# (без дополнительной памяти 1)
public void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int cur = array[i];
        int j = i;
        while (j > 0 && cur < array[j - 1])
        {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = cur;
    }
}

C# (без дополнительной памяти 2)
public void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int j;
        int buf = array[i];
        for (j = i - 1; j >= 0; j--)
        {
            if (array[j] < buf)
                break;
 
            array[j + 1] = array[j];
        }
        array[j + 1] = buf;
    }
}

Java
public static void insertionSort(int[] m, int a, int b) {
    int t;
    int i, j;
    for (i = a; i < b; i++) {
        t = m[i];
        for (j = i - 1; j >= a && m[j] > t; j--)
            m[j + 1] = m[j];
 
        m[j + 1] = t;
    }
}

Javascript
(function() {
    var oSort= function() {
 
        var that = {};
 
        //собственно сама функция сортировки  
        that.insertionSort = function(a) {
            var i,j,x,
                iCount = that.getCountOfElements(a);
 
            for( i=0; i<iCount; i++) {
                x = a[i];
                for( j=i-1; j>=0 && a[j]>x; j-- ) {
                    a[j+1] = a[j];
                }
                a[j+1] = x;
            }
 
            return a;
        };
 
        that.getCountOfElements = function(a) {
            var i = 0,
                elem;
            for (elem in a) {
                i++
            }
            return i;
        };
 
        return that;
 
    }();
 
    console.log(oSort.insertionSort([9, 13, 7, 12, 10, 14, 8, 11, 6]));
    //[6, 7, 8, 9, 10, 11, 12, 13, 14]
 
})();

VBA
Sub Sort(Mus() As Long)
    Dim l As Long, r As Long, i As Long, j As Long, buf As Long
    l = LBound(Mus)
    r = UBound(Mus)
 
    For i = (l + 1) To r
        buf = Mus(i)
        j = i - 1
        Do While (Mus(j) > buf)
            Mus(j + 1) = Mus(j)
            j = j - 1
            If j < l Then Exit Do
        Loop
        Mus(j + 1) = buf
    Next
End Sub

Python
def fast_insertion_sort(l):
    for i in xrange(1, len(l)):
        j = i - 1
        value = l.pop(i)
        while (j >= 0) and (l[j] > value):
            j -= 1
        l.insert(j + 1, value)
    return l
Perl[править]
for(1..$N-1){
    my$tmp=$out[$_];
        for($j=$_-1;$j>=0;$j--){
            $out[$j+1]=$out[$j];
            last if($out[$j]lt$tmp);
        }
    $out[$j+1]=$tmp;
}

Паскаль
const N = 255;
type TArray = array [1..N] of integer; 
procedure InsertSort(var x: TArray);
var
  i, j, buf: integer;
begin
  for i := 2 to N do
  begin
    buf := x[i];
    j := i - 1;
    while (j >= 1) and (x[j] > buf) do
    begin
      x[j + 1] := x[j];
      j := j - 1;
    end;
    x[j + 1] := buf;
  end;
end.

PHP
function insertion_sort(&$a) {
  // для каждого $a[$i] начиная со второго элемента...
  for ($i = 1; $i < count($a); $i++) {
    $x = $a[$i];
    for ($j = $i - 1; $j >= 0 && $a[$j] > $x; $j--) {
      /* сдвигаем элементы вправо, пока выполняется условие
         $a[$j] > $a[$i] */
      $a[$j + 1] = $a[$j];
    }
    // на оставшееся после сдвига место, ставим $a[$i]
    $a[$j + 1] = $x;
  }
}

Ruby
arr = [9, 13, 7, 12, 10, 14, 8, 11, 6]
for i in 1..arr.length - 1
  x = arr[i]
  for j in 0..i - 1
    if arr[i] < arr[j]
        i.downto(j + 1) do |k|
          arr[k] = arr[k - 1]
        end
      arr[j] = x
      break
    end
  end
end
puts "#{arr.join(" ")}"
# output => 6 7 8 9 10 11 12 13 14

Turbo Basic 1.1
Входной массив Y[1],...,Y

[VB]FOR I=2 TO N
   K=Y[I]
   J=I-1
   WHILE J>0 AND Y[J]>K
      Y[J+1]=Y[J]
      J=J-1
      WEND
   Y[J+1]=K
   NEXT I

Добавлено: 15 Апреля 2018 07:39:06 Добавил: Андрей Ковальчук

Примеры реализации сортировки пузырьком

Ассемблер
Синтаксис Intel

    mov bx, offset array
    mov cx, n
for_i:
    dec cx
    xor dx, dx
for_j:
    cmp dx, cx
    jae exit_for_j
    jbe no_swap
    mov ah, byte ptr bx[di]
    mov byte ptr bx[di], al
    mov byte ptr bx[si], ah
no_swap:
    inc dx
    jmp for_j
exit_for_j:
    loop    for_i

Синтаксис AT&T (GNU)
.text
# void bubble_sort (unsigned *array, unsigned length);
.globl bubble_sort
    .type   bubble_sort, @function
bubble_sort:
    mov 8(%esp), %ecx # unsigned length
    cmp $1, %ecx
    jbe exit
    mov 4(%esp), %eax # unsigned *array
    dec %ecx
for_ecx:
    xor %edi, %edi
for_edi:
    mov (%eax,%edi,4), %ebx
    cmp %ebx, 4(%eax,%edi,4)
    jae  no_xchng
    mov 4(%eax,%edi,4), %edx
    mov %edx, (%eax,%edi,4)
    mov %ebx, 4(%eax,%edi,4)
no_xchng:
    inc %edi
    cmp %edi, %ecx
    jne for_edi
    loop for_ecx
exit:
    ret

C
#define SWAP(A, B) { int t = A; A = B; B = t; }
 
void bubblesort(int *a, int n)
{
  int i, j;
 
  for (i = n - 1; i > 0; i--)
  {
    for (j = 0; j < i; j++)
    {
      if (a[j] > a[j + 1]) 
        SWAP( a[j], a[j + 1] );
    }
  }
}

C++
С использованием Template
#include <algorithm>
template< typename Iterator >
void bubble_sort( Iterator First, Iterator Last )
{
    while( First < --Last )
        for( Iterator i = First; i < Last; ++i )
            if ( *(i + 1) < *i )
                std::iter_swap( i, i + 1 );
}

Без использования Template
void bubble(int*a, int n)
{
for (int i=n-1;i>0;i--)
  {
    for (int j=0;j<i;j++)
      {
        if(a[j]>a[j+1])
          {
            int tmp=a[j];
            a[j]=a[j+1];
            a[j+1]=tmp;
          }
     }
  }
}

C#
void BubbleSort(int[] A)
{
   int temp;
 
   for(int i = 0; i < A.Length - 1; i++)
   {
      for(int j = 0; j < A.Length - i - 1; j++)
      {
         if(A[j] > A[j + 1])
         {
            temp = A[j];
            A[j]=A[j+1];
            A[j + 1] = temp;
         }
      }
   }
}

Delphi
Сортировка одномерного динамического целочисленного массива:

type
 TIntVec = array of Integer;
...
procedure BubbleSort(var a: TIntVec);
 var i,p,n: Integer; b: boolean;
begin
 n:= Length(a);
 if n < 2 then exit;
 repeat
  b:= false;
  Dec(n);
  if n > 0 then
  for i:= 0 to n-1 do
   if a[i] > a[i+1] then
    begin
     p:= a[i];
     a[i]:= a[i+1];
     a[i+1]:= p;
     b:= true;
    end;
 until not b;
end;

D
void bubbleSort(alias op, T)(T[] inArray) {
    foreach (i, ref a; inArray) {
        foreach (ref b; inArray[i+1..$]) {
            if (mixin(op)) {
                auto tmp = a;
                a = b;
                b = tmp;
            }
        }
    }
}

Fortran
do i=n-1,1,-1
do j=1,i
    if (a(j).gt.a(j+1)) then
        t=a(j)
        a(j)=a(j+1)
        a(j+1)=t
    endif
enddo
enddo

Java
void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
 
void bubblesort(int[] arr){
    for(int i = arr.length-1 ; i > 0 ; i--){
        for(int j = 0 ; j < i ; j++){
            if( arr[j] > arr[j+1] )
               swap(arr, j, j+1);
        }
    }
}

Pascal
for i:=n-1 downto 1 do {n - размер массива M[]}
    for j:=1 to i do
        if M[j]>M[j+1] then 
            begin
               tmp:= M[j];
               M[j]:= M[j+1];
               M[j+1]:= tmp;
            end;
write('вывод значений M[]: ');
for i:=1 to n do
    write(M[i]:4);
writeln;

Усовершенствованный алгоритм сортировки пузырьком:

P:=True; {есть перестановка?}
K:=1; {Номер просмотра}
While P Do
Begin
    P:=false;
    For i:=1 To n-k Do
        If X[i] > X[i+1] Then
        Begin
            A:=X[i];
            X[i]:=X[i+1];
            X[i+1]:=A;
            P:=true;
        End;
    k:=k+1;
End;

Perl
for(@out){
  for(0..$N-1){
    if($out[$_]gt$out[$_+1]){
      ($out[$_],$out[$_+1])=($out[$_+1],$out[$_]);
    }
  }
}

Ruby
arr = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
swap = true
size = arr.length - 1
while swap
  swap = false
  for i in 0...size
    swap |= arr[i] > arr[i + 1]
    arr[i], arr[i+1] = arr[i + 1], arr[i] if arr[i] > arr[i + 1]
  end
  size -= 1
end
puts arr.join(' ')
# output => 1 3 3 5 8 10 11 12 17 20

Python
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
 
def bubble_sort(arr):
    i = len(arr)
    while i > 1:
       for j in xrange(i - 1):
           if arr[j] > arr[j + 1]:
               swap(arr, j, j + 1)
       i -= 1

VBA
Sub Sort(Mus() As Long)
Dim i As Long, tmp As Long, t As Boolean
t = True
Do While t
    t = False
    For i = 0 To UBound(Mus()) - 1
        If Mus(i) > Mus(i + 1) Then
            tmp = Mus(i)
            Mus(i) = Mus(i + 1)
            Mus(i + 1) = tmp
            t = True
        End If
    Next
Loop
End Sub

PHP
$size = sizeof($arr)-1;
for ($i = $size; $i>=0; $i--) {
    for ($j = 0; $j<=($i-1); $j++)
        if ($arr[$j]>$arr[$j+1]) {
            $k = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $k;
        }
}

JavaScript
function sortBubble(data) {
    var tmp;
 
    for (var i = data.length - 1; i > 0; i--) {
        for (var j = 0; j < i; j++) {
            if (data[j] > data[j+1]) {
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
    return data;
}

JavaFX
function bubbleSort(seq:Number[]):Number[]{
 
    var sort = seq;
    var elem:Number;
 
    for(n in reverse [0..sizeof seq - 2]){
        for(i in [0..n] ){
            if(sort[i+1] < sort[i] ){
                elem = sort[i];
                sort[i] = sort[i+1];
                sort[i+1] = elem;
            }
        }
    }
 
    return sort;
}

Nemerle
using System.Console;
using Nemerle.Collections;
 
def arr = array [100, 45, 2, 5, 3, 122, 3, 5, 6, 1, 3];
 
foreach (i in [0..arr.Length-1])
    foreach (j in [0..arr.Length-2])
       when (arr[j] > arr[j+1])
           (arr[j], arr[j+1]) = (arr[j+1], arr[j]);
 
WriteLine($"Sorted list is a $(arr.ToList())");

TurboBasic 1.1
CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456
 
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
 
FOR X = 1 TO N
   Y[X] = X
   PRINT Y[X];
NEXT X:PRINT
 
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
 
PRINT " SLUCHAINYE CHISLA"
 
FOR X = 1 TO N
   YD=Y[X]
   XS=INT(RND*N)+1
   PRINT XS;
   Y[X]=Y[XS]
   Y[XS]=YD
NEXT X:PRINT
 
PRINT " PEREMESHANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
 
'ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
   F=0
   FOR I=1 TO N-J STEP 1
      'IF Y[I] > Y[I+1] THEN D=Y[I]:Y[I]=Y[I+1]:Y[I+1]=D:F=1
      IF Y[I] > Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1
 
      LOCATE 8,1                    REM
      PRINT " ANYMACIJA SORTIROVKI" REM
      FOR X1=1 TO N                 REM ANIMATION BLOCK
         PRINT Y[X1];               REM
      NEXT X1:PRINT                 REM
      DELAY .5                      REM
 
   NEXT I
   IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER
 
PRINT " OTSORTIROVANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1

Добавлено: 14 Апреля 2018 07:08:55 Добавил: Андрей Ковальчук

Примеры реализации сортировки слиянием

C++

               /**
                * @brief         Сортировка элементов от l до r массива buf
                * @param[in/out] buf - сортируемый массив
                * @param[in]     l - левая граница. При первой итерации l = 0
                * @param[in]     r - правая граница. При первой итерации r = buf.size() - 1
                *
                * В результате сортируются все элементы массива buf от l до r включительно.
                */
               template<typename Type>
void MergeSort(vector<Type>& buf, size_t l, size_t r)
{
    //! Условие выхода из рекурсии
    if(l >= r) return;
 
    size_t m = (l + r) / 2;
 
    //! Рекурсивная сортировка полученных массивов
    MergeSort(buf, l, m);
    MergeSort(buf, m+1, r);
    merge(buf, l, r, m);
}
 
/**
 * @brief Слияние элементов.
 * @param[in/out] buf - массив
 * @param[in]     l - левая граница. При певой итерации l = 0
 * @param[in]     r - правая граница. При первой итерации r = buf.size() - 1
 * @param[in]     m - граница подмассивов.
 *
 * Массив buf содержит два отсортированных подмассива:
 * - [l; m] - первый отсортированный подмассив.
 * - [m+1; r] - второй отсортированный подмассив.
 * В результате получаем отсортированный массив, полученный из двух подмассивов,
 * который сохраняется в buf[l; r].
 */
template<typename Type>
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
    if(l >= r || m < l || m > r) return;
    if(r == l + 1 && buf[l] > buf[r])
    {
        swap(buf[l], buf[r]);
        return;
    }
 
    vector<Type> tmp(&buf[l], &buf[r+1]);
 
    for(size_t i = l, j = 0, k = m - l + 1; i <= r; i++)
    {
        if(j > m - l)      buf[i] = tmp[k++];
        else if(k > r - l) buf[i] = tmp[j++];
        else               buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
    }
}

Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».
// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
               template <class T>
T* merge(T *m1, T* m2, int l1, int l2)
{
    T* ret = new T[l1+l2];
    int n = 0;
    // Сливаем массивы, пока один не закончится
    while (l1 && l2)
    {
        if (*m1 < *m2)
        {
            ret[n] = *m1;
            m1++;
            l1--;
        }
        else
        {
            ret[n] = *m2;
            m2++;
            l2--;
        }
        n++;
    }
    // Если закончился первый массив
    if (l1 == 0)
    {
        for (int i=0; i<l2; i++)
        {
            ret[n++] = *m2++;
        }
    }
    // Если закончился второй массив
    else
    {
        for (int i=0; i<l1; i++)
        {
            ret[n++] = *m1++;
        }
    }
    return ret;
}
 
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
    int n = 1, l, ost;
    T * mas1;
    while (n < len)
    {
        l = 0;
        while (l < len)
        {
            if (l+n >= len) break;
            ost = (l+n*2>len) ? (len-(l+n)) : n;
            mas1 = merge(mas + l, mas + l + n, n, ost);
            for (int i = 0; i<n+ost; i++) mas[l+i] = mas1[i];
            delete [] mas1;
            l += n*2;
        }
        n *= 2;
    }
}

Пример: char a[] = "ASORTINGEXAMPLE"; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием.

               template <typename Item>
void Merge(Item Mas[], int left, int right, int medium)
{
    int j = left;
    int k = medium + 1;
    int count = right - left + 1;
 
    if (count <= 1) return;
 
    Item *TmpMas = new Item[count];
 
    for (int i = 0; i < count; i++)
    {
        if (j <= medium && k <= right)
        {
            if (Mas[j] < Mas[k])
                TmpMas[i] = Mas[j++];
            else
                TmpMas[i] = Mas[k++];
        }
        else
        {
            if (j <= medium)
                TmpMas[i] = Mas[j++];
            else
                TmpMas[i] = Mas[k++];
        }
    }
 
    j = 0;
    for (int i = left; i <= right; i++)
    {
        Mas[i] = TmpMas[j++];
    }
    delete[] TmpMas;
}
 
template <typename Item>
void MergeSort(Item a[], int l, int r)
{
    int m;
 
    // Условие выхода из рекурсии
    if(l >= r) return;
 
    m = (l + r) / 2;
 
    // Рекурсивная сортировка полученных массивов
    MergeSort(a, l, m);
    MergeSort(a, m + 1, r);
    Merge(a, l, r, m);
}

C#
        static Int32[] Merge_Sort(Int32[] massive)
        {
            if (massive.Length == 1)
                return massive;
            Int32 mid_point = massive.Length / 2;
            return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
        }
 
        static Int32[] Merge(Int32[] mass1, Int32[] mass2)
        {
            Int32 a = 0, b = 0;
            Int32[] merged = new int[mass1.Length + mass2.Length];
            for (Int32 i = 0; i < mass1.Length + mass2.Length; i++)
            {
                if (b < mass2.Length && a < mass1.Length)
                    if (mass1[a] > mass2[b] && b < mass2.Length)
                        merged[i] = mass2[b++];
                    else //if int go for
                        merged[i] = mass1[a++];
                else
                    if (b < mass2.Length)
                        merged[i] = mass2[b++];
                    else
                        merged[i] = mass1[a++];
            }
            return merged;
        }
 
    static void Main(string[] args)
        {
              Int32[] arr = new Int32[100];
              //заполняем массив случайными числами
              Random rd = new Random();
              for(Int32 i = 0; i < arr.Length; ++i) {
                 arr[i] = rd.Next(1, 101);
              }
              System.Console.WriteLine("The array before sorting:");
              foreach (Int32 x in arr)
              {
                 System.Console.Write(x + " ");
              }
              //сортировка
 
              arr = Merge_Sort(arr);
 
              System.Console.WriteLine("\n\nThe array after sorting:");
              foreach (Int32 x in arr)
              {
                 System.Console.Write(x + " ");
              }
              System.Console.WriteLine("\n\nPress the <Enter> key");
              System.Console.ReadLine();
        }

Perl

@out=(5,2,8,9,4,2,7,9,4,1,6,9,0);
sub sortM{
    my($array,$first,$last)=@_;
    if($last>$first){
        my$middle=int(($last+$first)/2);
        sortM($array,$first,$middle);
        sortM($array,$middle+1,$last);
        my$j=0;
        $work[$j++]=$$array[$_]for($first..$last);
        $middle=int(($first+$last)/2)if($middle>$last);
        my$n=$middle-$first+1;
        for($i=$first,$j=0,$k=$n;$i<=$last;$i++){
            if(($j<$n)&&(($k==(($last-$first)+1))||($work[$j]lt$work[$k]))){
                $$array[$i]=$work[$j++]
            }else{
                $$array[$i]=$work[$k++];
            }
        }
    }
}
sortM(\@out,0,$#out+1);

Паскаль (сортировка текстовых файлов)
Сортировка простым слиянием
Procedure MergeSort(name: string; var f: text);
          Var a1,a2,s,i,j,kol,tmp: integer;
              f1,f2: text;
              b: boolean;
          Begin
             kol:=0;
 
             Assign(f,name);
             Reset(f);
             While not EOF(f) do
               begin
                 read(f,a1);
                 inc(kol);
               End;
             Close(f);
 
             Assign(f1,'{имя 1-го вспомогательного файла}');
             Assign(f2,'{имя 2-го вспомогательного файла}');
 
             s:=1;
             While (s<kol) do
               begin
 
                 Reset(f); Rewrite(f1); Rewrite(f2);
                 For i:=1 to kol div 2 do
                   begin
                     Read(f,a1);
                     Write(f1,a1,' ');
                   End;
                 If (kol div 2) mod s<>0 then
                   begin
                     tmp:=kol div 2;
                     While tmp mod s<>0 do
                       begin
                         Read(f,a1);
                         Write(f1,a1,' ');
                         inc(tmp);
                       End;
                   End;
                 While not EOF(f) do
                   begin
                     Read(f,a2);
                     Write(f2,a2,' ');
                   End;
                 Close(f); Close(f1); Close(f2);
 
 
                 Rewrite(f); Reset(f1); Reset(f2);
                 Read(f1,a1); 
                 Read(f2,a2);
                 While (not EOF(f1)) and (not EOF(f2)) do
                   begin
                     i:=0; j:=0;
                     b:=true;
                     While (b) and (not EOF(f1)) and (not EOF(f2)) do
                       begin
                         If (a1<a2) then
                           begin
                             Write(f,a1,' ');
                             Read(f1,a1);
                             inc(i);
                           End
                         else
                           begin
                             Write(f,a2,' ');
                             Read(f2,a2);
                             inc(j);
                           End;
                         If (i=s) or (j=s) then b:=false;
                       End;
                     If not b then
                       begin
                         While (i<s) and (not EOF(f1)) do
                           begin
                             Write(f,a1,' ');
                             Read(f1,a1);
                             inc(i);
                           End;
                         While (j<s) and (not EOF(f2)) do
                           begin
                             Write(f,a2,' ');
                             Read(f2,a2);
                             inc(j);
                           End;
                       End;
                   End;
                 While not EOF(f1) do
                   begin
                     tmp:=a1;
                     Read(f1,a1);
                     If not EOF(f1) then
                       Write(f,tmp,' ')
                     else
                       Write(f,tmp);
                   End;
                 While not EOF(f2) do
                   begin
                     tmp:=a2;
                     Read(f2,a2);
                     If not EOF(f2) then
                       Write(f,tmp,' ')
                     else
                       Write(f,tmp);
                   End;
                 Close(f); Close(f1); Close(f2);
 
                 s:=s*2;
               End;
             Erase(f1);
             Erase(f2);
          End;

Сортировка естественным слиянием
Procedure MergeSort(name: string; var f: text);
          Var s1,s2,a1,a2,where,tmp: integer;
              f1,f2: text;
          Begin
             s1:=5; s2:=5; {Можно задать любые числа, которые запустят цикл while}
             Assign(f,name);
             Assign(f1,'{имя 1-го вспомогательного файла}');
             Assign(f2,'{имя 2-го вспомогательного файла}');
             While (s1>1) and (s2>=1) do
               begin
                 where:=1;
                 s1:=0; s2:=0;
                 Reset(f); Rewrite(f1); Rewrite(f2);
                 Read(f,a1);
                 Write(f1,a1,' ');
                 While not EOF(f) do
                   begin
                     read(f,a2);
                     If (a2<a1) then
                       begin
                         Case where of
                            1: begin
                                 where:=2;
                                 inc(s1);
                               End;
                            2: begin
                                 where:=1;
                                 inc(s2);
                               End;
                         End;
                       End;
                     Case where of
                        1: write(f1,a2,' ');
                        2: write(f2,a2,' ');
                     End;
                     a1:=a2;
                   End;
                 If where=2 then
                   inc(s2)
                 else
                   inc(s1);
                 Close(f); Close(f1); Close(f2);
 
 
                 Rewrite(f); Reset(f1); Reset(f2);
                 Read(f1,a1);
                 Read(f2,a2);
                 While (not EOF(f1)) and (not EOF(f2)) do
                   begin
                     If (a1<=a2) then
                       begin
                         Write(f,a1,' ');
                         Read(f1,a1);
                       End
                     else
                       begin
                         Write(f,a2,' ');
                         Read(f2,a2);
                       End;
                   End;
                 While not EOF(f1) do
                   begin
                     tmp:=a1;
                     Read(f1,a1);
                     If not EOF(f1) then
                        Write(f,tmp,' ')
                     else
                        Write(f,tmp);
                   End;
                 While not EOF(f2) do
                   begin
                     tmp:=a2;
                     Read(f2,a2);
                     If not EOF(f2) then
                        Write(f,tmp,' ')
                     else
                        Write(f,tmp);
                   End;
                 Close(f); Close(f1); Close(f2);
               End; 
             Erase(f1);
             Erase(f2);
          End;

Delphi (сортировка произвольных типов данных - простое слияние)
unit uMergeSort;
 
interface
type
  TItem = Integer;               //Здесь можно написать Ваш произвольный тип
  TArray = array of TItem;
 
  procedure MergeSort(var Arr: TArray);
 
implementation
 
function IsBigger(d1, d2 : TItem) : Boolean;
begin
  Result := (d1 > d2);     //Сравниваем d1 и d2. Не обязательно так. Зависит от Вашего типа.
  //Сюда можно добавить счетчик сравнений
end;
 
//Процедура сортировки слияниями
procedure MergeSort(var Arr: TArray);
var
  tmp : TArray; //Временный буфер // А где реализация процедуры? Этот код работать не будет, допишите, пожалуйста
  //Слияние
  procedure merge(L, Spl, R : Integer);
  var
    i, j, k : Integer;
  begin
    i := L;
    j := Spl + 1;
    k := 0;
    //Выбираем меньший из первых и добавляем в tmp
    while (i <= Spl) and (j <=R) do
    begin
      if IsBigger(Arr[i], Arr[j]) then
      begin
        tmp[k] := Arr[j];
        Inc(j);
      end
      else
      begin
        tmp[k] := Arr[i];
        Inc(i);
      end;
      Inc(k);
    end;
    //Просто дописываем в tmp оставшиеся эл-ты
    if i <= Spl then      //Если первая часть не пуста
      for j := i to Spl do
      begin
        tmp[k] := Arr[j];
        Inc(k);
      end
    else                  //Если вторая часть не пуста
      for i := j to R do
      begin
        tmp[k] := Arr[i];
        Inc(k);
      end;
    //Перемещаем из tmp в arr
    Move(tmp[0], Arr[L], k*SizeOf(TItem));
  end;
 
  //Сортировка
  procedure sort(L, R : Integer);
  var
    splitter : Integer;
  begin
    //Массив из 1-го эл-та упорядочен по определению
    if L >= R then Exit;
    splitter := (L + R) div 2;  //Делим массив пополам
    sort(L, splitter);          //Сортируем каждую
    sort(splitter + 1, R);      //часть по отдельности
    merge(L, splitter, R);      //Производим слияние
  end;
 
  //Основная часть процедуры сортировки
begin
  SetLength(tmp, Length(Arr));
  sort(0, Length(Arr) - 1);
  SetLength(tmp, 0);
end;
 
end.

D
void mergeSort(int[] array) {
    static void merge(int[] array, int q) {
        int[] leftArray = array[0..q].dup ~ int.max;
        int[] rightArray = array[q..$].dup ~ int.max;
        int i = 0;
        int j = 0;
        int length = array.length;
        for (int k = 0; k < length; ++k) {
            array[k] = (leftArray[i] <= rightArray[j]) ? leftArray[i++] : rightArray[j++];
        }
    }
 
    if (array.length > 1) {
        int q = array.length / 2;
        mergeSort(array[0..q]);
        mergeSort(array[q..$]);
        merge(array, q);
    }
}

Добавлено: 14 Апреля 2018 06:51:55 Добавил: Андрей Ковальчук

Метод рекурсивного спуска. Java Math Parser

Класс предназначен для интерпретирования арифметических выражений методом рекурсивного спуска.
Поддерживаемые операции:

Побитовое И            &
Побитовое ИЛИ          |
Побитовое НЕ           ~
Сложение               +
Вычитание              -
Умножение              *
Деление                /
Остаток от деления     %
Целочисленное деление  \
Возведение в степень   ^


Поддерживаемые функции:
sin(x)   - синус
cos(x)   - косинус
tan(x)   - тангенс
ctg(x)   - котангенс
sinh(x)  - гиперболический синус
cosh(x)  - гиперболический косинус
tanh(x)  - гиперболический тангенс
sec(x)   - секанс
cosec(x) - косеканс
abs(x)   - модуль числа
sqrt(x)  - квадратный корень
ln(x)    - натуральный логарифм
lg(x)    - десятичный логарифм
log(x,y) - логарифм x по основанию y
xor(x,y) - побитовое исключающее ИЛИ




MathParser.java

import java.util.HashMap;

/**
 *
 * Класс модифицирован автором ShamaN.
 * Метод рекурсивного спуска для интерпретирования математических выражений.
 * Поддерживаются тригонометрические функции с одним/двумя параметрами.
 * @author shurik
 * @version 1.1
 */
public class MathParser {

    private static HashMap<String, Double> var;

    public MathParser() {
            var = new HashMap<>();
            setVariable("pi",Math.PI);
            setVariable("e",Math.E);
    }

    
    /**
     * Вставить новую переменную
     * @param varName имя переменной
     * @param varValue значение переменной
     */
    public static void setVariable(String varName, Double varValue) {
            var.put(varName, varValue);
    }
    
    /**
     * Заменяет значение существующей переменной
     * @param varName имя переменной
     * @param varValue значение переменной
     */
    public void replaceVariable(String varName, Double varValue) {       
            var.replace(varName, varValue);
    }

    /**
     * 
     * @param varName
     * @return Возвращает значение переменной varName
     * @throws Exception ругаемся на отсутствие переменной
     */
    public Double getVariable(String varName) throws Exception {
        if(!var.containsKey(varName)) {
            throw new Exception("Error:Try get unexists "+
                                               "variable '"+varName+"'" );
        }
        return var.get(varName);
    }

    /**
     * Парсим математическое выражение
     * @param s математическое выражение
     * @return результат
     * @throws Exception 
     */
    public double Parse(String s) throws Exception {
        if(s.isEmpty())
            throw new Exception("Empty expression");
        Result result = binaryFunc(s);
        if (!result.rest.isEmpty())
            throw new Exception("Error: can't full parse \n "+
                                              "rest: " + result.rest);
        return result.acc;
    }
    

    private Result binaryFunc(String s) throws Exception{
        
        Result cur;
        
        if(s.charAt(0) == '~'){
            cur = plusMinus(s.substring(1));
            
            cur.acc = ~ (int)cur.acc;
            return cur;
        }
        
        cur = plusMinus(s);
        double acc = cur.acc;
        
        cur.rest = skipSpaces(cur.rest);
        
        while(cur.rest.length() > 0){
            if(!(cur.rest.charAt(0) == '&' ||
                 cur.rest.charAt(0) == '|' || 
                 cur.rest.charAt(0) == '~')) break;
            
            char sign = cur.rest.charAt(0);
            String next = cur.rest.substring(1);
            cur = plusMinus(next);
            

            if(sign == '&')
                    acc = (int)acc & (int)cur.acc;
            else
                    acc = (int)acc | (int)cur.acc;
        }
        
        return new Result(acc,cur.rest);
        
    }

    private Result plusMinus(String s) throws Exception {

        Result cur = mulDiv(s);
        double acc = cur.acc;
        
        cur.rest = skipSpaces(cur.rest);

        while(cur.rest.length() > 0){
            if(!(cur.rest.charAt(0) == '+' || cur.rest.charAt(0) == '-'))
                    break;
            
            char sign = cur.rest.charAt(0);
            String next = cur.rest.substring(1);

            cur = binaryFunc(next);

            if(sign == '+')
                    acc+=cur.acc;
            else
                    acc-=cur.acc;
        }
        return new Result(acc,cur.rest);
    }

    


    private Result mulDiv(String s) throws Exception{
        Result cur = exponentiation(s);
        double acc = cur.acc;

        cur.rest = skipSpaces(cur.rest);
        
        
        while(true){
            if(cur.rest.length() == 0)
                    return cur;
                
            char sign = cur.rest.charAt(0);
            if(sign != '*' && sign != '/' && sign != '%' && sign != '\\') 
                return cur;

            String next = cur.rest.substring(1);
            Result right = exponentiation(next);
            switch(sign){
                case '*': 
                    acc*=right.acc; 
                    break;
                case '/': 
                    acc/=right.acc; 
                    break;
                case '%': // остаток от деления
                    acc%=right.acc; 
                    break; 
                case '\\': // целочисленное деление
                    acc = (acc - acc % right.acc)/right.acc; 
                    break;
            }
            cur = new Result(acc,right.rest);
        }
    }


    private Result exponentiation(String s) throws Exception{
        Result cur = bracket(s);
        double acc = cur.acc;
        
        cur.rest = skipSpaces(cur.rest);

        while(true){
            
            if(cur.rest.length() == 0) return cur;
            if(cur.rest.charAt(0) !='^') break;

            String next = cur.rest.substring(1);
            cur = bracket(next);
            cur.acc = Math.pow(acc,cur.acc);
        } 
        return cur;
    }


    private Result bracket(String s) throws Exception{
        
        s = skipSpaces(s);
        char zeroChar = s.charAt(0);
        if (zeroChar == '(') {
            Result r = binaryFunc(s.substring(1));
            if (!r.rest.isEmpty()) {
                r.rest = r.rest.substring(1);
            } else {
                throw new Exception("Expected closing bracket");
            }
            return r;
        }
        return functionVariable(s);
    }

    private Result functionVariable(String s) throws Exception{
        String f = "";
        int i = 0;
        // ищем название функции или переменной
        // имя обязательно должна начинаться с буквы
        while (i < s.length() && (Character.isLetter(s.charAt(i)) || 
              ( Character.isDigit(s.charAt(i)) && i > 0 ) )) {
            f += s.charAt(i);
            i++;
        }
        if (!f.isEmpty()) { // если что-нибудь нашли
            if ( s.length() > i && s.charAt( i ) == '(') { 
            // и следующий символ скобка значит - это функция
                Result r = binaryFunc(s.substring(f.length()+1));
                
                if(!r.rest.isEmpty() && r.rest.charAt(0) == ','){
                // если функция с двумя параметрами
                    double acc = r.acc;
                    Result r2 = binaryFunc(r.rest.substring(1));
                    
                    r2 = closeBracket(r2);
                    return processFunction(f, acc,r2);

                } else {
                    r = closeBracket(r);
                    return processFunction(f, r);
                }
            } else { // иначе - это переменная
                return new Result(getVariable(f), s.substring(f.length()));
            }
        }
        return num(s);
    }
    private Result closeBracket(Result r) throws Exception{
        if(!r.rest.isEmpty() && r.rest.charAt(0) ==')'){
            r.rest = r.rest.substring(1);
        } else
            throw new Exception("Expected closing bracket");
        return r;
    }

    private Result num(String s) throws Exception{
        int i = 0;
        int dot_cnt = 0;
        boolean negative = false;
        // число также может начинаться с минуса
        if( s.charAt(0) == '-' ){
            negative = true;
            s = s.substring( 1 );
        }
        // разрешаем только цифры и точку
        while (i < s.length() && 
              (Character.isDigit(s.charAt(i)) || s.charAt(i) == '.')) {
            // но также проверяем, что в числе может быть только одна точка!
            if (s.charAt(i) == '.' && ++dot_cnt > 1) {
                throw new Exception("not valid number '" 
                                    + s.substring(0, i + 1) + "'");
            }
            i++;
        }
        if( i == 0 ){ // что-либо похожее на число мы не нашли
            throw new Exception("can't get valid number in '" + s + "'" );
        }

        double dPart = Double.parseDouble(s.substring(0, i));
        if(negative) dPart = -dPart;
        String restPart = s.substring(i);

        return new Result(dPart, restPart);
    }

    private Result processFunction(String func, Result r) throws Exception{
        switch (func) {
            case "sin":
                return new Result(Math.sin(r.acc), r.rest);
            case "sinh": // гиперболический синус
                return new Result(Math.sinh(r.acc), r.rest);
            case "cos": 
                return new Result(Math.cos(r.acc), r.rest);
            case "cosh": // гиперболический косинус
                return new Result(Math.cosh(r.acc), r.rest);
            case "tan":
                return new Result(Math.tan(r.acc), r.rest);
            case "tanh": // гиперболический тангенс
                return new Result(Math.tanh(r.acc), r.rest);
            case "ctg":
                return new Result(1/Math.tan(r.acc), r.rest);
            case "sec": // секанс
                return new Result(1/Math.cos(r.acc), r.rest);
            case "cosec": // косеканс
                return new Result(1/Math.sin(r.acc), r.rest);   
            case "abs":
                return new Result(Math.abs(r.acc), r.rest);
            case "ln":
                return new Result(Math.log(r.acc), r.rest);
            case "lg": // десятичный логарифм
                return new Result(Math.log10(r.acc), r.rest);
            case "sqrt":
                return new Result(Math.sqrt(r.acc), r.rest);
            default:
                throw new Exception("function '" + func + "' is not       
                                                              defined");    
        }
    }
    private Result processFunction(String func,
                                   double acc, 
                                   Result r) throws Exception{
        switch(func){
            case "log": // логарифм x по основанию y
                return new Result(Math.log(acc)/Math.log(r.acc),
                                  r.rest);
            case "xor": // исключающее или 
                return new Result((int)acc ^ (int)r.acc,r.rest);
            default:
                throw new Exception("function '" + func + 
                                    "' is not defined");
        }
    }
    
    private String skipSpaces(String s){
        return s.trim();
    }
    

    private class Result {
        public double acc; // Аккумулятор
        public String rest; // остаток строки, которую мы еще не обработали
        public Result(double v, String r) {
            this.acc = v;
            this.rest = r;
        }
    }
}


Пример использования:
Main.java
public class Main{
    public static void main(String[] args){
        MathParser parser = new MathParser();
        String[] expressions = {"2+4*3-8^3",
                                "4*sin(0.5)+2*cos(2*0.5)",
                                "log(64,2)*lg(100)",
                                "xor(65,83)",
                                "63 & 95",
                                "2*(5-7",
                                "x*5",
                                "",
                                "2*pi*50",
                                "e^2+1",
                                "6.78.-7"};
        
        for(String expression:expressions){
            System.out.print(expression+"  ");
            try{
                System.out.print(parser.Parse(expression)+"\n");
            } catch(Exception e){
                System.out.println(e.getMessage());
            }
        }  
    }
}


Результат тестирования:
2+4*3-8^3 = -498.0
4*sin(0.5)+2*cos(2*0.5) = 2.9983067661530916
log(64,2)*lg(100) = 12.0
xor(65,83) = 18.0
63 & 95 = 31.0
2*(5-7 = Expected closing bracket
x*5 = Error:Try get unexists variable 'x'
2^6+8 = 72.0
2*pi*50 = 314.1592653589793
e^2+1 = 8.389056098930649
6.78.-7 = not valid number '6.78.'

Добавлено: 18 Мая 2015 21:20:03 Добавил: Василий Рыбин

Алгоритмы сортировки строк

Сортировка выбором

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.
Реализация на С++

template&lt; class T &gt;
void selectSort(T* arr, int size) 
{
    T tmp;
    for(int i = 0; i &lt; size; ++i) // i - номер текущего шага
    { 
        int pos = i; 
        tmp = arr[i];
        for(int j = i + 1; j &lt; size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] &lt; tmp) 
           {
               pos = j; 
               tmp = arr[j]; 
           }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}

Реализация на Си
void selectSort(int* arr, int size) 
{
    int tmp, i, j, pos;
    for(i = 0; i &lt; size; ++i) // i - номер текущего шага
    { 
        pos = i; 
        tmp = arr[i];
        for(j = i + 1; j &lt; size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] &lt; tmp) 
            {
               pos = j; 
               tmp = arr[j]; 
            }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}


Сортировка пузырьком(обменом)

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
Реализация на С++
template&lt; class T &gt;
void bubbleSort(T* arr, int size)
{
    T tmp;
 
    for(int i = 0; i &lt; size - 1; ++i) // i - номер прохода
    {            
        for(int j = 0; j &lt; size - 1; ++j) // внутренний цикл прохода
        {     
            if (arr[j + 1] &lt; arr[j]) 
            {
                tmp = arr[j + 1]; 
                arr[j + 1] = arr[j]; 
                arr[j] = tmp;
            }
        }
    }
}

Реализация на Си
void bubbleSort(int* arr, int size)
{
    int tmp, i, j;
 
    for(i = 0; i &lt; size - 1; ++i) // i - номер прохода
    {            
        for(j = 0; j &lt; size - 1; ++j) // внутренний цикл прохода
        {     
            if (arr[j + 1] &lt; arr[j]) 
            {
                tmp = arr[j + 1]; 
                arr[j + 1] = arr[j]; 
                arr[j] = tmp;
            }
        }
    }
}

Сортировка вставками

Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.
Реализация на С++
template&lt; class T &gt;
void insertSort(T* a, int size) 
{
    T tmp;
    for (int i = 1, j; i &lt; size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j &gt;= 0 && a[j] &gt; tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}

Реализация на Си
void insertSort(int* a, int size) 
{
    int i, j, tmp;
    for (i = 1; i &lt; size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j &gt;= 0 && a[j] &gt; tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}


Сортировка Шелла

Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.
Реализация
int increment(long inc[], long size) 
{
    int p1, p2, p3, s;
    p1 = p2 = p3 = 1;
    s = -1;
    do 
    {
        if (++s % 2) 
        {
            inc[s] = 8*p1 - 6*p2 + 1;
        } 
        else 
        {
            inc[s] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
    p1 *= 2;
    } 
    while(3*inc[s] &lt; size);  
 
    return s &gt; 0 ? --s : 0;
}
 
template&lt; class T &gt;
void shellSort(T a[], long size) 
{
    long inc, i, j, seq[40];
    int s;
 
    s = increment(seq, size); // вычисление последовательности приращений
    while (s &gt;= 0)  // сортировка вставками с инкрементами inc[] 
    {
         inc = seq[s--];
         for (i = inc; i &lt; size; ++i) 
         {
             T temp = a[i];
             for (j = i-inc; (j &gt;= 0) && (a[j] &gt; temp); j -= inc)
                a[j + inc] = a[j];
             a[j] = temp;
         }
    }
}

Часто вместо вычисления последовательности во время каждого запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc
 &gt; size.

[B]Пирамидальная сортировка


Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).
Реализация
template&lt; class T &gt;
void downHeap(T a[], long k, long n) 
{
    //  процедура просеивания следующего элемента 
    //  До процедуры: a[k+1]...a[n]  - пирамида 
    //  После:  a[k]...a[n]  - пирамида 
    T new_elem;
    long child;
    new_elem = a[k];
    
    while(k &lt;= n/2) // пока у a[k] есть дети 
    {       
        child = 2*k;
        
        if( child &lt; n && a[child] &lt; a[child+1] ) //  выбираем большего сына 
            child++;
        if( new_elem &gt;= a[child] ) 
            break; 
        // иначе 
        a[k] = a[child];    // переносим сына наверх 
        k = child;
    }
    a[k] = new_elem;
}
 
template&lt; class T &gt;
void heapSort(T a[], long size) 
{
    long i;
    T temp;
 
  // строим пирамиду 
    for(i = size / 2 - 1; i &gt;= 0; --i) 
        downHeap(a, i, size-1);
  
  // теперь a[0]...a[size-1] пирамида 
 
    for(i=size-1; i &gt; 0; --i) 
    {
        // меняем первый с последним 
        temp = a[i]; 
        a[i] = a[0]; 
        a[0] = temp;
        // восстанавливаем пирамидальность a[0]...a[i-1] 
        downHeap(a, 0, i-1); 
    }
}

Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

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

Быстрая сортировка (сортировка Хоара)

"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Псевдокод.
quickSort ( массив a, верхняя граница N ) {
Выбрать опорный элемент p - середину массива
Разделить массив по этому элементу
Если подмассив слева от p содержит более одного элемента,
вызвать quickSort для него.
Если подмассив справа от p содержит более одного элемента,
вызвать quickSort для него.
}

Реализация на Си
template&lt;class T&gt;
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N;        // поставить указатели на исходные места
  T temp, p;
 
  p = a[ N&gt;&gt;1 ];        // центральный элемент
 
  // процедура разделения
  do {
    while ( a[i] &lt; p ) i++;
    while ( a[j] &gt; p ) j--;
 
    if (i &lt;= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i&lt;=j );
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j &gt; 0 ) quickSortR(a, j);
  if ( N &gt; i ) quickSortR(a+i, N-i);
}

Каждое разделение требует, очевидно, O(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Итеративный алгоритм быстрой сортировки.
Псевдокод.
Итеративная QuickSort (массив a, размер size) {
Положить в стек запрос на сортировку массива от 0 до size-1.
do {
Взять границы lb и ub текущего массива из стека.
do {
1. Произвести операцию разделения над текущим массивом a[lb..ub].
2. Отправить границы большей из получившихся частей в стек.
3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
} пока меньшая часть состоит из двух или более элементов
} пока в стеке есть запросы
}

Реализация на Си.
#define MAXSTACK 2048 // максимальный размер стека
template&lt;class T&gt;
void qSortI(T a[], long size) {
 
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
 
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
T pivot; // опорный элемент
T temp;
 
lbstack[1] = 0;
ubstack[1] = size-1;
 
do {
// Взять границы lb и ub текущего массива из стека.
lb = lbstack[ stackpos ];
ub = ubstack[ stackpos ];
stackpos--;
 
do {
// Шаг 1. Разделение по элементу pivot
ppos = ( lb + ub ) &gt;&gt; 1;
i = lb; j = ub; pivot = a[ppos];
do {
while ( a[i] &lt; pivot ) i++;
while ( pivot &lt; a[j] ) j--;
if ( i &lt;= j ) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i &lt;= j );
 
// Сейчас указатель i указывает на начало правого подмассива,
// j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
// Возможен случай, когда указатель i или j выходит за границу массива
 
// Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
if ( i &lt; ppos ) { // правая часть больше
if ( i &lt; ub ) { // если в ней больше 1 элемента - нужно
stackpos++; // сортировать, запрос в стек
lbstack[ stackpos ] = i;
ubstack[ stackpos ] = ub;
}
ub = j; // следующая итерация разделения
// будет работать с левой частью
} else { // левая часть больше
if ( j &gt; lb ) {
stackpos++;
lbstack[ stackpos ] = lb;
ubstack[ stackpos ] = j;
}
lb = i;
}
} while ( lb &lt; ub ); // пока в меньшей части более 1 элемента
} while ( stackpos != 0 ); // пока есть запросы в стеке
}

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Поразрядная сортировка

Рассматриваемый ниже алгоритм существенно отличается от описанных ранее.
Во-первых, он совсем не использует сравнений сортируемых элементов.
Во-вторых, ключ, по которому происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам...
typedef struct slist_ { 
  long val;
  struct slist_ *next; 
} slist;
 
// функция сортировки возвращает указатель на начало отсортированного списка 
slist *radix_list(slist *l, int t) {
  //  t - разрядность (максимальная длина числа) 
  int i, j, d, m=1;
  slist *temp, *out, *head[10], *tail[10];
  out=l;
 
  for (j=1; j&lt;=t; j++) { 
    for (i=0; i&lt;=9; i++)
      head[i] = (tail[i]=NULL);
 
    while ( l != NULL ) {
      d = ((int)(l-&gt;val/m))%(int)10;
      temp = tail[d];
      if ( head[d]==NULL ) head[d] = l;
      else temp-&gt;next = l;
      temp = tail[d] = l;
      l = l-&gt;next;
      temp-&gt;next = NULL;
    }
    for (i=0; i&lt;=9; i++)
      if ( head[i] != NULL ) break;
    l = head[i];
    temp = tail[i];
    for (d=i+1; d&lt;=9; d++) {
      if ( head[d] != NULL) { 
        temp-&gt;next = head[d];
        temp = tail[d];
      }
    }
    m*=10;
  }
  return (out);
}


Сортировка подсчётом

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

Код C++
void counting_sort (int *vec, int len, int min, int max) {
 
  int *cnt = new int[max-min+1];
 
  for(int i = min; i &lt;= max; ++i) cnt[i - min] = 0;
  for(int i = 0; i &lt; len; ++i) ++cnt[vec[i] - min];
 
  for(int i = min; i &lt;= max; ++i)
    for(int j = cnt[i - min]; j--;)
      *vec++ = i;
}

Добавлено: 30 Декабря 2014 19:20:28 Добавил: Андрей Ковальчук

Алгоритм Флойда-Уоршала. Поиск матрицы кратчайших путей. Матрица вершин через которые проходят кратчайшие пути. Поиск кратчайшего пути между двумя вершинами.

Код C++

//Floyd.h
#ifndef _FLOYD_H_
#define _FLOYD_H_
 
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stack>
 
typedef std::vector<std::vector<int> > VM;
typedef std::stack<int> ST;
 
class MatrixAdj
{
public:
    MatrixAdj()
    {
    }
 
    virtual ~MatrixAdj()
    {
    }
 
    void SetSize(const size_t n)
    {
        Matr.resize(n);
        for(size_t i=0; i<n; ++i)
            Matr[i].resize(n);
    }
 
    void Fill()
    {
        for(size_t i=0; i<Matr.size(); ++i)
        {
            for(size_t j=0; j<Matr.size(); ++j)
            {
                if(i==j)
                    Matr[i][j]=0;
                else if(i>j)
                {
                    Matr[i][j]=Matr[j][i];
                }
                else
                {
                    std::cout<<"Enter weight of V"<< i <<",V"<< j <<" edge\n"
                        <<"0 for not connect them\n";
                    std::cin>>Matr[i][j];
                    if(Matr[i][j]==0)
                        Matr[i][j]=100;
                }
            }
        }
    }
protected:
    VM Matr;
};
 
class Floyd:public MatrixAdj
{
public:
    Floyd():MatrixAdj()
    {
    }
 
    ~Floyd()
    {
    }
 
    void Initialise()
    {
        MatrPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrPath[i].resize(Matr.size());
        for(size_t i=0; i<MatrPath.size(); ++i)
        {
            for(size_t j=0; j<MatrPath.size(); ++j)
            {
                if(Matr[i][j]==100)
                    MatrPath[i][j]=100;
                else
                    MatrPath[i][j]=j;
            }
        }
        Copy();
    }
    
    void FindPathMatr()
    {
        for(size_t k=0; k<Matr.size(); ++k)
        {
            for(size_t i=0; i<Matr.size(); ++i)
            {
                for(size_t j=0; j<Matr.size(); ++j)
                {
                    int b=MatrSPath[i][k]+MatrSPath[k][j];
                    if(b<MatrSPath[i][j])
                    {
                        MatrSPath[i][j]=b;
                        MatrPath[i][j]=k;
                    }
                }
            }
        }
    }
 
    void FindPath(size_t first, size_t second)
    {
        if(first>=MatrPath.size() || second>=MatrPath.size())
            throw std::invalid_argument("One of nodes for searching is more than Matr size");
        ST Goals;
        Path.push(first);
        Goals.push(second);
        while(!Goals.empty())
        {
            int u=Path.top();
            int v=Goals.top();
            int s=MatrPath[u][v];
            if(v==s)
            {
                Path.push(v);
                Goals.pop();
            }
            else
                Goals.push(s);
        }
    }
 
    void PrintWMatr(std::ostream& os) const
    {
        PrintMatr(Matr, os);
    }
 
    void PrintSPMatr(std::ostream& os) const
    {
        PrintMatr(MatrSPath, os);
    }
 
    void PrintPMatr(std::ostream& os) const
    {
        PrintMatr(MatrPath, os);
    }
 
    void PrintSt(std::ostream& os)
    {
        while(!Path.empty())
        {
            os<<Path.top()<<' ';
            Path.pop();
        }
        os<<'\n';
    }
private:
    VM MatrPath;
    VM MatrSPath;
    ST Path;
    
    void PrintMatr(const VM& Vec, std::ostream& os) const
    {
        for(size_t i=0; i<Vec.size(); ++i)
        {
            for(size_t j=0; j<Vec.size(); ++j)
            {
                os<<std::setw(3)<<Vec[i][j]<<' ';
            }
            os<<'\n';
        }
    }
 
    void Copy()
    {
        MatrSPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrSPath[i].resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            std::copy(Matr[i].begin(), Matr[i].end(), MatrSPath[i].begin());
    }
};
 
std::ostream& operator <<(std::ostream& os, const Floyd& Ob)
{
    os<<"Weight matrix\n";
    Ob.PrintWMatr(os);
    os<<"Shortest paths matrix\n";
    Ob.PrintSPMatr(os);
    os<<"Shortest path nodes matrix\n";
    Ob.PrintPMatr(os);
    return os;
}
 
#endif

Код C++
//Floyd.cpp
#include "Floyd.h"
 
int main()
{
    try
    {
        int n;
        std::cout<<"Enter numb of nodes: ";
        std::cin>>n;
        Floyd Ob;
        Ob.SetSize(n);
        Ob.Fill();
        Ob.Initialise();
        Ob.FindPathMatr();
        std::cout<<Ob;
        size_t first, second;
        std::cout<<"Enter first and second nodes for search path between them\n";
        std::cin>>first>>second;
        Ob.FindPath(first, second);
        std::cout<<"Shortest path between " << first <<" and "<< second <<" nodes is\n";
        Ob.PrintSt(std::cout);
    }
    catch(std::exception& e)
    {
        std::cerr<<e.what()<<'\n';
        return 1;
    }
    return 0;
}

Добавлено: 26 Сентября 2013 01:08:16 Добавил: Андрей Ковальчук

Алгоритм Уоршалла

Код C++

//Matrix_adj.h
#ifndef _MATRIX_ADJ_H_
#define _MATRIX_ADJ_H_
 
#include <vector>
 
class AdjMatr
{
public:
   AdjMatr()
   {
      VecAdj.resize(0);
      VecPath.resize(0);
   }
   ~AdjMatr(){}
   void input();
   void output(const std::vector<std::vector<int> >& Vec);
   void resize(size_t size);
   void find_path();
   void copy_matr();
   size_t set_size();
private:
   std::vector<std::vector<int> > VecAdj;
   std::vector<std::vector<int> > VecPath;
};
 
#endif /*ifndef Matrix_adj*/

Код C++
//Matrix_adj.cpp
#include "Matrix_adj.h"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
void AdjMatr::resize(size_t size)
{
   VecAdj.resize(size);
   for(size_t i=0; i<size; ++i)
      VecAdj[i].resize(size);
}
 
void AdjMatr::copy_matr()
{
   VecPath.resize(VecAdj.size());
   for(size_t i=0; i!=VecAdj.size(); i++)
   {
      VecPath[i].resize(VecAdj[i].size());
      std::copy(VecAdj[i].begin(), VecAdj[i].end(), VecPath[i].begin());
   }
}
 
void AdjMatr::input()
{
   size_t size=set_size();
   resize(size);
   for(size_t i=0; i<size; ++i)
   {
      for(size_t j=0; j<size; ++j)
      {
         if(i==j)
         {
            VecAdj[i][j]=0;
            continue;
         }
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node and 0 for not\n";
         std::cin>>VecAdj[i][j];
      }
   }
   std::cout<<"Initial adj matrix\n";
   output(VecAdj);
}
 
size_t AdjMatr::set_size()
{
   size_t size;
   std::cout<<"Enter size: ";
   std::cin>>size;
   return size;
}
 
void AdjMatr::output(const std::vector<std::vector<int> >& Vec)
{
   for(size_t i=0; i<Vec.size(); ++i)
   {
      std::copy(Vec[i].begin(), Vec[i].end(), std::ostream_iterator<int>(std::cout, " "));
      std::cout<<std::endl;
   }
}
 
void AdjMatr::find_path()
{
   copy_matr();
   std::cout<<"Initial path matrix\n";
   output(VecPath);
   for(size_t k=0; k<VecPath.size(); ++k)
   {
      for(size_t i=0; i<VecPath.size(); ++i)
      {
         if(VecPath[i][k]==1)
         {
            for(size_t j=0; j<VecPath.size(); ++j)
            {
               VecPath[i][j]=(VecPath[i][j]||VecPath[k][j]);
            }
         }
      }
   }
   std::cout<<"Path matrix\n";
   output(VecPath);
}


Код C++
//Main.cpp
#include "Matrix_adj.h"
 
#include <iostream>
 
int main()
{
   AdjMatr Ob;
   Ob.input();
   Ob.find_path();
   system("pause");
   return 0;
}

Добавлено: 26 Сентября 2013 01:05:48 Добавил: Андрей Ковальчук

Метод хорд

Код C++

double secant(double infinum, double supremum, double epsilon)
{
    while (fabs(supremum - infinum) > epsilon)
    {
        infinum = supremum - (supremum - infinum) * func(supremum) / (func(
                supremum) - func(infinum));
        supremum = infinum - (infinum - supremum) * func(infinum) / (func(
                infinum) - func(supremum));
    }
 
    return supremum;
}

Добавлено: 26 Сентября 2013 01:03:02 Добавил: Андрей Ковальчук

Фибоначчи

Код C++

#include <iostream>
#define eps 1e-3
int F(int n)
{
    int f, f1(1), f2(1), m(0);
    while(m < n - 1)
    {
        f = f1 + f2;
        f1 = f2;
        f2 = f;
        ++m;
    }
    return f1;
}
void Fib(double a, double b)
{
    std::cout<<"\n\n\n\tМетод Фибоначчи:\n";
    double x1, x2, _x, xf1, xf2;
    int k(0);
    int N(0);
    double fn1(1), fn2(1), fn, f = (b - a) / eps;
    while(fn1 < f)
    {
        fn = fn1 + fn2;
        fn1 = fn2;
        fn2 = fn;
        ++N;
    }
    x1 = a + (double)F(N - 2) / F(N) * (b - a) - (N&1 ? -1 : 1) * eps / F(N);
    x2 = a + (double)F(N - 1) / F(N) * (b - a) + (N&1 ? -1 : 1) * eps / F(N);
    xf1 = Fun(x1);
    xf2 = Fun(x2);
  P:
    ++k;
    if(xf1 >= xf2)
    {
        a = x1;
        x1 = x2;
        xf1 = xf2;
        x2 = a + (double)F(N - k - 1) / F(N - k) * (b - a) + ((N - k)&1 ? -1 : 1) * eps / F(N - k);
        xf2 = Fun(x2); 
    }
    else
    {
        b = x2;
        x2 = x1;
        xf2 = xf1;
        x1 = a + (double)F(N - k - 2) / F(N - k) * (b - a) - ((N - k)&1 ? -1 : 1) * eps / F(N - k);
        xf1 = Fun(x1);
    }
    if(fabs(b - a) <= eps)
    {
        _x = (a + b) / 2;
        std::cout<<"Результат:\nx = "<<_x<<"\t\tF(x) = "<<Fun(_x)<<
            "\nКоличество итераций: "<<k;
    }
    else
        goto P;
}

Добавлено: 26 Сентября 2013 01:02:23 Добавил: Андрей Ковальчук

Дихотомии(половинного деления)

Код C++

double dichotomy(double infinum, double supremum, double epsilon) {
   double x;
   while (supremum - infinum > epsilon) {
      x = (infinum + supremum) / 2;
      if (func(supremum) * func(x) < 0)
         infinum = x;
      else
         supremum = x;
   }
   return (infinum + supremum) / 2;
}

Добавлено: 26 Сентября 2013 01:01:13 Добавил: Андрей Ковальчук

Метод половинного деления

Код C++

#include <conio.h>
#include <math.h>
#include <iostream.h>
#define pi 3.14
 
double f(double x) {
 
    return   x*x-(cos(pi*x));
}
int main() {
    int n=0;
    double a,b,c,eps;
    cout<<"a="; cin>>a;
    cout<<"b="; cin>>b;
    cout<<"eps="; cin>>eps;
    do {
        c=(a+b)/2;
        if (f(c)*f(a)<=0) b=c;
        else a=c;
 
        n+=1;
 
    }
    while (fabs(a-b)>=eps);
        cout<<"c="<<c<<"\n";
        cout<<"n="<<n<<"\n";
        getch();
    return 0;
}

Добавлено: 26 Сентября 2013 01:00:41 Добавил: Андрей Ковальчук

Новый алгоритм получения Google PageRank

Буквально на днях Google поменял алгоритм, по которому генерировалась ссылка для получения показателей Google PageRank. В результате этого отвалились многие сервисы, вспомогательные программы, сторонние тулбары, счетчики и еще бессчетное количество сеошного барахла. Мне было бы глубоко фиолетово на их проблемы, но у меня на сайте тоже используется система автоматического съема значений Google PR. Поэтому пришлось быстренько адаптироваться к новым условиям. Я установил себе гугловский тулбар, быстренько выпотрошил его и получил алгоритм генерации ссылки для получения Google PageRank. Вот как он выглядит на JavaScript:

<script type="text/javascript">
 
// Программисты Google явно с юмором :)
var HASH_SEED = "Mining PageRank is AGAINST GOOGLE'S TERMS OF SERVICE. "+
                 "Yes, I'm talking to you, scammer.";
 
// Расчет хэша строки запроса
awesomeHash = function(a) {
    var b = 16909125;
    for (c = 0; c < a.length; c++) {
        b ^= HASH_SEED.charCodeAt(c % HASH_SEED.length) ^ a.charCodeAt(c);
        b = b >>> 23 | b << 9;
    }    
    return '8'+hexEncodeU32(b);
};
 
// Перевод числа в HEX-значение
hexEncodeU32 = function(a) {
    var b = toHex8(a >>> 24);
    b += toHex8(a >>> 16 & 255);
    b += toHex8(a >>> 8 & 255);
    return b + toHex8(a & 255)
};
toHex8 = function(a) {
    return (a < 16 ? "0": "") + a.toString(16)
};
 
// Функция получения ссылки для запроса Google PR
getPageRankLink = function(a) {
    return 'http://toolbarqueries.google.ru/tbr?features=Rank'+
           '&client=navclient-auto-ff&ch='+awesomeHash(a)+'&q=info:'+
           encodeURIComponent(a);
}
</script>

Функция вызывается следующим образом. На входе подается ссылка на страницу, для которой требуется рассчитать Google PageRank, на выходе получаем ссылку, по которой можно узнать результат.
<script type="text/javascript">
 
// Пример использования
st='http://www.manhunter.ru/'
alert(getPageRankLink(st));
 
</script>

Результат запроса к гугловскому серверу возвращается в виде строки, например, "Rank_1:1:2". Последняя цифра и есть искомое значение рейтинга страницы. Алгоритм можно без особого труда перевести на другие языки программирования.

Например, вот моя реализация на Ассемблере. В секции данных предварительно подготовим следующие данные:
section '.data' data readable writeable
 
buff1   rb 500h         ; Буфер для исходной ссылки
buff2   rb 500h         ; Буфер для готовой ссылки
buff3   rb 100h         ; Хэш
 
mask    db '%.8X',0
 
p1      db 'http://toolbarqueries.google.ru/tbr?features='
        db 'Rank&client=navclient-auto-ff&ch=8',0
p2      db '&q=info:',0
 
HASH    db "Mining PageRank is AGAINST GOOGLE'S TERMS OF SERVICE. "
        db "Yes, I'm talking to you, scammer."
h_len   = $-HASH

А вот так вычисляется хэш и составляется ссылка. Код прокомментирован, остальное можно наглядно посмотреть в варианте JavaScript. Подразумевается, что в buff1 уже содержится исходная ссылка.
        ; Записать первую часть ссылки
        invoke  lstrcpy,buff2,p1
 
        ; Инициализация хэша
        mov     ebx,1020345h
        xor     ecx,ecx
 
        ; Вычисление хэша
.loc_encode:
        mov     al,byte [buff1+ecx]
        or      al,al
        jz      .loc_end_encode
 
        xor     bl,al
 
        push    ecx
        xor     edx,edx
        mov     eax,h_len
        xchg    eax,ecx
        div     ecx
        mov     al,byte [HASH+edx]
        xor     bl,al
        pop     ecx
 
        mov     eax,ebx
        shr     ebx,23
        shl     eax,9
        or      ebx,eax
 
        inc     ecx
        jmp     .loc_encode
 
.loc_end_encode:
 
        ; Добавить в ссылку строку хэша
        invoke  wsprintf,buff3,mask,ebx
        add     esp,12
        invoke  lstrcat,buff2,buff3
 
        ; Добавить вторую часть ссылки
        invoke  lstrcat,buff2,p2
        mov     edi,buff2
        invoke  lstrlen,buff2
        add     edi,eax
        mov     esi,buff1
 
        ; URL-encoded ссылка
.loc_scan:
        lodsb
        or      al,al
        jz      .loc_end
 
        cmp     al,':'
        jne     @f
 
        mov     eax,'%3A'
        stosd
        dec     edi
        jmp     .loc_scan
@@:
        cmp     al,'/'
        jne     @f
 
        mov     eax,'%2F'
        stosd
        dec     edi
        jmp     .loc_scan
@@:
        cmp     al,'?'
        jne     @f
 
        mov     eax,'%3F'
        stosd
        dec     edi
        jmp     .loc_scan
@@:
        cmp     al,'&'
        jne     @f
 
        mov     eax,'%26'
        stosd
        dec     edi
        jmp     .loc_scan
@@:
        stosb
        jmp     .loc_scan
 
.loc_end:
        xor     eax,eax
        stosb
        ; В buff2 теперь находится ссылка для получения PR

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

Добавлено: 17 Сентября 2013 07:44:05 Добавил: Андрей Ковальчук

Алгоритм Шинглов — поиск нечетких дубликатов текста

В этой статье я расскажу об алгоритме поиска нечетких дубликатов под названием «Алгоритм Шинглов». А так же реализую данный алгоритм на языке Python.

Почему я решил изучить данный алгоритм? Сам я являюсь SEO-шником, занимаюсь продвижением сайтов и так далее… Соответственно, моя работа заключается в изменении выдачи поисковой системы по определенному запросу. Но проработав более года в этом направлении меня заинтересовала внутренняя часть поисковых систем. Как они борются с поисковым спамом, как ранжируют документы и т.д. Поиск нечетких дубликатов позволяет поисковой системе исключить из выдачи клоны или частично похожие страницы (под словом частично я подразумеваю некоторое значение, при котором в конкретной поисковой системе два документа будут определяться как почти одинаковыми).


Одним из таких алгоритмов является «Алгоритм Шинглов» (шингл на английском означает чешуйка).

Немного теории


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

Обратите внимание, задачей не стоит определить абсолютное значение схожести объектов, а так же выделения в каждом из объектов схожих частей. Нам необходимо только предположить, являются ли объекты почти дубликатами или нет.

Где может применяться данный алгоритм?


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

Почти одинаковый текст


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

Другой пример, посложнее. Если мы в копии оригинального текста перепишем каждое 5-6е предложение, то текст по-прежнему будет являться почти дублем.

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

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

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

Как работает алгоритм Шинглов?


Итак, мы имеем 2 текста и нам нужно предположить, являются ли они почти дубликатами. Реализация алгоритма подразумевает несколько этапов:

канонизация текстов;
разбиение текста на шинглы;
нахождение контрольных сумм;
поиск одинаковых подпоследовательностей.
Теперь поконкретнее. В алгоритме шинглов реализовано сравнение контрольных сумм текстов. В своей реализации я использую [URL=http://ru.wikipedia.org/wiki/%D0%A6%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B8%D0%B7%D0%B1%D1%8B%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4]CRC32[/URL], но применимы и другие, например [URL=http://ru.wikipedia.org/wiki/SHA1]SHA1[/URL] или [URL=http://ru.wikipedia.org/wiki/MD5]MD5[/URL] и т.д. Как известно, контрольные суммы статических функций очень чувствительны к изменениям. Например, контрольные суммы двух следующих текстов будут в корне отличаться:

- Текст: «My war is over.» Контрольная сумма: 1759088479
- Текст: «My war is over!» Контрольная сумма: -127495474
Как сказал Джон Рэмбо: «My war is over». Но сказать он это мог по-разному, громко восклицая или тихо шепча, так и у нас, отличие второй фразы от первой заключается всего лишь в восклицательном знаке в конце фразы, но как видим, контрольные суммы абсолютно разные.

При поиске почти дубликата нас не интересуют всякие там восклицательные знаки, точки, запятые и т.д. Нас интересуют только слова (не союзы, предлоги и т.д., а именно слова).

Следовательно, ставится задача: очистить текст от ненужных нам знаков и слов, которые не несут смысла при сравнении, это и называется «привести текст к канонической форме».

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

Давайте что-нибудь напрограммируем. Допустим, мы имеем два текста, занесем их в 2 переменных: source1 и source2. Нужно их почистить от ненужных символов и слов. Определим наборы стоп-слов и стоп-символов.
stop_symbols = '.,!?:;-\n\r()'

stop_words = (u'это', u'как', u'так',
  u'и', u'в', u'над',
  u'к', u'до', u'не',
  u'на', u'но', u'за',
  u'то', u'с', u'ли',
  u'а', u'во', u'от',
  u'со', u'для', u'о',
  u'же', u'ну', u'вы',
  u'бы', u'что', u'кто',
  u'он', u'она')

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

Создадим функцию, которая будет производить канонизацию текста:
def canonize(source):
  stop_symbols = '.,!?:;-\n\r()'

  stop_words = (u'это', u'как', u'так',
    u'и', u'в', u'над',
    u'к', u'до', u'не',
    u'на', u'но', u'за',
    u'то', u'с', u'ли',
    u'а', u'во', u'от',
    u'со', u'для', u'о',
    u'же', u'ну', u'вы',
    u'бы', u'что', u'кто',
    u'он', u'она')

  return ( [x for x in [y.strip(stop_symbols) for y in source.lower().split()] if x and (x not in stop_words)] )

Функция canonize очищает текст от стоп-символов и стоп-слов, приводит все символы строки к нижнему регистру и возвращает список, оставшихся после чистки слов.

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

Итак, тексты у нас очищены от всего лишнего. Теперь необходимо разбить каждый из них на подпоследовательности — шинглы. На практике я применяю подпоследовательности длинной в 10 слов. Из выделенных нами шинглов далее будут находиться контрольные суммы.

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

«Разум дан человеку для того, чтобы он разумно жил, а не для того только, чтобы он понимал, что он неразумно живет.»© В. Г. Белинский


После обработки нашей функцией текст примет следующий вид:

разум дан человеку того чтобы разумно жил того только чтобы понимал неразумно живет


Это и есть каноническая форма. Теперь нужно разбить ее на шинглы длиной в 10 слов. Так как шинглы составляются внахлест, то всего шинглов len(source)-(shingleLen-1), т.е. количество слов в тексте минус длина шинглов плюс 1.

Шинглы будут выглядеть следующим образом:

- Sh1 = разум дан человеку того чтобы разумно жил того только чтобы
- Sh2 = дан человеку того чтобы разумно жил того только чтобы понимал
- Sh3 = человеку того чтобы разумно жил того только чтобы понимал неразумно
- Sh4 = того чтобы разумно жил того только чтобы понимал неразумно живет

Напишем функцию, которая производит разбиение текста на шинглы:
def genshingle(source):
  shingleLen = 10 #длина шингла
  out = [] 
  for i in range(len(source)-(shingleLen-1)):
    out.append (' '.join( [x for x in source[i:i+shingleLen]] ).encode('utf-8'))

  return out

Но так как нас интересую именно контрольные суммы шинглов, то соответственно изменим нашу функцию. Мы будем использовать алгоритм хэширования CRC32, подключим библиотеку binascii, которая содержит в себе нужный нам метод. Измененная функция:
def genshingle(source):
import binascii
shingleLen = 10 #длина шингла
out = [] 
for i in range(len(source)-(shingleLen-1)):
out.append (binascii.crc32(' '.join( [x for x in source[i:i+shingleLen]] ).encode('utf-8')))

return out

Наш пример выдаст следующие наборы контрольных сумм:

[1313803605, -1077944445, -2009290115, 1772759749]
Таким образом, через наши 2 функции нужно прогнать 2 сравниваемых текста и мы получим 2 множества контрольных сумм шинглов, теперь необходимо найти их пересечения.
def compaire (source1,source2):
  same = 0
  for i in range(len(source1)):
    if source1[i] in source2:
    same = same + 1

  return same*2/float(len(source1) + len(source2))*100

Вот и все, функция нам вернет процент схожести двух текстов.

Скомпонованный код

# -*- coding: UTF-8 -*-
if __name__ == '__build__':
    raise Exception

def canonize(source):
        stop_symbols = '.,!?:;-\n\r()'

        stop_words = (u'это', u'как', u'так',
        u'и', u'в', u'над',
        u'к', u'до', u'не',
        u'на', u'но', u'за',
        u'то', u'с', u'ли',
        u'а', u'во', u'от',
        u'со', u'для', u'о',
        u'же', u'ну', u'вы',
        u'бы', u'что', u'кто',
        u'он', u'она')

        return ( [x for x in [y.strip(stop_symbols) for y in source.lower().split()] if x and (x not in stop_words)] )

def genshingle(source):
    import binascii
    shingleLen = 10 #длина шингла
    out = [] 
    for i in range(len(source)-(shingleLen-1)):
        out.append (binascii.crc32(' '.join( [x for x in source[i:i+shingleLen]] ).encode('utf-8')))

    return out

def compaire (source1,source2):
    same = 0
    for i in range(len(source1)):
        if source1[i] in source2:
            same = same + 1

    return same*2/float(len(source1) + len(source2))*100

def main():
    text1 = u'' # Текст 1 для сравнения
    text2 = u'' # Текст 2 для сравнения

    cmp1 = genshingle(canonize(text1))
    cmp2 = genshingle(canonize(text2))


    print compaire(cmp1,cmp2)

# Start program
main()

Я показал именно реализацию ядра алгоритма, но его можно дорабатывать до бесконечности, увеличивая его производительность и точность сравнения.

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

Так же, для увеличения производительности при обработке больших объемов текста можно сравнивать не все полученные контрольные суммы, а только те, которые, например, делятся на 25, или любое целое число в пределах от 10 до 40. Как показали тесты, это дает
значительный(!)
прирост скорости и не сильно уменьшает точность, но только при обработке больших объемов.

Добавлено: 17 Сентября 2013 01:47:18 Добавил: Андрей Ковальчук