Сортировка массива в php без использования sort(), работающая с русским текстом (array sort in cycle)

Мой пост на хабре http://habrahabr.ru/sandbox/66466/

Как-то давно проходил собеседование, и там была задача — не используя встроенных функций сортировки, отсортировать массив(вернее список имен из файла) от «а» до «я». Задачу тогда не смог решить и ушел ни с чем… И вот тут недавно вспомнил, стало интересно, каково же, все таки, решение?

Нашел кое-что тут: muruganasm.blogspot.com/2011/01/sort-array-of-string-without-using-php.html. Немного доработал для работы с именами. Например, есть файл listnames.txt:

Salopatan Dolot
   Lucara Vanibo
   Xyxelan Ubem
   Irabon Seboribal
   Abasixi Abubodul
   Sasipabi Itatop
   Latanybor Ocifil
   Obi Onu
   Laso pubyl
владимир петров
Илья бронштейн
Александр Мельников
  алексей шнырюк
512

Для вывода «по-красивее», решил обработать стринги функцией ucwords(). Но, как ни странно, она не захотела работать с русской кодировкой. setlocale() тоже не помогла нисколько. Тут, возможно сыграли настройки сервера. Вобщем, пошел довольно таки сложным путем. Надеюсь, кому-нибудь будет интересно:

<?php
$filename = 'listnames.txt';
$file_cont = (file_exists($filename))? file_get_contents($filename):die('No such file '.$filename);
$str2 = (!empty($file_cont))? preg_split("/[\n,]|[\r,]+/",$file_cont):die('No content was given from '.$filename);
print_r($str2);
$str = array_map("trim",$str2);
$str = array_map("ucwords", $str);
$str = array_map("non_en_to_uppercase", $str);
function non_en_to_uppercase($str){
    if( preg_match("/[А-я]{1,}+(\s+[А-я]{1,})?/i", $str)){
       $arr = preg_split("/[\s,]+/",$str);
       var_dump($arr);
       $new_str = "";
       foreach($arr as $word){
           $word = trim($word);
           $strlen = mb_strlen($word);
           $word = mb_strtoupper(mb_substr($word,0,1,'UTF-8'),'UTF-8') . mb_strtolower(mb_substr($word,1,$strlen),'UTF-8');
           $new_str .= " ".$word;
       }
       return trim($new_str);
    }
    else return $str;
}
$array_length = sizeof($str);

 for($x = 0; $x < $array_length; $x++) {
 
  for($y = 0; $y < $array_length; $y++) {
  
   
   if(strcasecmp($str[$x],$str[$y])<0) {
      $hold = $str[$x];
      $str[$x] = $str[$y];
      $str[$y] = $hold;
   }
  }
 }
$str = array_filter($str);
echo "<br />After sorting<br />";
print_r($str);
?>

Проверяем, если есть заданный файл. Если есть — читаем и построчно засовываем в массив $str2:

$file_cont = (file_exists($filename))? file_get_contents($filename):die('No such file '.$filename);
$str2 = (!empty($file_cont))? preg_split("/[\n,]|[\r,]+/",$file_cont):die('No content was given from '.$filename);

Удаляем пробелы, табуляцию с краев для каждого элемента массива:

$str = array_map("trim",$str2);

Приводим имена в «нормальный» вид. Т.е. иван петров в Иван Петров

$str = array_map("ucwords", $str);
$str = array_map("non_en_to_uppercase", $str);

Скорее всего, я где-то перемудрил с функцией non_en_to_uppercase(), но суть ее — проверить, если стринг в русской кодировке, и, если да, принудительно конвертировать первые буквы имени и фимилии в заглавные, а остальные — в строчные.

Далее в двойном цикле с помощью регистронезависимой функции strcasecmp сравниваем элементы массива, и меняем их местами в зависимости от результата сравнения:

 if(strcasecmp($str[$x],$str[$y])<0) {
      $hold = $str[$x];
      $str[$x] = $str[$y];
      $str[$y] = $hold;

Для примера Код:

$a = 'a';
$b = 'b';
echo strcasecmp($a,$b); //-1

выводит -1
и

echo strcasecmp($b,$a); //1

выдаст 1
Для пущей наглядности можно запустить этот код и увидеть, как элементы меняются местами:

$str = array('Z','c','A','C','E','B','M','N');
$array_length = sizeof($str);
 for($x = 0; $x < $array_length; $x++) { 
  for($y = 0; $y < $array_length; $y++) {  
   if(strcasecmp($str[$x],$str[$y])<0) {   
      $hold = $str[$x];
      $str[$x] = $str[$y];
      $str[$y] = $hold;
      echo "[$x] => $str[$x] <br />[$y] => $str[$y]<br /><br />";
   }
  }
 }

Напомню, что strcasecmp() не работает нормально с русской кодировкой. буквы «а» и «А» не равны. Поэтому мне пришлось выше приводить имена к единому регистру самописной функцией non_en_to_uppercase($str)

Теперь очистим вывод от пустых значений и печатаем отсортированный массив:

$str = array_filter($str);
echo "<br />After sorting<br />";
print_r($str);