# Shell sort and Selection sort

This section covered the algorithms and programs in C and C++ language for shell sort and selection sort.

## Topics Covered

• Algorithm for shell sort
• C program to implement shell sort
• C++ program to implement shell sort
• Algorithm for selection sort
• C program to implement selection sort
• C++ program to implement selection sort

## Algorithm for shell sort

``````shellsort(array, size)
for interval i <- size/2n down to 1
for each interval "i" in array
sort all the elements at interval "i"
exit shellsort``````

### C program to implement shell sort

``````#include <stdio.h>
#include <conio.h>
// Function for shell sort
void shellsort(int array[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}

// Print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d  ", array[i]);
}
printf("\n");
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellsort(data, size);
printf("Sorted array: \n");
printArray(data, size);
}``````

### C++ program to implement shell sort

``````#include<iostream>
using namespace std;

// Function to implement shell sort.
void shellsort(int a[], int n)
{
int i, j, k, temp;

for(i = n/2; i > 0; i = i/2)
{
for(j = i; j < n; j++)
{
for(k = j-i; k >= 0; k = k-i)
{
// If value at the higher index is greater, then break the loop.
if(a[k+i] >= a[k])
break;
// otherwise switch the value
else
{
temp = a[k];
a[k] = a[k+i];
a[k+i] = temp;
}
}
}
}
}
int main()
{
int n, i;
cout<<"\nEnter the size of the array :";
cin>>n;

//applying loop for taking the inputs in the array
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}

shellsort(arr, n);

// Applying loop for printing the final sorted array.
cout<<"\nFinal sorted array \n ";
for (i = 0; i < n; i++)
{
cout<<" "<<arr[i];
}
return 0;
}``````

#### Algorithm for selection sort

``````selectionsort(array, size)
repeat (size - 1) times
set the first unsorted element as the minimum element
for each of the unsorted element
if element < currentminimum
set element as new minimum
swap minimum with first unsorted position
exit selectionsort``````

### C program to implement selection sort

``````#include <stdio.h>
#include <conio.h>

// function to swap the the position of two elements
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void selectionsort(int array[], int size) {
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++)
{
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}
// put min at the correct position
swap(&array[min_idx], &array[step]);
}
}
// function to print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d  ", array[i]);
}
printf("\n");
}
// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionsort(data, size);
printf("Final sorted array in the ascsending Order:\n");
printArray(data, size);
}``````

### C++ program to implement selection sort

``````#include<iostream>
using namespace std;
int main()
{
int n;
cout<<"Enter the value of array size ";
cin>>n;
int arr[n];

//applying loop for taking the inputs in the array
for(int i=0; i<=n; i++ )

{
cin>>arr[i];
}

for(int i=0; i<=n-1; i++)
{
for( int j=i+1; j<=n; j++ )
{
if(arr[i]>arr[j])
{
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}

// Applying loop for printing the final sorted array.
cout<<"Final sorted array "<<endl;
for(int i=0; i<=n; i++ )

{
cout<<arr[i]<<" ";
}
return 0;
}``````

### Complexity

• Shell Sort
• Time – O(n*log n)
• Space- O(1)
• Selection Sort
• Time – O(n2)
• Space- O(1)

You can try the practical on these topics on virtual labs and use these codes for understanding properly.

We will be happy to hear your thoughts
Hello!๐