Member Avatar for tubby123

What is the number of swaps required to sort n elements using selection sort, in the worst case?
The site i am referring says theta(n).
Shouldnt it be theta(n2), cuz worst case it requires n swaps for each of the n elements.

  • 2 Contributors
  • 5 Replies
  • 101 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by Narue

Dani AI

Generated

Short version (building on ): selection sort performs at most one swap per outer pass, so swaps <= n-1 (Theta(n)). The inner loop does a fixed number of comparisons that add up to n(n-1)/2, so comparison work is Theta(n^2) and the overall time is Theta(n^2).

A compact pseudocode snapshot to show where the single-swap-per-pass idea comes from:

for i = 0 to n-2
  min = i
  for j = i+1 to n-1
    if A[j] < A[min] then min = j
  if min != i then swap(A[i], A[min])

Counting notes:

  • Comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2 exactly.
  • Swaps: at most one per i, so at most n-1 total; best case 0, worst case n-1.
  • Expected swaps for a random permutation = sum_{m=2..n} (m-1)/m = n - H_n (about n - ln n), so still Theta(n).

Practical clarifications:

  • Analysts often count a logical swap as one operation; an implementation swap is usually three assignments, so if counting write operations, account for that (<= 3(n-1) writes from swaps).
  • Selection sort is in-place and simple, not stable by default, and not adaptive in comparisons (it always does the same comparisons), but it is adaptive in writes (fewer swaps when many elements already in place). That property makes it sometimes useful when writes are expensive (flash, EEPROM); for even fewer writes look at cycle sort (specialized).

Conclusion: answered correctly; ’s intuition that every inner comparison triggers a swap is what to avoid — selection sort selects first, then swaps at most once per pass.

Recommended Answers

All 5 Replies

Member Avatar for Narue

cuz worst case it requires n swaps for each of the n elements

How do you figure that?

Member Avatar for tubby123

How do you figure that?

Worst case, ya, it requires n swaps, if say the array is in the descending order ...

so is the correct answer theta(n) ???

Member Avatar for Narue

Worst case, ya, it requires n swaps

Not for each element (which is what you stated previously). Selection sort requires at most n-1 swaps total because a swap is only performed after selecting the item to move (or not move, depending on the intermediate relative order). Thus, the worst case for swaps is indeed theta(n).

Member Avatar for tubby123

ok cool, just to summarize,
number of swaps : n-1 or theta(n)
worst case running time : O(n2) ..

narue, correct ???

Member Avatar for Narue

Yup. O(n2) running time isn't wrong, but you can tighten it to theta(n2) if you want. Best, average, and worst cases for selection sort are (typically) all the same.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.