Providing a copy of assignment and what I have for my code so far, 1) Need some

Question

Providing a copy of assignment and what I have for my code so far, 1) Need some help fixing the error i'm receiving in QuickSort and 2)need some help fixing the way the time is being calculated that times the algorithms, please use c# if possible it's what I used .

I believe i'm almost done with this assignment just need some tweaking and any sort of help would be a great deal of help.

1) getting a crash on QuickSort - system.stackOverflow exception , Need help fixing this don't know what is causing the crash.

2) Help fix the negative values for the time average , not sure if my time function is wrong but I what i'm trying to do is time the sort algorithms . heres where I do the timing

t1 = time();
MergeSort(b,0,b.Length-1);
t2 = time();

talg2[i, n] = t2 - t1;

Showing how i'm getting negative values for time avg in MergeSort

COPY OF ASSIGNMENT

COPY OF MY CODE

namespace WindowsFormsApplication2
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
double time()
{
double DateTimestart =0;
DateTimestart = DateTime.Now.Millisecond;

return DateTimestart;
}

void InsertionSort(int[] a)
{
int length = a.Length;

for (int i = 1; i < length; i++)
{
int j = i;

while ((j > 0) && (a[j] < a[j - 1]))
{
int k = j - 1;
int temp = a[k];
a[k] = a[j];
a[j] = temp;

j--;
}
}
  
}
void MergeSort(int[] a, int p, int r)
{
if (p < r)
{
int q = (p + r) / 2;
//Sort left (will call Merge to produce a fully sorted left array)
MergeSort(a, p, q);
//Sort right (will call Merge to produce a fully sorted right array)
MergeSort(a, q + 1, r);
//Merge the sorted left & right to finish off.
Merge(a, p, q, r);
}
}
void Merge(int[] a, int p, int q, int r)
{
int lengthLeft = q - p + 1;
int lengthRight = r - q;
int[] leftArray = new int[lengthLeft + 1];
int[] rightArray = new int[lengthRight + 1];
for (int i = 0; i < lengthLeft; i++)
{
leftArray[i] = a[p + i];
}
for (int j = 0; j < lengthRight; j++)
{
rightArray[j] = a[q + j + 1];
}
leftArray[lengthLeft] = Int32.MaxValue;
rightArray[lengthRight] = Int32.MaxValue;
int iIndex = 0;
int jIndex = 0;
for (int k = p; k <= r; k++)
{
if (leftArray[iIndex] <= rightArray[jIndex])
{
a[k] = leftArray[iIndex];
iIndex++;
}
else
{
a[k] = rightArray[jIndex];
jIndex++;
}
}
}
void QuickSort(int[] a, int p, int r)
{
if (p < r)
{
int q = Partition(a, p, r);
QuickSort(a, p, q - 1);
QuickSort(a, q + 1, r);
}
}

int Partition(int[] a, int p, int r)
{
int pivot = a[r];
int temp;

int i = p;
for (int j = p; j < r; j++)
{
if (a[j] <= pivot)
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
i++;
}
}

a[r] = a[i];
a[i] = pivot;

return i;
}

private void button1_Click(object sender, EventArgs e)
{
int ns = 1000, nf = 20000, counter = 1000, m = 10;
Random random = new Random();
int randomNumber = random.Next(0, 32767);
int[,] a = new int[m, nf];

int[] b = new int[nf];
double[] IS_tavg = new double[nf];
double[,] talg1 = new double[m, nf];
double IS_taccum = 0;
double t1, t2;
//Generates array
for (int i = 0;i<m;i++)
{
for (int j = 0; j < nf; j++)
{
a[i, j] = random.Next(0, 32767);
// listBox1.Items.Add("A["+i + "]"+"B["+j + "] "+ a[i, j]);
}

}
  
  
  
  
//INSERT SORT
for (int n = 0; n < nf; n += counter) // goes until 20k and increments by 1k
{
  
for (int i = 0; i < m; i = i + 1)
{
  
b[n] = a[i, n];
t1 = time();
InsertionSort(b);
t2 = time();

talg1[i, n] = t2 - t1;

IS_taccum = talg1[i, n] + IS_taccum;
}
  
IS_tavg[n] = IS_taccum / m;
listBox1.Items.Add("[" + n + "] " + "INSERT TIME AVERAGE = " + IS_tavg[n]);
}

listBox1.Items.Add("------------------------------------------------------");
double[] MS_tavg = new double[nf];
double[,] talg2 = new double[m, nf];
double MS_taccum = 0;
  
//MERGE SORT
for (int n = 0; n < nf; n += counter) // goes until 20k and increments by 1k
{

for (int i = 0; i < m; i = i + 1)
{

b[n] = a[i, n];
t1 = time();
  
MergeSort(b,0,b.Length-1);
t2 = time();

talg2[i, n] = t2 - t1;

MS_taccum = talg2[i, n] + MS_taccum;
}

MS_tavg[n] = MS_taccum / m;
listBox1.Items.Add("["+ n+"] "+"MERGE TIME AVERAGE = " + MS_tavg[n]);
}
listBox1.Items.Add("------------------------------------------------------");
double[] QS_tavg = new double[nf];
double[,] talg3 = new double[m, nf];
double QS_taccum = 0;

//QUICK SORT
for (int n = 0; n < nf; n += counter) // goes until 20k and increments by 1k
{

for (int i = 0; i < m; i = i + 1)
{

b[n] = a[i, n];
t1 = time();
// might need to tweak it
QuickSort(b, 0, b.Length - 1);
t2 = time();

talg3[i, n] = t2 - t1;

QS_taccum = talg3[i, n] + QS_taccum;
}

QS_tavg[n] = QS_taccum / m;
listBox1.Items.Add("["+ n+"] "+"QUICK TIME AVERAGE = " + QS_tavg[n]);
}

  
  

  
}

Explanation / Answer

1.

On a sorted collection, the pivot chosen as the leftmost element will separate a sublist into an empty list and everything else, and then recurse into a sublist that is just one element less than the original (the pivot). Thus, your stack depth needs to be at least the same as the number of elements you're sorting. So if you have a largish collection, a StackOverflowException is not unexpected.

The only fix, really, is not using the naive quicksort.

Try changing your code as below:

2.

Couls you try changing the code and use mergesort as per the below shown program:

public IList MergeSort(IList list)
{
if (list.Count <= 1)
return list;
  
int mid = list.Count / 2;
  
IList left = new ArrayList();
IList right = new ArrayList();
  
for (int i = 0; i < mid; i++)
left.Add(list[i]);
  
for (int i = mid; i < list.Count; i++)
right.Add(list[i]);
  
return Merge(MergeSort(left), MergeSort(right));
}
  
public IList Merge(IList left, IList right)   
{
IList rv = new ArrayList();
  
while (left.Count > 0 && right.Count > 0)
if (((IComparable)left[0]).CompareTo(right[0]) > 0)
{
rv.Add(right[0]);
right.RemoveAt(0);
}
else
{
rv.Add(left[0]);
left.RemoveAt(0);
}
  
for (int i = 0; i < left.Count; i++)
rv.Add(left[i]);
  
for (int i = 0; i < right.Count; i++)
rv.Add(right[i]);
  
return rv;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.