top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

    Get Free Article Updates

Facebook Login
Site Registration
Print Preview

The Selection Sort

+1 vote
25 views

Selection Sort:-

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

This process continues and requires n−1 passes to sort n items, since the final item must be in place after the (n−1) st pass.

This algorithm is not suitable for large data sets as its average and worst case complexities are of Ο(n2), where n is the number of items.

Algorithm:-

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted.

Pictorial Representation:-

In the first pass, the smallest element found is 1, so it is placed at the first position, then leaving first element, smallest element is searched from the rest of the elements, 3 is the smallest, so it is then placed at the second position. Then we leave 1 and 3, from the rest of the elements, we search for the smallest and put it at third position and keep doing this, until array is sorted.

C program for selection sort:-

#include <stdio.h>
#include <stdbool.h>
#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count) {
   int i;
	
   for(i = 0;i <count-1;i++) {
      printf("=");
   }
	
   printf("=\n");
}

void display() {
   int i;
   printf("[");
	
   // navigate through all items 
   for(i = 0;i<MAX;i++) {
      printf("%d ", intArray[i]);
   }
	
   printf("]\n");
}

void selectionSort() {

   int indexMin,i,j;
	
   // loop through all numbers 
   for(i = 0; i < MAX-1; i++) { 
	
      // set current element as minimum 
      indexMin = i;
		
      // check the element to be minimum 
      for(j = i+1;j<MAX;j++) {
         if(intArray[j] < intArray[indexMin]) {
            indexMin = j;
         }
      }

      if(indexMin != i) {
         printf("Items swapped: [ %d, %d ]\n" , intArray[i], intArray[indexMin]); 
			
         // swap the numbers 
         int temp = intArray[indexMin];
         intArray[indexMin] = intArray[i];
         intArray[i] = temp;
      }          

      printf("Iteration %d#:",(i+1));
      display();
   }
}  

main() {
   printf("Input Array: ");
   display();
   printline(50);
   selectionSort();
   printf("Output Array: ");
   display();
   printline(50);
}

Complexity:-

AlgorithmWorst caseAverage caseBest case
Bubble sort     O(n2)     O(n2)   
   O(n2)

 

Its worst case would be when the array is in reversed order. In that case, it would perform O(n2).

For average case too its performance is O(n2).

 

posted 6 days ago by Pooja Singh

  Promote This Article
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button


Related Articles

Bubble Sort:-

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in orderBubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, you mustn't swap the element. Then, again second and third elements are compared and swapped if it is necessary and this process go on until last and second last element is compared and swapped.

Note: If there are n elements to be sorted then, the process mentioned above should be repeated n-1 times to get required result.

Algorithm:-

Step 1: Repeat Steps 2 and 3 for i=1 to 10

Step 2: Set j=1

Step 3: Repeat while j<=n

         (A) if  a[i] < a[j]

             Then interchange a[i] and a[j]

             [End of if]

         (B) Set j = j+1
        [End of Inner Loop]

    [End of Step 1 Outer Loop]

Step 4: Exit
Pictorial Representation
 

C program for bubble sort

   #include<stdio.h> //header files

   #include<conio.h>

void bubble_sort(int[], int);

      void main()      //starting of main function

 {

   int arr[30], num, i;    //array of size 30

  printf("\nEnter no of elements :");

   scanf("%d", &num);

   printf("\nEnter array elements :");

   for (i = 0; i < num; i++)

   scanf("%d", &arr[i]);

   bubble_sort(arr, num);     //calling the function

   getch(); //to hold the screen

 }

void bubble_sort(int iarr[], int num) 

{

   int i, j, k, temp;

   printf("\nUnsorted Data:");

   for (k = 0; k < num; k++) 

        {

      printf("%5d", iarr[k]);

        }

      for (i = 1; i < num; i++) 

            {

      for (j = 0; j < num - 1; j++) 

                 {

           if (iarr[j] > iarr[j + 1]) 

                       {

            temp = iarr[j];

            iarr[j] = iarr[j + 1];

            iarr[j + 1] = temp;

                       }

                 }

      printf("\nAfter pass %d : ", i);

      for (k = 0; k < num; k++) 

               {

         printf("%5d", iarr[k]);

               }

         }

}

Complexity:-

AlgorithmWorst caseAverage caseBest case
Bubble sort     O(n2)     O(n2)    O(n)

 

READ MORE
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#470/147, 3rd Floor, 5th Main,
HSR Layout Sector 7,
Bangalore - 560102,
Karnataka INDIA.
QUERY HOME
...