Викиучебник

Реализации алгоритмов/Сортировка/Быстрая: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Строка 537:
== [[JavaScript]] ==
 
<source lang="javascript" line="1">
function srt(arr)
/*
{
* Алгоритм быстрой сортировки
if (arr instanceof Array)
*{
* @param data Array
if (arr.length < 2)
* @param compare function(a, b) - возвращает 0 если a=b, -1 если a<b и 1 если a>b (необязательная)
return arr;
* @param change function(a, i, j) - меняет местами i-й и j-й элементы массива а (необязательная)
*▼
*/
const qsort = (data, compare, change) => {
let a = data,
f_compare = compare,
f_change = change;
 
/*------------------------------+
if (!(a instanceof Array)) { // Данные не являются массивом
| [left][base] |
return undefined;▼
+------------------------------*/
};
let baseIndex = arr.length - 1;
if (f_compare === undefined) { // Будем использовать простую функцию (для чисел)
for (let i = 0; i < baseIndex; ++i)
f_compare = (a, b) => {
{
if (a === b) {
if (+arr[i] >= +arr[baseIndex])
return 0;
{
} else if (a > b) {
arr.push(arr.splice(i--, 1)[0]);
return 1;
--baseIndex;
} else {
}
return -1;
}
}
}
};
if (f_change === undefined) { // Будем использовать простую смену (для чисел)
f_change = (a, i, j) => {
const temp = a[i];
a[i] = a[j];
a[j] = temp;
}
};
 
/*------------------------------+
const qs = (l, r) => {
| [left][base][rest] |
let i = l,
+------------------------------*/
j = r,
let left = arr.splice(0, baseIndex);
x = a[l+r>>1];
let base = arr.splice(0, 1);
//x = a[Math.floor(Math.random()*(r-l+1))+l];
// now arr is the rest of it
// x = a[l]; // Если нет желания использовать объект Math
 
return srt(left).concat(base, srt(arr));
while (i <= j) {
▲ *}
while (f_compare(a[i], x) === -1) {
 
i++;
▲ return undefined;
}
while (f_compare(a[j], x) === 1) {
j--;
}
if (i <= j) {
f_change(a, i++, j--);
}
}
if (l < j) {
qs(l, j);
}
if (i < r) {
qs(i, r);
}
qs(0, a.length - 1);
}
}
</source>
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Быстрая