C Implementation of Various Sorting Algorithms

This is a simple C implementation of various sorting algorithms such as Bubble Sort, Insertion Sort, Selection Sort and Shell Sort.

Bubble Sort

Bubble sort, is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Complexity:

Worst complexity: n^2
Best complexity: n

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final list one item at a time. This is an in-place comparison-based sorting algorithm. It is much less efficient on large lists than more advanced algorithms such as quick sort, heap sort, or merge sort.

Complexity:

Worst complexity: n^2
Best complexity: n^2

Selection Sort

Selection sort 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.

Complexity:

Worst complexity: n^2
Best complexity: n^2

Shell Sort

Shell Sort Algorithm, also known as Shell sort or Shell’s method, is an in-place comparison sorting algorithm. It can be seen as either a generalization of sorting by exchange or sorting by insertion.

Complexity:

Average complexity: n*log(n)^2 or n^(3/2)
Best complexity: n

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

void bubblesort(float[], int);
void insertionsort(float[], int);
void selectionsort(float[], int); 
void shellsort(float[], int);

void print(float[], int);
void read(float[], int);

void main() {
  char wtc = 'y';
  while (wtc == 'y' || wtc == 'Y') {
    clrscr();
    int choice, n;
    float a[200];
    printf("Enter the size of array");
    scanf("%d", & n);
    printf("\n");
    printf("Enter %d integers of array", n);

    read(a, n);
    printf("\n Enter the following numbers to use the following techniques:\n");
    printf("\t1.BUBBLE SORT\n");
    printf("\t2.INSERTION SORT\n");
    printf("\t3.SELECTION SORT\n");
    printf("\t4.SHELL SORT\n");

    printf("\n");
    printf("Enter your choice");
    scanf("%d", & choice);
    switch (choice) {
    case 1:
      {
        bubblesort(a, n);
        print(a, n); //calling funtion by using switch statements
        getch();
        break;
      }
    case 2:
      {
        insertionsort(a, n);
        print(a, n);
        getch();
        break;
      }
    case 3:
      {
        selectionsort(a, n);
        print(a, n);
        getch();
        break;
      }
    case 4:
      {
        shellsort(a, n);
        print(a, n);
        getch();
        break;
      }
    }
    cout << "\n\n Do you want to continue(y/n)";
    cin >> wtc;
  }
  getch();
}

void read(float a[], int n) {
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
}

//Bubble sort implementation
void bubblesort(float a[], int n) {
  for (int p = 0; p < (n - 1); p++) {
    for (int i = 0; i < n - 1; i++) {
      if (a[i] > a[i + 1]) {
        float temp;
        temp = a[i + 1];
        a[i + 1] = a[i];
        a[i] = temp;
      }
    }
  }
}

//Insertion sort implementation
void insertionsort(float a[], int n) {
  for (int i = 1; i < n; i++) {
    float x = a[i];
    int j = i;
    while (j > 0 && a[j - 1] > x) //definition of insertion sort
      a[j--] = a[j - 1];
    a[j] = x;
  }
}

//Shell sort implementation
void shellsort(float a[], int n) {
  int gap;
  int swap;
  gap = n / 2;

  int k = 0;
  do {
    do {

      swap = 0;
      k++;
      int i;
      for (i = 0; i < n - gap; i++)
        if (a[i] > a[i + gap]) {
          int temp;
          temp = a[i];
          a[i] = a[i + gap];
          a[i + gap] = temp;

          swap = 1;
        }
      for (int t = 0; t < n; t++)
        cout << " " << a[t];
      cout << "swap=" << swap;
      cout << "\n";
    } while (swap);
  } while (gap = gap / 2);
}

//Selection sort implementation
void selectionsort(float a[], int n) {
  for (int i = 0; i < n; i++) {

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

void print(float a[], int n) {
  for (int i = 0; i < n; i++) {
    cout << a[i] << ",";
  }
  cout << endl;
}