Question

JAVA

Each of the following 6 questions refer to the following list of values in the order as shown.
555 288 633 666 444 422 399 477

21. Print the values in the order they would have after the first round of bubble sort’s bubbling
operation low to high.
22. Print the values in the order they would have after the first round of selection sort for sorting
low to high, assuming it selects the max.
23. Print the values in the order they would have after the first round of selection sort for sorting
low to high, assuming it selects the min.
24. Print the values in the order they would have after the first round of a binary radix sort for
sorting low to high.
25. Print the values in the order they would have after the first round of a decimal radix sort for
sorting low to high.
26. Print the values in the order they would have after the first round of quicksort’s 3-way
partition operation. Assume it chooses the last element in the array as the pivot.
27. Theoretically (if it could be done), what would be the best value to use as the pivot for a
quicksort round of partitioning?

Answer 1

21. After first round of bubbling, the array is as follows:

288 555 633 444 422 399 477 666

22. After first round of selection sort that selects the max element, the max element is moved to the end. The array is as follows:

555 288 633 444 422 399 477 666

23. After first round of selection sort that selects the min element, the min element is moved to start. The array is as follows:

288 555 633 666 444 422 399 477

24. The array is sorted based on the last digit in the binary notation of the elements. Thus even numbers (last binary digit 0) appear after odd numbers(last binary digit 1) after first pass of binary radix sort.

After the first round of binary radix sort, the array is as follows:

288 666 444 422 555 633 399 477

25.In decimal radix sort, in the first pass, array is sorted on the last decimal digit.

422 633 444 555 666 477 288 399

26. In quick sorts, 3 way partition, the last element is selected as pivot. All elements lesser than pivot occur at the beginning , then the elements equal to the pivot appear and finally the elements greater than the pivot appear. The array after first round of sorting is: (477 is the pivot)

288 444 422 399 477 555 633 666