Как отсортировать массив

Здравствуйте, я в пхп середничок, на днях меня попросили на собеседовании расписать принцип сортировки одномерного массива по значению, не используя встроенные функции(ksort, usort и т.д.). Стыдно признать, но я ничего толкового с ходу не смог сочинить

Просьба профессионалов поделиться опытом: есть одномерный массив [3,2,45,67,12]. Как отсортировать его, не используя пользовательские функции ?

 

Спасибо rognorog за оперативный ответ. На собеседовании я попытался проделать нечто похожее через цикл for. Но видно оперативки у меня не хватило Растерялся под пристальным взглядом профессионалов. Скажи, много времени тебе потребовалось? Хочу также уметь быстро придумывать решения.

 

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

....

сорри, поторопился все правильно! Добавил еще значений и вышла путаница

Добавлено спустя 51 минуту 6 секунд:

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

 

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

 

Нашел функцию на хабре: http://rsdn.ru/article/alg/sort.xml "Сортировка вставками"
(Если чесс сказать даже не подозревал до этого дня, что алгоритмов сортировки существует аж целых 14).

адаптировал ее под пхп:

Код (Text):

1.  
2. $array=[545454545,3,2,1,67,234,876,124,776,9890];
3. $count=sizeof($array);
4.   // i определяет подсписок A[0]...A[i]
5.   for ($i=1; $i<$count; $i++)
6.   {
7.     // индекс j пробегает вниз по списку от A[i] в процессе
8.     // поиска правильной позиции вставляемого значения
9.     $j = $i;
10.     $temp = $array[$i];
11.     // обнаружить подходящую позицию для вставки, сканируя подсписок,
12.     // пока temp < A[j-1] или пока не встретится начало списка
13.     while ($j > 0 && $temp < $array[$j-1])
14.     {
15.       // сдвинуть элементы вправо, чтобы освободить место для вставки
16.       $array[$j] = $array[$j-1];
17.       $j--;
18.     }
19.     // точка вставки найдена; вставить temp
20.     $array[$j] = $temp;
21.   }
22.  
23.   print_r($array);

И все вроде работает как надо. Ну скажите, разве обычный человек может придумать такое за две-три минуты(время, которое мне отвели на тесте)?

 

Нашел для себя наиболее подходящее решение, метод "Быстрой сортировки":

Код (Text):

1.  
2. function quicksort($array)
3.     {
4.         if (count($array) == 0)
5.             return array();
6.         $pivot = $array[0];
7.         $left = $right = array();
8.         for ($i = 1; $i < count($array); $i++) {
9.             if ($array[$i] < $pivot)
10.                 $left[] = $array[$i];
11.             else
12.                 $right[] = $array[$i];
13.         }
14.         return array_merge(quicksort($left), array($pivot), quicksort($right));
15.     }
16.     $sorted = quicksort($array);