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.


code in C:
#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: