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
40 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 Apr 20 by Pooja Singh

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


Related Articles

Quick Sort

Quick sort is a very popular sorting method. This sort name comes from the fact that quick sort can sort a list of data elements significantly faster than any of the common sorting algorithms. This sorting uses a strategy called divide and conquer. It is based on the principle that is faster and easier to sort two small arrays than one larger one. 

The sequence of steps required to perform a quick sort operation on a set of elements of  the array are as follows.

  1. A pivot item near the middle of the array is chosen. Let it be x.
  2. Now scan the array from left to right until some element e.g., ai>x is encountered.
  3. Now scan the array from right to left until some element e.g.,aj<x is encountered.
  4. Now exchange the items ai and aj.
  5. Again repeat steps 2 to 4 until the scan operation meets somewhere in the middle of the array.

Quick sort is also called partition exchange sort and it was invented by C.A.R. Hoare. The average execution time of quick sort is O(n(log2n)2) and this sort is good for large sorting jobs.

Pictorial Representation

 

 

Quick Sort Algorithm

1. If n < = 1, then return.

2. Pick any element V in a[]. This is called the pivot.

3. Rearrange elements of the array by moving all elements xi > V right of V and all elements x­i < = V left of V. If the place of the V after re-arrangement is j, all elements with value less than V, appear in a[0], a[1] . . . . a[j – 1] and all those with value greater than V appear in a[j + 1] . . . . a[n – 1].

4. Apply quick sort recursively to a[0] . . . . a[j – 1] and to a[j + 1] . . . . a[n – 1].

Program for Quick Sort 

#include <stdio.h>

void quick_sort(int[], int, int);
int partition(int[], int, int);

int main() 
{
    int a[50], n, i;

    printf("How many elements?");
    scanf("%d", & n);
    printf("\nEnter array elements:");

    for  (i = 0; i < n; i++)
    {
        scanf("%d", & a[i]);
    }

    quick_sort(a, 0, n - 1);

    printf("\nArray after sorting:");

    for (i = 0; i < n; i++)
    {  
        printf("%d ", a[i]);
    }


    return 0;
}

 

void quick_sort(int a[], int l, int u) 
{
    int j;

    if  (l < u) 
    {
        j = partition(a, l, u);
        quick_sort(a, l, j - 1);
        quick_sort(a, j + 1, u);
    }
}

 

int partition(int a[], int l, int u) 
{
    int v, i, j, temp;
    v = a[l];
    i = l;
    j = u + 1;

    do 
    {
        do
        {
            i++;
        }

        while (a[i] < v && i <= u);

        do
        {
            j--;
        }

        while (v < a[j]);

        if  (i < j)
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    } 

    while (i < j);

    a[l] = a[j];
    a[j] = v;

    return (j);

}

The complexity of the quick sort algorithm is given in the following table.

AlgorithmWorst caseAverage caseBest case
Quick sortO(n)2log2nlog2n
READ MORE
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...