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;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

#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 {

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;

}

Bubble Sort

Insertion Sort

Selection Sort

Shell Sort

About The Author

M. Saqib

C Implementation of Various Sorting Algorithms

Bubble Sort

Insertion Sort

Selection Sort

Shell Sort

About The Author

M. Saqib

Related Posts

C Program to show Fibonacci Sequence

C Implementation of Base64 Encoding and Decoding

Smith-Waterman Algorithm – The Optimal Pairwise Sequence Alignment Problem

Insertion in Arrays using C [Add an element in Array in C]