how to calculate number of camparision in selection sort?

Mehdinaqvi (43)
kindly tell me where and how to put comparision condition in order to caculate total number of comparision in selection sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
        static void selectsort(int[] dataset, int n)
        {
            int i, j;
            for (i = 0; i < n; i++)
            {
                int min = i;
                for (j = i + 1; j < n; j++)
                    if (dataset[j] < dataset[min])
                        min = j; //find min value
                //then swap it with the beginning item of the unsorted list
                int temp = dataset[i];
                dataset[i] = dataset[min];
                dataset[min] = temp;
            }

        }



    }
}
dhayden (599)
When we talk about comparisons in sorting algorithms, it's comparing one item that's being sorted to another. So in this case, it's line 8.
anup30 (259)
i am not clear about the question.

in this sorting style total number of comparison = factorial(n-1).

and maximum number of swap = n-1.

in order to find total swaping operation occured add,
int totalSwap = n-1; //line 3
if (min==i) totalSwap--; //line 10
Last edited on
anup30 (259)
Correction: total number of comparison in selection sort =
(n-1)+(n-2)+(n-3)+......+3+2+1 = n*(n-1)/2
Last edited on
Topic archived. No new replies allowed.

C++

Forum