Реализовываю алгоритм быстрой сортировки, но она работает только когда элементов меньше чем +-3000. Если элементов больше - вылезает эта ошибка. Условие возврата есть, все работает правильно. В чем проблема и как ее решить? Вот код:
function getRandomIntInclusive(min, max) {
tf = 0;
min = Math.ceil(min);
max = Math.floor(max);
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function getBaseLog(x, y) {
return Math.log(y) / Math.log(x);
}
function check_sort(array){
var flag = true;
for (var i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
flag = false;
}
}
return flag;
}
function default_sort(array){
var flag = true;
while(flag){
flag = false;
for (var i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
flag = true;
var tmp = array[i];
array[i] = array[i + 1];
array[i + 1] = tmp;
}
}
}
return array;
}
function bubblesort(array){
var flag = true;
var k = 0;
var array_length = array.length;
var steps = Math.floor(array_length/100);
const time_start= new Date().getTime();
while(flag){
flag = false;
for (var i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
flag = true;
var tmp = array[i];
array[i] = array[i + 1];
array[i + 1] = tmp;
}
}
k++;
}
const time_end = new Date().getTime();
var ms = time_end - time_start;
console.log("Bubblesort - " + check_sort(array));
return ms;
}
function selection(array){
const time_start= new Date().getTime();
var fixed = 0;
var array_length = array.length;
var steps = Math.floor(array_length/100);
while (fixed < array.length - 1){
var exchange = fixed;
for (var i = fixed + 1; i < array.length; i++) {
if(array[exchange] > array[i]){
exchange = i;
}
}
if(exchange != fixed){
var temp = array[fixed];
array[fixed] = array[exchange];
array[exchange] = temp;
}
fixed++;
}
const time_end = new Date().getTime();
var ms = time_end - time_start;
console.log("Selection - " + check_sort(array));
return ms;
}
function shell(array){
var step = array.length;
const time_start= new Date().getTime();
var array_length = array.length;
var k = 0;
while (step > 1){
k++;
step = Math.floor(step/2);
for (var i = 0; i < step; i++) {
var tmpray = [];
for(var p = i; p <= array.length - 1; p += step){
tmpray.push(array[p]);
}
tmpray = default_sort(tmpray);
var j = 0;
for(var p = i; p <= array.length - 1; p += step){
array[p] = tmpray[j];
j++;
}
}
}
const time_end = new Date().getTime();
var ms = time_end - time_start;
console.log("Shell - " + check_sort(array));
return ms;
}
var mrg_steps;
var mrg_max;
var mrg_k;
function merge_recursive(array){
mrg_k += 1;
if(array.length > 1){
var array_1 = array.slice(0, Math.floor((array.length)/2));
var array_2 = array.slice(Math.floor((array.length)/2), array.length);
array = default_sort(merge_recursive(array_1).concat(merge_recursive(array_2)));
}
return array;
}
function merge(array){
mrg_max = array.length*2;
mrg_steps = Math.floor(mrg_max/100);
mrg_k = 1;
const time_start= new Date().getTime();
if(array.length > 1){
var array_1 = array.slice(0, Math.floor((array.length)/2));
var array_2 = array.slice(Math.floor((array.length)/2), array.length);
array = default_sort(merge_recursive(array_1).concat(merge_recursive(array_2)));
}
const time_end = new Date().getTime();
var ms = time_end - time_start;
console.log("Merge - " + check_sort(array));
return ms;
}
var k = 0;
function quicksort_recursive(start, end, array){
k++;
var i = start + 1;
var j = end;
var fixed = start;
while(1){
while(array[fixed] > array[i] && i < end){
i++;
}
while(array[j] >= array[fixed] && j > start){
j--;
}
if(i < j){
var tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
else {
var tmp = array[j];
array[j] = array[fixed];
array[fixed] = tmp;
break;
}
}
if(j > start) quicksort_recursive(start, j, array);
if(i < end) quicksort_recursive(i, end, array);
return;
}
function quicksort(array){
const time_start= new Date().getTime();
var start = 0;
var end = array.length - 1;
var i = start + 1;
var j = end;
var fixed = start;
while(1){
while(array[fixed] > array[i] && i < end){
i++;
}
while(array[j] >= array[fixed] && j > start){
j--;
}
if(i < j){
var tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
else {
var tmp = array[j];
array[j] = array[fixed];
array[fixed] = tmp;
break;
}
}
if(j > start) quicksort_recursive(start, j, array);
if(i < end) quicksort_recursive(i, end, array);
const time_end = new Date().getTime();
var ms = time_end - time_start;
console.log("Quick - " + check_sort(array));
return ms;
}
var array = [];
for (var i = 0; i < 9000; i++) {
array.push(getRandomIntInclusive(-200000, 200000));
}
console.log(bubblesort(array));
console.log(selection(array));
console.log(shell(array));
console.log(merge(array));
console.log(quicksort(array));
В общем, из-за выбора в качестве pivot первого элемента, вы попадаете на худший случай при отсортированном массиве на входе.
В итоге, каждый элемент порождает развилку и длина стека стремится к размеру задачи = N.
Каждый вызов отнимает некоторое количество памяти, и в итоге, в моём браузере стек заканчивается на глубине=6987.
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
У меня есть множество компоентов в dropdown спискеНадо чтобы при нажатии на любой из элементов списка, происходило конкретное действие
У меня есть массив содержащий массивы с пустыми строкамимне нужно удалить все массивы с пустыми строками и оставить только те,которые содержат...