/*****************************************************************\
BUBBLE SORT
This program makes a list of numbers and stores them in an array.
Then it scrambles up the numbers randomly.  Then it sorts them.
Finally it checks that all numbers are back in the right place.
\*****************************************************************/

void setup()
{
   makeNumbers();
   bubbleSort();
   checkSorted();
}

int[] nums = new int[10000000];
int howMany = 0;

void makeNumbers()
{
   howMany = inputInt("How many numbers do you want?");
   for(int c = 0; c < howMany; c = c+1)
   {
      nums[c] = c;
   }
   for(int c = 0; c < howMany; c = c+1)    // scramble up nums
   {
      int a = (int)(Math.random()*howMany);
      int b = (int)(Math.random()*howMany);
      int temp = nums[a];
      nums[a] = nums[b];
      nums[b] = temp;
   }
}

void bubbleSort()
{
  for(int pass = 0; pass < howMany; pass = pass+1)
  {  for(int c = 0; c < howMany - 1; c = c+1)
     { 
        if(nums[c] > nums[c+1])
        {  int temp = nums[c];
           nums[c] = nums[c+1];
           nums[c+1] = temp;
        }
     }
  }
}

void checkSorted()
{
  for(int c = 0; c < howMany; c = c+1)
  {
    if(nums[c] != c)
    { output("Failed at position " + c + " = " + nums[c]);
      return;
    }
  }
  output("Success!");
}

public void output(String message)
{  javax.swing.JOptionPane.showMessageDialog(this,message);  }
 
public String input(String prompt)
{  return javax.swing.JOptionPane.showInputDialog(this,prompt);  }
     
public int inputInt(String prompt)
{  int result=0;
   try{result=Integer.valueOf(
   input(prompt).trim()).intValue();}
   catch (Exception e){result = 0;}
   return result;
}

/***************************************************************\
(1) Run the program and try it with very sizes of lists.

(2) Explain why the bubbleSort() method requires nested loops,
    but the checkSorted() method only has a single loop.

(3) Make a list of the amount of time the program runs
    for various sizes of lists:
   
    How Many    How Long (seconds)
    --------    ------------------
        1000
        4000
       16000
       64000
      256000
     
(4) Explain why the HowMany list is going up in x4 steps,
    but the HowLong list is increasing in much larger steps.

(5) Estimate how long it would take to sort a list of 40000
    numbers, then run the program and check your estimate.
   
(6) Estimate how long it would take to sort a million numbers.   

(7) Figure out an improvement for the bubbleSort method
    that will make it run significantly faster.  Then try it
    and explain how much faster it is.

\***************************************************************/