Dark Mode

Rucha Shelke
asked
in Algorithms
Sep 17, 2014

19,765 views
32 votes

Best answer

Correct Option: **C -** Selection sort.

Because in selection the maximum swaps which can take place are $O(n)$

Because we pick up an element an find the minimum (in case of forward sorting) from the next index till the end of array and than perform the swap

Hence, $O(n)$ whereas in all other algos the swaps are greater ( considering Worst-Case scenario )

partition (arr[], low, high) { // pivot (Element to be placed at right position) pivot = arr[high]; i = (low - 1) // Index of smaller elementfor (j = low; j <= high- 1; j++)// no. of iterations=high-1-low+1{ // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // increment index of smaller elementswap arr[i] and arr[j]} }swap arr[i + 1] and arr[high]) // +1 swapreturn (i + 1) }

To understand my doubt please refer to the code above.

In the 1st level high=n and low=1. For the worst case of swapping, for each iteration there should be swapping. Hence total no. of swappings would be high-1-low+1=n-1-1+0=n-2 and outside the loop there is another swapping. Total swapping would be = n-1 in the 1st level. No. of swaps=O(n).

At 2nd level, if the pivot divides the array into equal halves then no. of swapping in this way is (low=1,high=(n/2)-1) so total swaps= (n/2)-1-1+1+1=n/2 and as there is another array set where low=n/2+1 and high=n so swaps=n/2 and hence total swaps=n.

If pivot element is placed at the end (for sorted array) then, low=1, high=n-1 so swaps= high-1-low+1+1=(n-1)-1-1+1+1=n-1.

We can assume that at each level the no. of swaps is O(n).

No. of levels= logn.

Total no. of swaps = nlogn.

How will it be n^2 @Bikram Sir ?

0

9 votes

Let's try to analyse the number of swaps in each of the given sorting algorithms. **Quick sort** – Worst Case input for maximum number of swaps will be already sorted array in decreasing order. Recurrence for Total number of swaps in this case : T(n) = T(n-1) + O(n) // O(n) swaps will occur in alternate calls to partition algorithm. = O(n2) **Insertion sort** - Worst Case input for maximum number of swaps will be already sorted array in ascending order.When a new element is inserted into an already sorted array of k size, it can lead to k swaps (in case it is the smallest of all) in worst case. For n-1 iterations of insertion sort, total swaps will be O(n2). **Selection sort** – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its orrect position. For n-1 iterations of selection sort, it can have O(n) swaps. **Heap sort **– Total number of swaps in Heap sort can be O(nlogn) as after performing Build-heap which may require O(n) swaps, it performs n-1 extract-min operations resulting into O(nlogn) swaps.

1

Politically correct, it depends on which order sorting would be performed using Insertion Sort! Like sorting them in **NON DECREASING ORDER (I. E. INCREASING ORDER) **, then worst case will be array elements sorted in **NON INCREASING ORDER (I. E. DECREASING ORDER).**

**And, vice versa. **If one can't get what I meant above, read it thrice. Most probably one will easily get what I meant. Else, just reply back here.

0

4 votes

Number of swaps

Quick sort = $\Theta (nlogn)$

Insertion sort = $\Theta (n^{2})$

Selction sort = no swaps required since we are shifting elements in the array and not swapping

Heap sort = $\Theta (nlogn)$

Option C

Quick sort = $\Theta (nlogn)$

Insertion sort = $\Theta (n^{2})$

Selction sort = no swaps required since we are shifting elements in the array and not swapping

Heap sort = $\Theta (nlogn)$

Option C

@srestha mam ,

the first line that said by @reena_kandari has no problem at all , In worst case, if we got bad partitioning the number of swaps would be O(N^2) in QSort. Let say input (1,2,3,4,5) first pivot should be 5, next one 4, next one 3 and so on......hence total 5+4+3+2+1=15 => 5(5+1)/2 number of comparisons made, more precisely we can say N(N+1)/ 2 i.e. O(N^2).

but

in worst case we have to do only n Logn swaps like 9,2,4,5,6,7,8

in this line I'm not getting what actually she is saying, if she talks about Qsort then in** avg case** Qsort takes NlogN swaps not in worst case. In worst case it should be O(N^2). So this would be an avg not worst. But if she talked about for general sorting, then it should be completely wrong.

Because

Insertion sort => in best case (already sorted) input takes like 1,2,3,4,5 there is no swaps happen it would be O(1) since data is already sorted. But in worst case like 5,4,3,2,1 it takes 1+2+3+4 precisely (N-1)N / 2 i.e again O(N^2).

Heap Sort => O(NlogN) all cases.

but in Selection Sort => we either swap smallest element to fist element , then 2nd smallest to 2nd element of array and so on...or largest element to last one, 2nd largest to N-1th element and so on.

hence it take O(N) number of swaps in all cases.

0

In quick sort no. of swappings :

case 1) [1,2,3,4,5] , last element as pivot

no. of swappings = 5+4+3+2+1 {when 5 is pivot then 1,2,3,4 are swapped with itself, similarly for others}

= (n-1)+(n-2)+.......+2+1

= (n(n-1))/2

= O(n^2)

case 2)[5,4,3,2,1] , last element as pivot

no. of swappings = 1 + 1 + 1 + 1 + 1

= (n)

=O(n)

eg: [5,4,3,2,1] {1 is pivot, 1 and 5 will be swapped}

[1] [4,3,2,5] {5 is pivot, 5 will be swapped with itself}

[1] [4,3,2] [5] {2 is pivot, 4 and 2 will be swapped}

[1] [2][3,4] [5] {4 is pivot, 4 will be swapped with itself}

[1] [2] [3] [4] [5] {3 is pivot, 3 will be swapped with itself}

case 3) [2,2,2,2,2], last element as pivot

no. of swappings = 1 + 1 + 1+ 1 +1

= n

= O(n)

Am I correct ???? and in best case is no of swappings = O(log n) ???

case 1) [1,2,3,4,5] , last element as pivot

no. of swappings = 5+4+3+2+1 {when 5 is pivot then 1,2,3,4 are swapped with itself, similarly for others}

= (n-1)+(n-2)+.......+2+1

= (n(n-1))/2

= O(n^2)

case 2)[5,4,3,2,1] , last element as pivot

no. of swappings = 1 + 1 + 1 + 1 + 1

= (n)

=O(n)

eg: [5,4,3,2,1] {1 is pivot, 1 and 5 will be swapped}

[1] [4,3,2,5] {5 is pivot, 5 will be swapped with itself}

[1] [4,3,2] [5] {2 is pivot, 4 and 2 will be swapped}

[1] [2][3,4] [5] {4 is pivot, 4 will be swapped with itself}

[1] [2] [3] [4] [5] {3 is pivot, 3 will be swapped with itself}

case 3) [2,2,2,2,2], last element as pivot

no. of swappings = 1 + 1 + 1+ 1 +1

= n

= O(n)

Am I correct ???? and in best case is no of swappings = O(log n) ???

0