l

 

For an array of size n, we need n-1 passes and a total of (n²-2)/2 comparisons. We swap positions whenever the elements are out of order.

To reduce the number of comparisons we can use a Two-way bubble sort. In one pass we bubble the larger numbers up, and in the subsequent pass, we bubble the smaller numbers down. Even with Two-way bubble sort, we still have the problem of not caring whether the array is already sorted. So we need a flag to tell us if any swaps were there.

Also by using the Quick sort method we reduce the number of compares and swaps. Quick sort uses a divide-and-conquer strategy. A recursive approach in which the original problem is partitioned into simpler sub-problems, each of which can be considered independently.

 (1) The algorithm chooses some element to be the pivot.

 (2) Perform a sequence of exchanges so that all elements that are less than this pivot are to its left and all elements that are greater than the pivot are to its right.

The algorithm continues recursively with steps (1) and (2), until it is done.

 

 

 

 

 

Click to see graphical representation

1. Why is a flag needed in bubble sort?

    a) To sort the array

    b) To know when the array is in order

    c) To calculate the number of compares

 (Answer: c)

2. Explain the difference between Bubble sort and Two-Way bubble sort.

    (Answer:  In Bubble Sort on each pass through the list, exchange pairs of values that are out of sequence. Eventually, all pairs in in the correct order, and the algorithm stops. While in the Two-way bubble we bubble up in one pass, and we bubble down in the subsequent pass..