Suppose a sorting algorithm in each stage swaps only adjacent elements. That is,

Question

Suppose a sorting algorithm in each stage swaps only adjacent elements. That is, (like for example Bubble-Sort and Simple Insertion-Sort) in each stage it swaps A[i] and A[i + 1] for some i. Let di denote the the distance of A[i]. Show that A[i] must go through di comparisons in any algorithm of this type.

In the algorithm, always explain how and why they work. ALWAYS, analyze the complexity of an algorithm. In all algorithms, always try to get the fastest possible.In all data structures, try to minimize as much as possible the running time of any operation.

Explanation / Answer

Consider the bubble sort example for swapping adjacent elements in the given list. Consider the below exmaple for bubble sort of three passes.

Let us take the array of numbers A[] = {5 1 4 2 8}, and sort the array from lowest number to greatest number using bubble sort.
In each step, elements written in bold are being compared. Three passes will be required.

First Pass
( 5 1 4 2 8 ) o ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) o ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) o ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) o ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass
( 1 4 2 5 8 ) o ( 1 4 2 5 8 )
( 1 4 2 5 8 ) o ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) o ( 1 2 4 5 8 )
( 1 2 4 5 8 ) o ( 1 2 4 5 8 )
Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass
( 1 2 4 5 8 ) o ( 1 2 4 5 8 )
( 1 2 4 5 8 ) o ( 1 2 4 5 8 )
( 1 2 4 5 8 ) o ( 1 2 4 5 8 )
( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

So In the above exmaple in each pass the elements are compared like A[i] with A[i+1} ..so it will swap the elements based on adjacent elements every time.
when N means Number of elements. When N is small it is best algorithm but incase of N is large number it will take the time complexity of O(n^2).

Insertion sort technique is also work based on the swapping adjacent elements in the given list. So the Average time complexity is O(n logn n).
It will optimise the time complexity

here exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other (n2) sorting algorithms, such as insertion sort,

tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large

The only significant advantage that bubble sort has over most other implementations,

but not insertion sort, is that the ability to detect that the list is sorted is efficiently built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions).

Bubble sort should be avoided in the case of large collections. It will not be efficient in the case of a reverse-ordered collection.

the optimised psudo code for bubble sort is

procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
if A[i-1] > A[i] then
swap(A[i-1], A[i])
swapped = true
end if
end for
n = n - 1
until not swapped
end procedure

The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time:

More generally, it can happen that more than one element is placed in their final position on a single pass. In particular, after every pass, all elements after the last swap are sorted, and do not need to be checked again. This allows us to skip over a lot of the elements, resulting in about a worst case 50% improvement in comparison count (though no improvement in swap counts), and adds very little complexity because the new code subsumes the "swapped" variable

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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