Saturday, April 9, 2011

JavaScript version of QuickSort

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
  <head>
    <title></title>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <style type="text/css">
        body {
          text-align:center;
          font-family:"arial",verdana,sans-serif;
          background-color: #f2f2f2;
        }
        #wrapper{
          margin: 0 auto;
          width: 900px;
          text-align: left;
          background: white;
        }
        #innerWrapper{
          margin-left: 20px;
        }
        #qsDataOrg, #qsDataAns{
            color: gray;
        }
    </style>
    <script type="text/javascript">
        function QuickSort() {
            this.qsData = [];
            this.nElem = 0;
        }
        QuickSort.prototype.insert = function(val) {
            this.qsData[this.nElem] = val;
            this.nElem++;
        };
        QuickSort.prototype.numOfElement = function() {
            return this.nElem;
        }
        QuickSort.prototype.display = function(id) {
          var qsdOrg = document.getElementById(id);
          for (i = 0; i < this.nElem; i++ ) {
            qsdOrg.appendChild(document.createTextNode(this.qsData[i]));
            qsdOrg.appendChild(document.createTextNode(" "));
          }
        };
        QuickSort.prototype.sort = function (left, right) {
            // base case is: (right-left <= 0), omitted in code
            if ((right - left) > 0) {
                var pivot = this.qsData[right];
                var px = this.partition(left, right, pivot);
                this.sort(left, px - 1);
                this.sort(px + 1, right);
                return;
            }
        };
        QuickSort.prototype.partition = function(left, right, pivot) {
            var temp = right;
            var flag = true;
            while (flag) {
                while (this.qsData[left] < pivot) {
                    left++;
                }
                while ((right > 0) && (this.qsData[--right] > pivot)) {
                }
                if (left < right) {
                    this.swap(left, right);
                    left++;
                } else {
                    flag = false;
                }
            }
            this.swap(left, temp);
            return left;
        };
        QuickSort.prototype.swap = function(x , y) {
            var temp = this.qsData[x];
            this.qsData[x] = this.qsData[y];
            this.qsData[y] = temp;
        };
        // becuase the document has to be loaded, before script runs,
        // need window.onload. otherwise getElementBy stuff will return null
        window.onload = function(){
            var a = [2,41,15,93,23,5,63,10,4,43];
            var qs = new QuickSort();
            for (i = 0; i < a.length; i++) {
                qs.insert(a[i]);
            }
            //document.write("<br />"); <<< this wipes out display
            //  including "qsDataOrg" and gave me the null error for qsDataOrg.
            qs.display("qsDataOrg");
            qs.sort(0, qs.numOfElement() - 1);
            qs.display("qsDataAns");
        }
    </script>
  </head>
  <body>
    <div id="wrapper">
      <div id ="innerWrapper">
        <h2>This is a QuickSort project in JavaScript</h2>
        <div id="qsDataOrg">
            <p> The list of numbers to be sorted </p>
        </div>
        <div id="qsDataAns">
            <p> Here is the sorted list</p>
        </div>
      </div>
    </div>
  </body>
</html>

No comments:

Post a Comment