To do: October 23
There are 35 people in this class.
a) If every person elbow bumped with every other person in this class, how many elbow bumps will have taken place?
To do: October 23
There are 35 people in this class.
a) If every person elbow bumped with every other person in this class, how many elbow bumps will have taken place?
b) What about if there are n people? How many elbow bumps?
Quadratic sorting algorithms:
Selection sort
Insertion sort
public void selectSort( int[] nums )
{
for(int i=0; i< nums.length-1; i++)
{
int min = i;
for(int j = i+1; j< nums.length; j++)
{
if( nums[j] < nums[min] )
min = j;
}
if(min != i)
{
int temp = nums[min];
nums[min] = nums[i];
nums[i] = temp;
}
}
}
public void sort2 int[] arr)
{
for (int i=1; i< arr.length; i++)
{
int key = arr[i];
int j=i;
while(j>0 && key < arr[j-1])
{
arr[j] = arr[j-1];
j--;
}
arr[j]=key;
}
}
Selection sort
public void selectSort( int[] nums )
{
for(int i=0; i< nums.length-1; i++)
{
int min = i;
for(int j = i+1; j< nums.length; j++)
{
if( nums[j] < nums[min] )
min = j;
}
if(min != i)
{
int temp = nums[min];
nums[min] = nums[i];
nums[i] = temp;
}
}
}
Write the first 5 passes in the sorting algorithm:
[10, 2, 7, -5, 9, 12, 0]
Selection sort
public void selectSort( int[] nums )
{
for(int i=0; i< nums.length-1; i++)
{
int min = i;
for(int j = i+1; j< nums.length; j++)
{
if( nums[j] < nums[min] )
min = j;
}
if(min != i)
{
int temp = nums[min];
nums[min] = nums[i];
nums[i] = temp;
}
}
}
Write the first 4 passes in the selection sorting algorithm:
[10, 2, 7, -5, 9, 12, 0]
1 -> [-5, 2, 7, 10, 9, 12, 0]
2 -> [-5, 0, 7, 10, 9, 12, 2]
3 -> [-5, 0, 2, 10, 9, 12, 7]
4 -> [-5, 0, 2, 7, 9, 12, 10]
Insertion sort
public void sort2 int[] arr)
{
for (int i=1; i< arr.length; i++)
{
int key = arr[i];
int j=i;
while(j>0 && key < arr[j-1])
{
arr[j] = arr[j-1];
j--;
}
arr[j]=key;
}
}
Write the first 4 passes in the insertion sorting algorithm:
[10, 2, 7, -5, 9, 12, 0]
Insertion sort
public void sort2 int[] arr)
{
for (int i=1; i< arr.length; i++)
{
int key = arr[i];
int j=i;
while(j>0 && key < arr[j-1])
{
arr[j] = arr[j-1];
j--;
}
arr[j]=key;
}
}
Write the first 4 passes in the insertion sorting algorithm:
[10, 2, 7, -5, 9, 12, 0]
1 -> [2, 10, 7, -5, 9, 12, 0]
2 -> [2, 7, 10, -5, 9, 12, 0]
3 -> [-5, 2, 7, 10, 9, 12, 0]
4 -> [-5, 2, 7, 9, 10, 12, 0]
Quadratic sorting algorithms:
Which sorting algorithm is modelled by the elbow bump problem - selection or insertion sort? Explain why.
Evaluate Guess My Number programs using rubric
Homework