Compare the performances of the following sorting algorithms. You can either wri

Question

Compare the performances of the following sorting algorithms. You can either write the algorithms on your own or modify algorithms obtained from elsewhere. Create a table with the rows being the different algorithms and the columns being the inputs.

Run each input 10 times and report the mean, and standard deviation for each run. You can also represent the results as a table. Write a short summary (about 1 paragraph) on your observations.

A. Quicksort

B. Quicksort until size of generated partitions is less than equal to 1000, 500, 100, 10 and then using insertion sort

C. Bucketsort

Explanation / Answer

Solution:

A.

Insertion sort is simple for small lists, it is generally faster than a comparably implemented quicksort . That is why a practical sort implementation will generally fall back on something like insertion sort for the "base case", instead of recursing all the way down to single elements as in case of quick sort . It is much less efficient on large lists than quicksort.

B.

QUICK SORT (Size of generated partitions is less than equal to 1000, 500,100,10)

The basic idea is that two pivots are selected and three partitions are created. Here is the main part of modification: there are to approaches depending on whether the pivots are the same or not. If the pivots are different and we order them so that compare(pivot1, pivot2) is true (we say, pivot1 is "less" than pivot2), then the following partitions are created:

the elements that are "less" than or equal to pivot1 (!compare(pivot1,a[i]) is true);

the elements that are between pivot1 and pivot2 (compare(pivot1,a[i]) && compare(a[i],pivot2) is true);

the elements that are "greater" than or equal to pivot2 (!compare(a[i],pivot2) is true).

If the selected pivots are the same, the partitions are slightly different:

the elements that are "less" than pivot1 (compare(a[i],pivot1) is true);

the elements that are equal to pivot1 (and obviously equal to pivot2) (!compare(pivot1,a[i]) && !compare(a[i],pivot1) is true);

the elements that are "greater" than pivot1 (compare(pivot1,a[i]) is true).

If the pivots are equal, obviously the second partition does not have to be sorted.

C.

Bucket sort is mainly useful when input is uniformly distributed over a range. Bucket sort is a comparison sort algorithm that operates on elements by dividing them into different buckets and then sorting these buckets individually. Each bucket is sorted individually using a separate sorting algorithm or by applying the bucket sort algorithm recursively.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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