www.webdeveloper.com
Results 1 to 8 of 8

Thread: [RESOLVED] bubble sort problems

Hybrid View

  1. #1
    Join Date
    May 2010
    Location
    midlands
    Posts
    4

    resolved [RESOLVED] bubble sort problems

    Hi guys,

    I'm new to JavaScript and I've got some javascript code that I'm trying to solve for my first uni course. I've emailed my tutor but they have not got back to me and I'm running out of time. If anyone can point me in the right direction then I would appreciate your help. I have entered the code I have done so far. I'm trying to get the inner and outer loop to count each time it is used so I can measure the efficiency of the programme. I'm also trying to get the programme to stop once the array is sorted and there is no more swaps to be done but as yet have no idea how to do this without using a while loop condition. I know there are better ways of doing this but this is how they want it done.

    function bubbleSort(arrayToSort)
    {
    // declare and initialise a variable to hold the length of the argument array
    var length = arrayToSort.length;

    //declare an array to be returned by the function
    var returnArray = new Array(length);
    //copy each element of the argument array to the return array
    for (var i = 0; i < length; i = i + 1)
    {
    returnArray[i] = arrayToSort[i];
    }

    // PLACE YOUR CODE FOR THE FUNCTION HERE
    /* */

    var temp;
    for (j = 0; j < returnArray.length - 1; j = j + 1)
    {

    for (k = 0; k < returnArray.length; k = k + 1)
    {

    if (returnArray[k] > returnArray[k + 1])
    {

    temp = returnArray[k + 1];

    returnArray[k + 1] = returnArray[k];

    returnArray[k] = temp;
    }
    }

    }
    total = j + k;
    window.alert ('The number of loops to sort the array was: ' + total);
    return returnArray;
    }

  2. #2
    Join Date
    May 2010
    Location
    midlands
    Posts
    4
    Ps I'm sorry I tried to get the code to indent in here but was unable to do it.

  3. #3
    Join Date
    Dec 2005
    Location
    FL
    Posts
    7,259
    I'm not sure if this is what you are after, but it does all but the finished early comparisons.

    It is mostly your code with an internal inner and outer loop count.

    I don't see how the internal counts would be changed in a bubble sort because the of the nature of the "bubble" requirements to check for lowest value and move.
    Add your own array comparison for equality to end early, but that would only happen
    if the scrambled array is nearly sorted already.

    Code:
    <html>
    <head>
    <title>Bubble Sort Example</title>
    <script type="text/javascript">
    // From: http://www.webdeveloper.com/forum/showthread.php?p=1087503#post1087503
    
    var ScrambledArray = []
    var BSortedArray = [];
    
    function TestSort() {
      ScrambledArray = []
      for (var i=0; i<100; i++) { ScrambledArray[i] = i; }
      ScrambledArray.sort(randOrd);
      document.getElementById('Original').innerHTML = 'Scrambled<p>'+DisplayArray(ScrambledArray);
      BSortedArray = bubbleSort(ScrambledArray);
      document.getElementById('Final').innerHTML = 'Sorted<p>'+DisplayArray(BSortedArray);
    }
    
    function DisplayArray(Arr) {
      var str = '';
      var tmp = '';
      for (var i=0; i<Arr.length; i++) {
    	  if ((i &#37; 5) == 0) { str += '<br>'; }
    	  tmp = Arr[i];  if (tmp<10) { tmp = '&nbsp;'+tmp; }
    	  str += tmp+'&nbsp;&nbsp;&nbsp;';
      }
      return str;	
    }
    function randOrd() {
      return (Math.round(Math.random())-0.5);
    }
    
    function bubbleSort(arrayToSort) {
      var outerCnt = 0;
      var innerCnt = 0;
    // declare and initialise a variable to hold the length of the argument array
      var length = arrayToSort.length;
    
    //declare an array to be returned by the function
      var returnArray = new Array(length);
    //copy each element of the argument array to the return array
      for (var i = 0; i < length; i = i + 1) { returnArray[i] = arrayToSort[i]; }
    
    // PLACE YOUR CODE FOR THE FUNCTION HERE
    /* */
    
      var temp;
      for (j = 0; j < returnArray.length - 1; j = j + 1) {
    	outerCnt++;
        for (k = 0; k < returnArray.length; k = k + 1) {
    	  innerCnt++;
          if (returnArray[k] > returnArray[k + 1]) {
            temp = returnArray[k + 1];
            returnArray[k + 1] = returnArray[k];
            returnArray[k] = temp;
          }
        }
      }
      total = j + k;
      var str = 'The number of loops to sort the array was: ' + total;
          str +='\n\nOuter Counts = '+outerCnt;
          str +='\n\nInner Counts = '+innerCnt;
      alert(str);    
      return returnArray;
    } 
    </script>
    </head>
    <body>
    <button onclick="TestSort()">Test Sort</button>
    <div id="Original" style="font-family:monospace;width:20%;border:1px solid red;float:left"></div>
    <div id="Final" style="font-family:monospace;width:20%;border:1px solid red;float:left"></div>
    <br style="clear:both">
    </body>
    </html>
    Code can be indented by use of the [ code] and [ /code] tags (without the spaces)
    to view as shown above.

  4. #4
    Join Date
    May 2010
    Location
    midlands
    Posts
    4
    Hi,

    Thank you for taking the time to try and help me and showing me how to insert code. You have helped me to see where I was going wrong with my count and I've been able to make the adaptations to get it working. The way we are being taught means that we are unable to use the style that most programmers use but its given me enough to work out what I had to do.

    I'm still finding it hard to work out how to stop the loop if there have been no swaps. I figure I need to use a Boolean condition but I'm not sure how to write the condition. I've tried using an else condition after the if but it then prevents any more swaps being done in the inner loop. Would I have to put the clause on the outer loop? If so how would I go about doing this.

    I don't mind you explaining in English what I need to do so I can convert it into code. I just need to get it in my head what I need to do.

  5. #5
    Join Date
    Dec 2005
    Location
    FL
    Posts
    7,259

    Lightbulb

    I know of no way to check if a bubble sort is finished early
    other than to go through the entire array at least once
    to check the current order and determine if swaps are required.

    You can create a function to do this easily, but it will add
    to the length of time that is required to perform the 'bubbleSort'
    function. At the end of each 2nd loop swap check, you can do
    something like check the status of the current array for any
    additional swaps that might be required.

    Code:
    function isSortFinished() {
      var needSwaps = 0;
      for (var i=0; i<BSortedArray.length-1; i++) {
        if (BSortedArray[i] > BSortedArray[i+1]) { needSwaps++; }
      }
      return needSwaps;
    }
    Then modify your sort code like:
    Code:
      var temp;
      for (j = 0; j < returnArray.length - 1; j = j + 1) {
    	outerCnt++;
        for (k = 0; k < returnArray.length; k = k + 1) {
    	  innerCnt++;
          if (returnArray[k] > returnArray[k + 1]) {
            temp = returnArray[k + 1];
            returnArray[k + 1] = returnArray[k];
            returnArray[k] = temp;
          }
        }
        if (isSortFinished() == 0) { break; }
      }
    Could also put check before the first outer loop to see if 'BSortedArray'
    is already in sorted order and not go through the sort loop to begin with.

    All code above is untested, so make sure you understand my comments before you do the modifications.
    Post back if you don't understand my comments.

    Good Luck!

  6. #6
    Join Date
    May 2010
    Location
    midlands
    Posts
    4
    Thank you, I do understand what you are talking about as I was thinking along the same lines. I had some inspiration late last night in bed. (I'm sure that is when my brain works at its best. I already have some code that counts the swaps so it should be pretty easy to then write a condition for it. I'm going to have a play around with it now and see if it gets me anywhere. Thanks for all your help and putting me on the right road.

  7. #7
    Join Date
    Dec 2005
    Location
    FL
    Posts
    7,259
    You're most welcome.
    Happy to help.
    Good Luck!

  8. #8
    Join Date
    May 2010
    Posts
    1
    why not just add numberOfSwaps in yout if statement?

    if (returnArray[k] > returnArray[k + 1])
    {

    temp = returnArray[k + 1];

    returnArray[k + 1] = returnArray[k];

    returnArray[k] = temp;
    numberOfSwaps=numberOfSwaps+1;
    }
    }
    alert ('swaps performed' + numberOfSwaps)

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center



Recent Articles