Selection sort, also called in-place comparison sort, is a sorting algorithm in computer programming. It is well-known algorithm for its simplicity and also performance advantages. The article shows the process with C language code and an example.

As the name indicates, first we select the smallest item in the list and exchange it with the first item. Then we select the second smallest in the list and exchange it with the second element and so on. Finally, all the items will be arranged in ascending order. Since, the next least item is selected and exchanged accordingly so that elements are finally sorted, this technique is called selection sort.

For example, consider the elements 50, 40, 30, 20, 10 and sort using selection sort.

pos = i;

for(j=i+1; j<n; j++)

{

If(arr[j] < arr[pos])

pos = j;

}

After finding the position of the smallest number, it should be exchanged with i'th position. The equivalent statements are shown below:

temp = arr[pos];

arr[pos] = arr[i];

arr[i] = temp;

The above procedure has to be performed for each value of i in the range 0 < i < n-1. The equivalent

Step1: [Input the number of items]

Read: n

Step2: [Read n elements]

for i = 0 to n-1

Read: arr[i]

[End of for]

Step3: for i = 0 to n - 2 do

pos = i;

for j = I + 1 to n – 1 do

if(arr[j] < arr[pos]) then

pos = j

[End of if]

[End of for]

temp = arr[pos]

arr[pos] = arr[i]

arr[i] = temp

[End of for]

Step4: [Display Sorted items]

for i = 0 to n -1

Write: arr[i]

[End of for]

Step5: Exit

main()

{

int n, arr[10], pos, i, j, temp;

clrscr();

printf("Enter the number of items:\n");

scanf("%d",&n);

printf("Input the n items here:\n");

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

{

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

}

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

{

pos = i;

for(j = i+1; j< n; j++)

{

if(arr[j] < arr[pos])

pos = j;

}

temp = arr[pos];

arr[pos] = arr[i];

arr[i] = temp;

}

printf("The sorted elements are as:\n");

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

{

printf("%d\n",arr[i]);

}

getch();

}

The program will outputs as:

Binary Search in C

Linear Search in C

As the name indicates, first we select the smallest item in the list and exchange it with the first item. Then we select the second smallest in the list and exchange it with the second element and so on. Finally, all the items will be arranged in ascending order. Since, the next least item is selected and exchanged accordingly so that elements are finally sorted, this technique is called selection sort.

For example, consider the elements 50, 40, 30, 20, 10 and sort using selection sort.

**Design**: The position of smallest element from i'th position onwards can be obtained using the following code:pos = i;

for(j=i+1; j<n; j++)

{

If(arr[j] < arr[pos])

pos = j;

}

After finding the position of the smallest number, it should be exchanged with i'th position. The equivalent statements are shown below:

temp = arr[pos];

arr[pos] = arr[i];

arr[i] = temp;

The above procedure has to be performed for each value of i in the range 0 < i < n-1. The equivalent

**algorithm**to sort N elements using selection sort is shown below:Step1: [Input the number of items]

Read: n

Step2: [Read n elements]

for i = 0 to n-1

Read: arr[i]

[End of for]

Step3: for i = 0 to n - 2 do

pos = i;

for j = I + 1 to n – 1 do

if(arr[j] < arr[pos]) then

pos = j

[End of if]

[End of for]

temp = arr[pos]

arr[pos] = arr[i]

arr[i] = temp

[End of for]

Step4: [Display Sorted items]

for i = 0 to n -1

Write: arr[i]

[End of for]

Step5: Exit

**C**program to implement the selection sort.main()

{

int n, arr[10], pos, i, j, temp;

clrscr();

printf("Enter the number of items:\n");

scanf("%d",&n);

printf("Input the n items here:\n");

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

{

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

}

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

{

pos = i;

for(j = i+1; j< n; j++)

{

if(arr[j] < arr[pos])

pos = j;

}

temp = arr[pos];

arr[pos] = arr[i];

arr[i] = temp;

}

printf("The sorted elements are as:\n");

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

{

printf("%d\n",arr[i]);

}

getch();

}

The program will outputs as:

**Advantages**- Very simple and easy to implement.
- Straight forward approach.

**Disadvantages**- It is not efficient. More efficient sorting techniques are present.
- Even if the elements are sorted, n-1 passes are required.

Binary Search in C

Linear Search in C

## 0 comments :

## Post a Comment