Scenarios for selection sort, insertion sort, and quick sort

Question

If anyone can give some input on my logic, I would very much appreciate it.

Which method runs faster for an array with all keys identical, selection sort or insertion sort?

I think that this would be similar to when the array is already sorted, so that insertion sort will be linear, and the selection sort quadratic.

Which method runs faster for an array in reverse order, selection sort or insertion sort?

I think that they would run similarly, since the values at every position will have to be changed. The worst case scenario for insertion sort is reverse order, so that would mean it is quadratic, and then the selection sort would already be quadratic as well.

Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?

Since it is randomly sorted, I think that would mean that the insertion sort would have to perform many more times the number of operations that the number of values. If that's the case, then its not linear.So, it would likely be quadratic, or perhaps a little below quadratic.

What is the maximum number of times during the execution of Quick.sort() that the largest item can be exchanged, for an array of length N?

The maximum number cannot be passed over more times than there are spaces available, since it should always be approaching its right position. So, going from being the first to the last value spot, it would be exchanged N times.

About how many compares will quick.sort() make when sorting an array of N items that are all equal?

When drawing out the quick sort , a triangle can be drawn around the compared objects at every phase, that is N tall and N wide, the area of this would equal the number of compares performed, which would be (N^2)/2

Answer 1

Here are my comments on your comments:

Which method runs faster for an array with all keys identical, selection sort or insertion sort?

I think that this would be similar to when the array is already sorted, so that insertion sort will be linear, and the selection sort quadratic.

Yes, that's correct. Insertion sort will do O(1) work per element and visit O(n) elements for a total runtime of O(n). Selection sort always runs in time Θ(n²) regardless of the input structure, so its runtime will be quadratic.

Which method runs faster for an array in reverse order, selection sort or insertion sort?

I think that they would run similarly, since the values at every position will have to be changed. The worst case scenario for insertion sort is reverse order, so that would mean it is quadratic, and then the selection sort would already be quadratic as well.

You're right that both algorithms have quadratic runtime. The algorithms should actually have relatively comparable performance, since they'll make the same total number of comparisons.

Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?

Since it is randomly sorted, I think that would mean that the insertion sort would have to perform many more times the number of operations that the number of values. If that's the case, then its not linear.So, it would likely be quadratic, or perhaps a little below quadratic.

This should take quadratic time (time Θ(n²)). Take just the elements in the back third of the array. About a third of these elements will be 1's, and in order to insert them into the sorted sequence they'd need to be moved above 2/3's of the way down the array. Therefore, the work done would be at least (n / 3)(2n / 3) = 2n² / 9, which is quadratic.

What is the maximum number of times during the execution of Quick.sort() that the largest item can be exchanged, for an array of length N?

The maximum number cannot be passed over more times than there are spaces available, since it should always be approaching its right position. So, going from being the first to the last value spot, it would be exchanged N times.

There's an off-by-one error here. When the array has size 1, the largest element can't be moved any more, so the maximum number of moves would be N - 1.

About how many compares will quick.sort() make when sorting an array of N items that are all equal?

When drawing out the quick sort , a triangle can be drawn around the compared objects at every phase, that is N tall and N wide, the area of this would equal the number of compares performed, which would be (N^2)/2

This really depends on the implementation of Quick.sort(). Quicksort with ternary partitioning would only do O(n) total work because all values equal to the pivot are excluded in the recursive calls. If this isn't done, then your analysis would be correct.

Hope this helps!