Java
приведена классическая сортировка Хоара
Листинг 5 :
1 function quickSort( l, h, type ) { 2 var low = l; 3 var high = h; 4 var rt = eval( "txt[ " + Math.round( ( l + h ) / 2 ) + " ]" ); 5 var middle = new fillArray( rt.years, rt.books, rt.authors ); 6 7 do { 8 9 while( isLow( eval( "txt[ " + low + " ]" ), middle, type ) ) 10 low++; 11 12 while( isLow( middle, eval( "txt[ " + high + " ]" ), type ) ) 13 high--; 14 15 if( low <= high ) { 16 var temp = txt[ low ]; 17 txt[ low++ ] = txt[ high ] 18 txt[ high-- ] = temp; 19 } 20 } while( low <= high ); 21 22 if( l < high ) 23 quickSort( l, high, type ); 24 if( low < h ) 25 quickSort( low, h, type ); 26 }
В листинге 5 приведена классическая сортировка Хоара, но с небольшими модификациями. На этих модификациях я и хочу обратить внимание прежде всего. ИтаК, посмотрим на строки 4-5. Здесь создается новый элемент на основании данных элемента массива, который берется как среднее значение между границами цикла сортировки. Почему пришлось внести такую модификацию? Почему нельзя было написать классически, как и положено в сортировке Хоара: var middle = eval( "txt[ " + Math.round( ( l + h ) / 2 ) + " ]" );? Дело в том, что здесь не получено значения элемента массива, как в классической сортировке, а есть только ссылка на него (хотя слово ссылка здесь не совсем уместно). При таком подходе дальнейшие действия теряют смысл. Немного отклонюсь от темы моей статьи и разъясню этот момент. Приведу следующий листинг:
Листинг 6 :
1 function cls() { 2 this.member = "value"; 3 } 4 5 var x = new cls(); 6 var y = x; 7 alert( "x.member = " + x.member + ", y.member = " + y.member ); 8 x.member = "new value"; 9 alert( "x.member = " + x.member + ", y.member = " + y.member );
Что происходит после того, как на восьмой строке было присвоено члену класса новое значение? Изменится ли только значение в переменной x? Нет, изменится значение в обеих переменных. Дело в том, что присваивания значения созданного пользовательского класса не происходит. Попробую провести похожую аналогию со ссылками в языке С++. Я не получу автономного значения, которое было бы независимо от оригинала. А получу своего рода ссылку на значение, которое подвержено изменениям из оригинальной переменной. Такая ссылка разрушает всю семантику сортировки Хоара, поскольку алгоритм требует сравнения в процессе сортировки с опорным значением середины диапазона элементов, а сам алгоритм в процессе работы может заменять значение, находящееся по адресу опорного элемента другим значением. Именно поэтому мне пришлось создать отдельное значение через оператор new. Конечно, это влечет дополнительные затраты процессорного времени на повторное определение "весовых" значений данных, но эти затраты достаточно минимальны. Впрочем, если у вас есть желание, вы можете модифицировать функцию fillArray так, чтобы она принимала шесть аргументов. В качестве трех последних аргументов можно заносить уже полученные ранее данные о "весовом" значении членов массива.
Итак, я выяснил зачем требуется создавать новый элемент в сортировке Хоара. Перейду теперь к строкам 9 и 12. Здесь в качестве сравнения значений элементов вызывается функция isLow, которая принимает в качестве аргументов два объекта для сравнения и третий аргумент - имя члена класса, по которому производится сортировка (внимательный читатель уже заметил этот третий непонятный аргумент в алгоритме Хоара). Приведу эту функцию сравнения:
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий