Question

Homework help please :
The question is in comments.

Answer 1

The following version of Selection Sort is supposed to sort an array in ascending order. For better performance it tries to tackle the array from both ends simultneously:

public void sort (int a[ ])

{

int left = 0, right = a.length - 1;

int k;

while (left < right)

{

for (k = left + 1; k < right; k++ )

{ if (a[k] < a[left])

swap(a,k,left);

else if (a[k] > a[right])

swap(a,k,right);

}

left++;

right--;

}

}

swap(a,i,j) correctly swaps a[i] and a[j]. This code has a bug, though. Which of the following changes would assure that the method sorts all arrays correctly?

I. Remove else in

else if (a[k] > a[right]) . . .

II. Replace

for (k = left + 1; k < right; k++ )

with

for (k = left; k <= right; k++ )

III. Add

if (a[left] > a[right])

swap(a, left, right);

at the beginning of the while loop (before the for loop).
I only
II only
III only
I or II
II or III

2. Suppose Mergesort is implemented as follows:

public void sort(int [ ] a, int n1, int n2)
{ if (n1 == n2)
return;
else if (n2 == n1 + 1)
{ if (a[n2] < a[n1])
swap(a,n1,n2); // swaps a[n1] and a [n2]
return;
}
int m = (n1 + n2) / 2;
sort(a,n1,m);
sort (a, m+1, n2);
if (a[m] > a [m+1])
merge (a,n1,m,n2); // merges a[n1] . . . a[m] and a[m+1] . . . a[n2]
}

How many times will the method merge be called if an array a contains the values

2 1 4 3 6 5 8 7

7
4
3
1
0

Answer 2

what do you think? in the merge sort, don't i have to separate the array?

Answer 3

dividing
[2143] [6587]
[21] [43] [65] [87]
left side: 1234
right side: 5678

Answer 4

its either 3 or 7

Answer 5

Can you provide a more specific question?

Answer 6

I can't make them anymore specific. I asked my Computer Science teacher, and she said that the questions are no more specific than what I have.

Answer 7

sorry, I keep losing connection to this site.

Answer 8

Sorry Elle, I'm too busy at the moment to get to the bottom of this sorting algorithm.

Answer 9

@wio

Answer 10

For merge sort, I think merge sort will be called `n log(n)` times regardless.

Answer 11

Really? well for my hw questions its asking how many times will the merge be called for the values 2, 1, 4, 3,6, 5, 8, 7
out of the answers, its either 3 or 7.

Answer 12

I would say it gets called 7 times.

Answer 13

can you show that through the divide, and how it would sort please?

Answer 14

1 [2143] -[6587]
2 [21]-[43] [65]-[87]
4 [2]-[1] [4]-[3] [6]-[5] [8]-[7]
1+2+4=7

Answer 15

```
[2143] [6587]
[21] [43] [65] [87]
[2] [1] [4] [3] [6] [5] [8] [7]
Merge 4:
[12] [34] [56] [78]
Merge 2:
[1234] [5678]
Merge 1:
[12345678]
```

Answer 16

Thank you :)
How would you do the first question? I thought that the answer was II or III, but my teacher told me its wrong.

Answer 17

I'm having trouble with question 1.

Answer 18

```
public void sort (int a[ ])
{
int left = 0, right = a.length - 1;
int k;
while (left < right)
{
for (k = left + 1; k < right; k++ )
{ if (a[k] < a[left])
swap(a,k,left);
else if (a[k] > a[right])
swap(a,k,right);
}
left++;
right--;
}
}
```

I'm thinking III

Answer 19

I'm looking in a textbook

Answer 20

I guess II could fix it as well

Answer 21

I'll check for III in another textbook.

Answer 22

Which one do you think is more correct?

Answer 23

I think III is more correct

Answer 24

I'll try to run it. :)

Answer 25

It looks like III fits better. :)

Answer 26

Thank you :)
I'll be here on OS if i need any help :)