Question

In a Union Find algorithm, why does path compression make deunion, (undo union), hard?

How many comparisons are needed for Bubblesort and Cocktailsort?

Answer 1

A union-find algorithm performs two necessary operation which are:

Find: Find particular element in subset.This can be used for finding if two elements are in the same subset.

Union: combine two subsets into a single subset.

Suppose have set of different elements and all of them are in their own set so basically we have called MakeSet on each invididual elements. So, first we do union of set. And make representative to one of the set . but after making union set it really difficult to split into their previous subset. Hence deunion is difficult in union and find path compression algorithm.

No. of comparision needed in Bubble sort:-

If n is total no of elements then,

(n-1)+(n-2)+(n-3)+(n-4)….+2+1=n(n-1)/2

No. of comparision needed in Cocktail sort:-

If n is total no of elements then,

(n(n-1)/2)