Home » Shell sort and Selection sort

AlgorithmsC++ programmingData structures

Shell sort and Selection sort

Arpit Jain

May 19, 2021

0

SaveSavedRemoved 0

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(n²)
  • Space- O(1)

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