Реализации алгоритмов/Сортировка/Быстрая: различия между версиями
Содержимое удалено Содержимое добавлено
Slimbde (обсуждение | вклад) |
Отмена правки 157182, сделанной Slimbde (обсуждение) кажется вандализм Метка: отмена |
||
Строка 537:
== [[JavaScript]] ==
<source lang="javascript
/*
* Алгоритм быстрой сортировки
* @param data Array
▲ {
* @param compare function(a, b) - возвращает 0 если a=b, -1 если a<b и 1 если a>b (необязательная)
* @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)) { // Данные не являются массивом
};
if (f_compare === undefined) { // Будем использовать простую функцию (для чисел)
f_compare = (a, b) => {
if (a === b) {
return 0;
} else if (a > b) {
return 1;
} 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) => {
let i = l,
j = r,
x = a[l+r>>1];
//x = a[Math.floor(Math.random()*(r-l+1))+l];
// x = a[l]; // Если нет желания использовать объект Math
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>
|