[RESOLVED] bubble sort problems

This site is best viewed in a modern browser with JavaScript enabled.

john2java

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 = arrayToSort;
}

// 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;
}

john2java

Ps I'm sorry I tried to get the code to indent in here but was unable to do it.

JMRKER

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.

<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.

john2java

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.

JMRKER

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.

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:

  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!

john2java

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.

JMRKER

You're most welcome.
Happy to help.
Good Luck!

fenixcomp

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)