javascript crashing when running quicksort

Question

I'm trying to write a quicksort in javascript and display the sorted output. But Whenever I run the execute() function the program hangs and stopped responding. Why is this? I'm not so familiar with javascript and I just translated this from my java code. But I just don't see why it didn't work. Here the code.

<script type="text/javascript">
function exchange(a, i, j) {
   var k = a[i];
   a[i] = a[j];
   a[j] = k;
}
function partition(a2, lo, hi) {
   var i2 = lo;
   var j2 = hi + 1;
   var v = a2[lo];
   while (true) {
       while (a2[++i2] < v) {
          if (i2 == hi) {
              break;
          }
       }
       while (v < a2[--j2]) {
         if (j2 == lo) {
            break;
         }
       }
       if (i2 >= j2) {
          break;
       }
       exchange(a2, i2, j2);
   }
   exchange(a2, lo, j2);
   return j2;
}
function sort(a3, lo2, hi2) {
   var j3 = partition(a3, lo2, hi2);
   sort(a3, lo2, j3 - 1);
   sort(a3, j 3+ 1, hi2);
}
function sort(a4) {
   sort(a4, 0, a.length - 1);
}
function execute() {
   var array = document.getElementById("texts").value.split(' ');
   sort(array);
   for (a in array) {
       document.write(array[a] + "<br>");
   }
}
</script>

This looks funny: sort(a3, j 3+ 1, hi2);. That should be j3, right? — Guffa
– Guffa, Commented Jul 25, 2014 at 16:00
Guessing you are either blowing the stack because of a recursive call that goes too deep, or the browser is becoming unresponsive because a section of code is taking too long to execute. Also, you have 2 definitions of sort(). JavaScript doesn't support overloaded methods in the usual OOP way. That's probably part of the issue. I'm guessing you're calling the second definition of sort(). That's why you didn't catch what @Guffa is pointing out in his comment. Because that code isn't executed. — pje
– pje, Commented Jul 25, 2014 at 16:08
@pge, I didn't know about java script not doing the same as OOP does. I just translated this from java I didn't rewrite it. Can you explain further regarding the overloaded methods? And about the second definition of sort you mean the recurssive sort with 3 parameters or the sort with 1? Which is not exxecuting? — lightning_missile
– lightning_missile, Commented Jul 25, 2014 at 16:31
@pje, I didn't know about java script not doing the same as OOP does. I just translated this from java I didn't rewrite it. Can you explain further regarding the overloaded methods? And about the second definition of sort you mean the recurssive sort with 3 parameters or the sort with 1? Which is not exxecuting? – — lightning_missile
– lightning_missile, Commented Jul 26, 2014 at 4:10

pje · Accepted Answer · 2014-07-25 18:10:24Z

1

Unless you are implementing quick-sort just for fun, consider using the sort() method on the Array object:

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.sort(); // result: Apple,Banana,Mango,Orange

When sorting numbers, pass a function to sort() to determine whether to sort in ascending or descending order:

var numbers = [2,41,5,2,16,7];
numbers.sort(function (a,b) { return a-b; });
// result: 2,2,5,7,16,41

If you want to implement quick sort in JavaScript just for fun, consider reading through: http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/. It gives a nice walkthrough of the algorithm, and some example code.

Reference:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

edited Jul 25, 2014 at 18:10

answered Jul 25, 2014 at 16:14

pje

2,4681 gold badge26 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user3717117 · Accepted Answer · 2014-07-25 16:30:42Z

try this code

<html>
<head>
<title>Quicksort</title>
<script type="text/javascript" src="quicksort.js" >
</script>
</head>
<body>
<form id="qsform" action="" method="" >
<input type="text" size="80" name="unsorted" value="S C K U P E M I B R" /> <br />
<input type="button" name="sort" value="Sort" onclick="dosort(this.form)" /> <br />
<input type="text" size="80" name="sorted" value="" />
</form>
</body>
</html>

and the javacsript code for this form is given below

   Array.prototype.swap=function(i, j)
   {
   var tmp=this[i];
   this[i]=this[j];
   this[j]=tmp;
   }

   function partition(array, a2, lo, hi)
   {
   var piv=array[hi];
   array.swap(hi, lo-1);
   var store=a2;
   var ix;
   for(ix=a2; ix<lo-1; ++ix) {
   if(array[ix]<=piv) {
   array.swap(store, ix);
   ++store;
   }
   }
   array.swap(lo-1, store);

   return store;
   }

   function qsort(array, a2, lo)
   {
   if(lo-1>a2) {
   var hi=a2+Math.floor(Math.random()*(lo-a2));

   hi=partition(array, a2, lo, hi);

   qsort(array, a2, hi);
   qsort(array, hi+1, lo);
   }
   }

   function quick_sort(array)
   {
   qsort(array, 0, array.length);
   }

   function dosort(form)
   {
   var array=form.unsorted.value.split(/ +/);

   quick_sort(array);

   form.sorted.value=array.join(' ');
   }

Collectives™ on Stack Overflow

javascript crashing when running quicksort

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related