Below is C code, and Python code, for the Selectionsort algorithm. The input is an array A of n decimal numbers. Line 10 sorts the first n − 1 numbers in A recursively. C Code: 1: void Selectionsort( double A[], int n ) { 2: // sort A[0],A[1],...,A[n-1] into ascending order 3: int i,m; double t; 4: if( n<=1 ) return; // A is already sorted 5: m = 0; 6: for( i=1; iA[m] ) m = i; 8: // interchange A[i] and A[m] 9: t = A[i]; A[i] = A[m]; A[m] = t; 10: Selectionsort(A,n-1); 11: return; 12: } Python Code: 1: def Selectionsort(A,n): 2: # sort A[0], A[1], ..., A[n-1] into ascending order 3: if n<=1: 4: return # A is already sorted 5: m=0 6: for i in range(1,n): 7: if A[i]>A[m]: m=i 8: # interchange A[i] and A[m] 9: A[i], A[m] = A[m], A[i] 10: Selectionsort(A,n-1) Let cn be the number of comparisons between elements of A made in line 7. Give a recurrence equation and an initial value for cn and solve it. Does Selectionsort do fewer or more comparisons than Bubblesort? Note: you do not need to know how an algorithm works in order to count the number of times it executes a particular operation
Below is C code, and Python code, for the Selectionsort
C Code:
1: void Selectionsort( double A[], int n ) {
2: // sort A[0],A[1],...,A[n-1] into ascending order
3: int i,m; double t;
4: if( n<=1 ) return; // A is already sorted
5: m = 0;
6: for( i=1; i<n; i++ )
7: if( A[i]>A[m] ) m = i;
8: // interchange A[i] and A[m]
9: t = A[i]; A[i] = A[m]; A[m] = t;
10: Selectionsort(A,n-1);
11: return;
12: }
Python Code:
1: def Selectionsort(A,n):
2: # sort A[0], A[1], ..., A[n-1] into ascending order
3: if n<=1:
4: return # A is already sorted
5: m=0
6: for i in range(1,n):
7: if A[i]>A[m]: m=i
8: # interchange A[i] and A[m]
9: A[i], A[m] = A[m], A[i]
10: Selectionsort(A,n-1)
Let cn be the number of comparisons between elements of A made in line 7. Give a recurrence equation and an initial value for cn and solve it. Does Selectionsort do fewer or more comparisons than Bubblesort?
Note: you do not need to know how an algorithm works in order to count the number of times it executes a particular operation
Step by step
Solved in 2 steps
