Selection Sort - Show passes with no of camparison and swap
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
Selection sort Algorithm
1) Create array a[0 n-l] of n elements.
2) initialize i to 0
3) Set element at i as min and position to i
4) initialize j to i+1
5) if element at j is more than array[position] then
move value of j to position
6) increment j by 1
7) if j<n then goto step 4
8) Swap the element at i with element at position .
9) increment i by 1
10) if i<n-1 then goto step 3
11) Return the sorted array.
#include<stdio.h> int array[100], n, i,j,k,temp,count=0, position, swap=0; void selectionsort() { for ( i = 0 ; i < ( n - 1 ) ; i++ ) { position = i; for ( j = i + 1 ; j < n ; j++ ) { if ( array[position] > array[j] ) { position = j; count++; } else count++; } if ( position != i ) { temp = array[i]; array[i] = array[position]; array[position] = temp; swap++; } count++; printf("\npass %d:\t",i+1); for ( k = 0 ; k < n ; k++ ) printf("%d\t", array[i]); } } int main() { printf("Enter number of elements:"); scanf("%d", &n); for ( i = 0 ; i < n ; i++ ) { printf("Enter number :"); scanf("%d", &array[i]); } selectionsort(); printf("\n\nSorted list in ascending order:\n"); for ( i = 0 ; i < n ; i++ ) printf("%d\n", array[i]); printf("comparison count: %d\n", count); printf("swap count: %d\n", swap); return 0; }output:-
Enter number of elements:5 Enter number :29 Enter number :21 Enter number :64 Enter number :20 Enter number :56 pass 1: 20 20 20 20 20 pass 2: 21 21 21 21 21 pass 3: 29 29 29 29 29 pass 4: 56 56 56 56 56 Sorted list in ascending order: 20 21 29 56 64 comparison count: 14 swap count: 3 --------------------------------
time and space complexity:
Worst case performance: О(n^2)
Best case performance: О(n^2)
Average case performance: О(n^2)
Worst case space complexity: О(n) total, O(1) auxiliary
Analysis
Pass 1 :- n-1 comparisons
Pass 2 :- n-2 comparisons
...
Pass i :- n-i comparisons
So the total will be the summation of n-i from 1=1 to n-1. We get 1/2 [ n (n-1) ]
which finally leads the worst case complexity of 0(n^2).
Even exchange mechanism can not be devised for this algorithm. So irrespective of pattern of the set of input elements, the efficiency will always be 0(n^2) for best and average case also.
0 comments: