# questions on sorting algorithm

RabiDas Sharma

Ranch Hand

Posts: 69

posted 3 years ago

In case of selection sort the number comparisions

made is n(n-1)/2 so complexity of it is O(n2)

I think In case of

n(n-1)/2 so generalised complexity is O(n2)

but my study material says

if no exchnage is made i.e,

in case of completely sorted array there is no exchange so

complexity is: O(n)

so my

2>

please rectify mistakes if any

thnks in advance

with regards

made is n(n-1)/2 so complexity of it is O(n2)

**Question**__1>In case of selection sort As n(n-1)/2 comparisions made__

and n(n-1)/2 is polynomial of degree 2

so complexity is: O(n2)and n(n-1)/2 is polynomial of degree 2

so complexity is: O(n2)

I think In case of

**exchange sort**also number of comparisions made isn(n-1)/2 so generalised complexity is O(n2)

but my study material says

If the array is already sorted, zero exchanges are made.

In the worst case there are many exchanges required, i.e.(n-1)/2 exchanges are required.

In the average case n(n-1)/4 exchanges are made.

Therefore, general complexity is O (n2).

Best case complexity is O(n)

if no exchnage is made i.e,

in case of completely sorted array there is no exchange so

complexity is: O(n)

so my

**question**is :2>

__complexity depends on number of comprisions or exchanges made.??__

I believe former is correct.

I believe former is correct.

please rectify mistakes if any

thnks in advance

with regards

Campbell Ritchie

Marshal

Posts: 52581

119

posted 3 years ago

Please tell us where that quote comes from.

I always thought you went for the worst‑case complexity in which case both appear to run in O(

I always thought you went for the worst‑case complexity in which case both appear to run in O(

*n²*) time.
Ulf Dittmer

Rancher

Posts: 42970

73

posted 3 years ago

Generally one talks about worst-case complexity - that's probably what it would be used for if nothing else is specifically mentioned. But it can be worthwhile examining average-case complexity (or even best-case complexity) if you know that your data will generally adhere to the average case rather than the worst case.

No, it wouldn't be correct to put it in absolute terms like that - it's

But what you're generally interested in is the time it takes to execute a program - and a swap of two numbers takes a lot more time than a comparison of two numbers, so for sorting algorithms one generally considers just the swaps.

Just hypothetically, if a sorting algorithm had O(n^2) swaps and O(n^3) comparisons, you would likely have to have very large numbers of N before the time taken for comparisons dominates the time taken for swaps.

complexity depends on number of comprisions or exchanges made? I believe former is correct.

No, it wouldn't be correct to put it in absolute terms like that - it's

*operations*in general. If you wanted to cover all the bases, you'd have to use two O(n) measures, one for comparisons and one for swaps (and even more if you'd be doing other operations that depend on the size of the data).But what you're generally interested in is the time it takes to execute a program - and a swap of two numbers takes a lot more time than a comparison of two numbers, so for sorting algorithms one generally considers just the swaps.

Just hypothetically, if a sorting algorithm had O(n^2) swaps and O(n^3) comparisons, you would likely have to have very large numbers of N before the time taken for comparisons dominates the time taken for swaps.