MHB Stable Algorithm: Insertion, Merge, Heap, Quicksort?

[mathmari]

Hey!

Which of the following sorting algorithms are (or can be implemented as) stable:
Insertion Sort, Merge Sort, Heap Sort, Quicksort ??

How can we determine it?? (Wondering)

 

[mathmari]

For a stable sorting algorithm it stands the following:

If we have for example the sequence 1212. After sorting the first 1 will still be before the second 1 and the 2 that is now at the second position wil still be before the 2 of the last position...

At Insertion Sort each element x will be compared with all the elements on its right side. These elements won't get before x, since all the elements at the left side of x are sorted and since it is still on the right side it is bigger or equal that x. So, Insertion Sort is stable. Is this correct?? (Wondering)

How could we formulate it formally?? (Wondering)

 

[I like Serena]

Hey!

Which of the following sorting algorithms are (or can be implemented as) stable:
Insertion Sort, Merge Sort, Heap Sort, Quicksort ??

How can we determine it?? (Wondering)

Take a look: Sorting_algorithm#Comparison_of_algorithms

It shows which of those algorithms is stable. (Wasntme)

For a stable sorting algorithm it stands the following:

If we have for example the sequence 1212. After sorting the first 1 will still be before the second 1 and the 2 that is now at the second position wil still be before the 2 of the last position...

At Insertion Sort each element x will be compared with all the elements on its right side. These elements won't get before x, since all the elements at the left side of x are sorted and since it is still on the right side it is bigger or equal that x. So, Insertion Sort is stable. Is this correct?? (Wondering)

Yes, Insertion Sort is stable. (Nod)

How could we formulate it formally?? (Wondering)

It think your formulation is good enough, unless you want to give a proof.

To prove an algorithm is not stable, it suffices to give a counter example.

To show an algorithm is stable, such as is the case for Insertion Sort, you'd need to go through each step of the algorithm and show that the original sort order is an invariant. (Sweating)

See e.g. Insertion Sort for a proof that the algorithm actually sorts. It could be extended by considering at every step if the original sort order is retained.

 

[mathmari]

To show an algorithm is stable, such as is the case for Insertion Sort, you'd need to go through each step of the algorithm and show that the original sort order is an invariant. (Sweating)

See e.g. Insertion Sort for a proof that the algorithm actually sorts. It could be extended by considering at every step if the original sort order is retained.

Is the invariant the following?? (Wondering)

At the beginning of each iteration of the for loop, if $A[a]=A, a<b \leq j-1$, then $A[a]$ appears before $A$.

Initialization:
We have to show that the invariant holds before the first iteration of the loop where $j=2$. In this case, the subarray $A[1 \dots j-1]$ consists of only the element $A[1]$, so there are no $a<b \leq j-1=1$. So, the invariant holds trivially.

Maintenance:
We have to check if the property maintains at each iteration. The body of the outer for loop shifts the elements $A[j-1], A[j-2], A[j-3], \dots$ one position to the right until the right position for $A[j]$ is found, at which the value of $A[j]$ will be inserted, but it doesn't change their order. SO, if the invariant holds before an iteration of the loop, it still holds before the next iteration.

Termination:
We have to check what happens when the loop stops. The outer for loop stops when $j=n+1$. Setting $j=n+1$ at the invariant loop, we have that for each $A[a]=A, a<b \leq n$, it implies that $A[a]$ appears before $A$ at the initial subarray. But the subarray $A[1 \dots n]$ is the whole array. So, Insertion Sort is stable.
Is this correct?? (Wondering) Could I improve something?? (Wondering)

 

[I like Serena]

Is the invariant the following?? (Wondering)

At the beginning of each iteration of the for loop, if $A[a]=A, a<b \leq j-1$, then $A[a]$ appears before $A$.

Initialization:
We have to show that the invariant holds before the first iteration of the loop where $j=2$. In this case, the subarray $A[1 \dots j-1]$ consists of only the element $A[1]$, so there are no $a<b \leq j-1=1$. So, the invariant holds trivially.

