# Selection Sort in C

## What is Selection Sort in C

In this Sorting technique the list is divided into two parts. first one is left end and second one is right end .  The selection Sort is very  simple sorting algorithm. Time Complexity (Best) Ω(n2) Time Complexity (Avg) Θ(n2) Time Complexity (Worst) O(n2) Space Complexity O(1)

## Steps for Selection Sort in C

There are following Step of selection sort algorithm.

• Step 1-Select the smallest value in the list.
• Step 2-Swap smallest value with the first element of the list.
• Step 3-Again select the smallest value in the list (exclude first value).
• Step 4- Repeat above step for (n-1) elements untill the list is sorted. ### Implementation of Selection Sort

• We have been given a unsorted array. which we’ll  make  a sorted array using selection sort. first of all  find the smallest value in the array and then swap smallest value with the starting value.
• According to the below image,  8 is smallest value in this array so 8 is swapped with the first element that is 72.
• Similarly, in the next iteration we’ll  find the next smallest value, excluding the starting value so in this array  10 is second smallest value, which is to be swapped with 50.
• These iteration will continue until we have the largest element to the right most end, along with all the other elements in their correct position.
• And then we can finally say that the given array is converted in sorted array. ### Algorithm of selection  sort

#### Algorithm  SELECTION(A,N): This algorithm sorts the array A with N elements.

1-[loop]

Repeat Step 2 and 3 for K=0,1,2,..N-2:

2-Call MIN(A,K,N)

3-[Interchange A[K] and A[LOC].]

Set TEMP=A[K],A[K]=A[LOC] and

A[LOC]=TEMP.

[End of Step 1 loop]

4-Exit.

### Code of Selection sort in C

```// C program for implementation of selection sort
#include <stdio.h>

/* Display function to print values */
void display(int array[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ",array[i]);
}
printf("\n");
}

// The main function to drive other functions
int main()
{
int array[] = {5, 3, 1, 9, 8, 2, 4, 7};
int size = sizeof(array)/sizeof(array);

printf("This is how array looks before sorting: \n");
display(array, size);

int i, j, min_idx,temp;

// Loop to iterate on array
for (i = 0; i < size-1; i++)
{
// Here we try to find the min element in array
min_idx = i;
for (j = i+1; j < size; j++)
{
if (array[j] < array[min_idx])
min_idx = j;
}
// Here we interchange the min element with first one                            temp = array[min_idx];
array[min_idx] = array[i];
array[i] = temp;}
printf("This is how array looks after sorting: \n");
display(array, size);

return 0;
}```
`// C program for implementation of selection sort  #include <stdio.h>void swap(int *xp, int *yp)  {      int temp = *xp;      *xp = *yp;      *yp = temp;  }  void selectionSort(int array[], int size)  {      int i, j, min_idx;      // Loop to iterate on array     for (i = 0; i < size-1; i++)      {          // Here we try to find the min element in array         min_idx = i;          for (j = i+1; j < size; j++)        {        if (array[j] < array[min_idx])              min_idx = j;          }        // Here we interchange the min element with first one          swap(&array[min_idx], &array[i]);      }  }  /* Display function to print values */void display(int array[], int size)  {      int i;      for (i=0; i < size; i++)    {          printf("%d ",array[i]);    }    printf("\n");  }  // The main function to drive other functions int main()  {      int array[] = {5, 3, 1, 9, 8, 2, 4, 7};      int size = sizeof(array)/sizeof(array);    printf("This is how array looks before sorting: \n");      display(array, size);    selectionSort(array, size);     printf("This is how array looks after sorting: \n");      display(array, size);     return 0;  }  `

### Output

#### Output

`This is how array looks before sorting:   5 3 1 9 8 2 4 7This is how array looks after sorting:1 2 3 4 5 7 8 9`

## Performance

The Selection Sort best and worst case scenarios both follow the time complexity format O(n^2) as the sorting operation involves two nested loops. The size of the array again affects the performance.

#### Strengths

• The arrangement of elements does not affect its performance.
• Uses fewer operations, so where data movement is costly it is more economical

#### Weaknesses

• The comparisons within unsorted arrays requires O(n^2) which is ideal where n is small  Ω(n2)

Θ(n2)

O(n2)

O(1)

## Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews. 