Maintenance:
We have to check if the property maintains at each iteration. The body of the outer for loop shifts the elements $A[j-1], A[j-2], A[j-3], \dots$ one position to the right until the right position for $A[j]$ is found, at which the value of $A[j]$ will be inserted, but it doesn't change their order. SO, if the invariant holds before an iteration of the loop, it still holds before the next iteration.

Termination:
We have to check what happens when the loop stops. The outer for loop stops when $j=n+1$. Setting $j=n+1$ at the invariant loop, we have that for each $A[a]=A, a<b \leq n$, it implies that $A[a]$ appears before $A$ at the initial subarray. But the subarray $A[1 \dots n]$ is the whole array. So, Insertion Sort is stable.
Is this correct?? (Wondering) Could I improve something?? (Wondering)

Looks good to me! (Whew)

The only possible improvement I see is to add the actual algorithm so that it is clear what you're talking about. (Nerd)

 

[mathmari]

I am thinking again about the invariant and I got stuck...

At the statement:

At the beginning of each iteration of the for loop, if $A[a]=A, a<b \leq j-1$, then $A[a]$ appears before $A$.

is it correct to suppose $a<b \leq j-1$ ?? (Wondering) Or should it be $a<b \leq j$ ?? (Wondering)

 

[I like Serena]

I am thinking again about the invariant and I got stuck...

At the statement:

At the beginning of each iteration of the for loop, if $A[a]=A, a<b \leq j-1$, then $A[a]$ appears before $A$.

is it correct to suppose $a<b \leq j-1$ ?? (Wondering) Or should it be $a<b \leq j$ ?? (Wondering)

That depends on the actual algorithm that you're using.
Which algorithm is it? (Wondering)

 

[mathmari]

That depends on the actual algorithm that you're using.
Which algorithm is it? (Wondering)

It is the following:

INSERTION-SORT(A)
1  for j ← 2 to length[A]
2      do key ← A[j]
3      Insert A[j] into the sorted sequence A[1 . . . j−1]
4      i ← j − 1
5      while i > 0 and A[i] > key
6           do A[i + 1] ← A[i]
7           i ← i − 1
8      A[i + 1] ← key

 

[I like Serena]

I am thinking again about the invariant and I got stuck...

At the statement:

At the beginning of each iteration of the for loop, if $A[a]=A, a<b \leq j-1$, then $A[a]$ appears before $A$.

is it correct to suppose $a<b \leq j-1$ ?? (Wondering) Or should it be $a<b \leq j$ ?? (Wondering)

I believe it does not matter. Both are fine. (Smile)

However, looking at your invariant, I do see another problem. It should be 'originally appeared' instead of 'appears'. (Nerd)

 

[mathmari]

I believe it does not matter. Both are fine. (Smile)

Ok... But how will the termination be when we take $a<b \leq j$?? (Wondering) In this case $j=n+1$, so $a<b \leq n+1$. $A[a]=A,a<b \leq n+1$, it implies that $A[a]$ appears before $A$ at the initial subarray.

Can we formulate it in that way?? (Wondering) Or is it a problem to have $a<b \leq n+1$ ?? (Wondering)

However, looking at your invariant, I do see another problem. It should be 'originally appeared' instead of 'appears'. (Nerd)

Yes, you're right! (Smile)

We have to check if the property maintains at each iteration. The body of the outer for loop shifts the elements $A[j−1],A[j−2],A[j−3],\dots$ one position to the right until the right position for $A[j]$ is found, at which the value of $A[j]$ will be inserted, but it doesn't change their order. o, if the invariant holds before an iteration of the loop, it still holds before the next iteration.

At the maintenance do I have to justify why their order doesn't change ?? (Wondering) Do I have to mention the condition $A>key$ ?? (Wondering)

 

[mathmari]

Could you give me some hints how the statement of the invariant for the Merge Sort will look like?? (Wondering)

 

[I like Serena]

Could you give me some hints how the statement of the invariant for the Merge Sort will look like?? (Wondering)

What's the algorithm? (Wondering)