/*
Summary: Shell Sort generalizes an exchanging sort, such as insertion or bubble sort, by starting the comparison and exchange of elements with elements that are far apart before finishing with neighboring elements. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange.The idea is to arrange the list of elements so that, starting anywhere, considering every hth element gives a sorted list.
*/

#include  <stdio.h>
#define size 10
/* Function Prototype */
int shell_sort(int []);

int main()
{
 int arr[size], i;

 printf("Enter 10 elements to be sorted:");
 for (i = 0;i < size;i++)
 {
  scanf("%d", &arr[i]);
 }

 shell_sort(arr);

 printf("The array after sorting is:");
 for (i = 0;i < size;i++)
 {
  printf("\n%d", arr[i]);
 }

 return 0;
}



    /* Code to sort array using shell sort */

int shell_sort(int array[])
{
 int i = 0, j = 0, k = 0, mid = 0;

 for (k = size / 2;k > 0;k /= 2)
 {
  for (j = k;j < size;j++)
  {
   for (i = j - k;i >= 0;i -= k)
   {
    if (array[i + k] >= array[i])
    {
     break;
    }
    else
    {
     mid = array[i];
     array[i] = array[i + k];
     array[i + k] = mid;
    }
   }
  }
 }

 return 0;
}

/*
Summary: Selection sort divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted. It proceeds by finding the smallest (or largest) element in the unsorted sublist, exchanging it with the leftmost unsorted element and moving the sublist boundaries one element to the right.
Complexity - O(n^2)
*/

#include<conio.h>
#include<stdio.h>
#define max 50

int selsort(int, int[]);

int main()
{
 int i, size, data[max];

 printf("\nEnter no of Elements:");
 scanf("%d",&size);

 printf("\nEnter Elements:");
 for(i=1;i<=size;i++)
  scanf("%d",&data[i]);

 printf("\nUnsorted data:\n");
 for(i=1;i<=size;i++)
  printf("%d\t",data[i]);

 selsort(size, data);

 return 0;
}

int selsort(int n, int data[])
{
 int i, j, min, temp;

 printf("\nSorted List is:\n");
 for(i=1;i<=n-1;i++)
 {
  min = i;
  for(j=i+1;j<=n;j++)
  {
   if(data[j]<data[min])
    min = j;
  }

  temp=data[i];
  data[i]=data[min];
  data[min]=temp;
 }

 for(i=1;i<=n;i++)
  printf("%d\t",data[i]);

}

/*
Summary: Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.
Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least digit and move towards the most significant digit. MSD radix sorts work the other way around.
Complexity - O(d·n)
*/

#include <stdio.h>
int min = 0, count = 0, array[100] = {0}, array1[100] = {0};

int main()
{
 int k, i, j, temp, t, n;

 printf("Enter size of array :");
 scanf("%d", &count);

 printf("Enter elements into array :");
 for (i = 0; i < count; i++)
 {
  scanf("%d", &array[i]);
  array1[i] = array[i];
 }

 for (k = 0; k < 3; k++)
 {
  for (i = 0; i < count; i++)
  {
                min = array[i] % 10;        /* To find minimum lsd */
   t = i;
   for (j = i + 1; j < count; j++)
   {
    if (min > (array[j] % 10))
    {
     min = array[j] % 10;
     t = j;
    }
   }

   temp = array1[t];
   array1[t] = array1[i];
   array1[i] = temp;
   temp = array[t];
   array[t] = array[i];
   array[i] = temp;
  }

        for (j = 0; j < count; j++)        /*to find MSB */
            array[j] = array[j] / 10;
 }

 printf("Sorted Array (Radix sort) : ");
 for (i = 0; i < count; i++)
  printf("%d ", array1[i]);

 return 0;
}

/*
Summary: Quicksort is a very efficient sorting algorithm.It has two phases:
-the partition phase and
-the sort phase.
Most of the work is done in the partition phase - it works out where to divide the work. The sort phase simply sorts the two smaller problems that are generated in the partition phase.
Complexity: O(n·log n)
*/

#include <stdio.h>
int quicksort (int [], int, int);

int main()
{
 int list[50];
 int size, i;

 printf("Enter the number of elements: ");
 scanf("%d", &size);

 printf("Enter the elements to be sorted:\n");
 for (i = 0; i < size; i++)
 {
  scanf("%d", &list[i]);
 }

 quicksort(list, 0, size - 1);

 printf("After applying quick sort\n");
 for (i = 0; i < size; i++)
 {
  printf("%d ", list[i]);
 }

 printf("\n");

 return 0;
}

int quicksort(int list[], int low, int high)
{
 int pivot, i, j, temp;

 if (low < high)
 {
  pivot = low;
  i = low;
  j = high;

  while (i < j)
  {
   while (list[i] <= list[pivot] && i <= high)
   {
    i++;
   }
   while (list[j] > list[pivot] && j >= low)
   {
    j--;
   }
   if (i < j)
   {
    temp = list[i];
    list[i] = list[j];
    list[j] = temp;
   }
  }

  temp = list[j];
  list[j] = list[pivot];
  list[pivot] = temp;
  quicksort(list, low, j - 1);
  quicksort(list, j + 1, high);

 }
}

/*
Summary: Merge sort is a divide and conquer comparison-based sorting algorithm. It works as follows:-
1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.
Complexity - O(n·log n)
*/

#include <stdio.h>
int mergeSort(int [], int, int, int);
int partition(int [],int, int);

int main()
{
 int list[50];
 int i, size;

 printf("Enter total number of elements:");
 scanf("%d", &size);

 printf("Enter the elements:\n");
 for(i = 0; i < size; i++)
 {
  scanf("%d", &list[i]);
 }

 partition(list, 0, size - 1);

 printf("After merge sort:\n");
 for(i = 0;i < size; i++)
 {
  printf("%d   ",list[i]);
 }

 return 0;

}

int partition(int list[],int low,int high)
{
 int mid;

 if(low < high)
 {
  mid = (low + high) / 2;
  partition(list, low, mid);
  partition(list, mid + 1, high);
  mergeSort(list, low, mid, high);
 }
}

int mergeSort(int list[],int low,int mid,int high)
{
 int i, mi, k, lo, temp[50];

 lo = low;
 i = low;
 mi = mid + 1;

 while ((lo <= mid) && (mi <= high))
 {
  if (list[lo] <= list[mi])
  {
   temp[i] = list[lo];
   lo++;
  }
  else
  {
   temp[i] = list[mi];
   mi++;
  }
  i++;
 }

 if (lo > mid)
 {
  for (k = mi; k <= high; k++)
  {
   temp[i] = list[k];
   i++;
  }
 }
 else
 {
  for (k = lo; k <= mid; k++)
  {
   temp[i] = list[k];
   i++;
  }
 }

 for (k = low; k <= high; k++)
 {
  list[k] = temp[k];
 }
}

/*
Summary: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Complexity - O(n^2)
*/

#include <stdio.h>
#define MAX 10
int insertion_sort(int *);

int main()
{
 int a[MAX], i;

 printf("enter 10 elements to be sorted:");
 for (i = 0;i < MAX;i++)
 {
  scanf("%d", &a[i]);
 }

 insertion_sort(a);

 printf("sorted elements:\n");
 for (i = 0;i < MAX; i++)
 {
  printf(" %d", a[i]);
 }

 return 0;
}

/* sorts the input */
int insertion_sort(int * x)
{
 int temp, i, j;

 for (i = 1;i < MAX;i++)
 {
  temp = x[i];
  j = i - 1;
  while (temp < x[j] && j >= 0)
  {
   x[j + 1] = x[j];
   j = j - 1;
  }
  x[j + 1] = temp;
 }
}

/*
Summary: The heapsort algorithm can be divided into two parts.
-Step 1: a heap is built out of the data.
-Step 2: a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array.
The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by choosing a min-heap or max-heap in step one.
Complexity: O(n·log n)
*/

#include <stdio.h>
int main()
{
 int heap[10], no, i, j, c, root, temp;

 printf("\n Enter no of elements :");
 scanf("%d", &no);
 printf("\n Enter the nos : ");

 for (i = 0; i < no; i++)
  scanf("%d", &heap[i]);

 for (i = 1; i < no; i++)
 {
  c = i;
  do
  {
   root = (c - 1) / 2;
                if (heap[root] < heap[c])   /* to create MAX heap array */
   {
    temp = heap[root];
    heap[root] = heap[c];
    heap[c] = temp;
   }
   c = root;
  } while (c != 0);
 }

 printf("Heap array : ");
 for (i = 0; i < no; i++)
  printf("%d\t ", heap[i]);

 for (j = no - 1; j >= 0; j--)
 {
  temp = heap[0];
            heap[0] = heap[j];    /* swap max element with rightmost leaf element */
  heap[j] = temp;
  root = 0;
  do
  {
                c = 2 * root + 1;    /* left node of root element */
   if ((heap[c] < heap[c + 1]) && c < j-1)
    c++;
                if (heap[root]<heap[c] && c<j)    /* again rearrange to max heap array */
   {
    temp = heap[root];
    heap[root] = heap[c];
    heap[c] = temp;
   }
   root = c;
  } while (c < j);
 }

 printf("\n The sorted array is : ");
 for (i = 0; i < no; i++)
  printf("\t %d", heap[i]);

 printf("\n Complexity : \n Best case = Avg case = Worst case = O(n logn) \n");

 return 0;
}

/*
Summary: Gnome sort(stupid sort) is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. It is conceptually simple, requiring no nested loops.
Complexity - O(n^2)
*/

#include <stdio.h>
int main()
{
 int i, temp, ar[10], n;

 printf("\nenter the elements number u would like to enter:");
 scanf("%d", &n);
 printf("\nenter the elements to be sorted through gnome sort:\n");

 for (i = 0; i < n; i++)
  scanf("%d", &ar[i]);
 i = 0;
 while (i < n)
 {
  if (i == 0 || ar[i - 1] <= ar[i])
   i++;
  else
  {
   temp = ar[i-1];
   ar[i - 1] = ar[i];
   ar[i] = temp;
   i = i - 1;
  }
 }

 for (i = 0;i < n;i++)
  printf("%d\t", ar[i]);

    return 0;
}

/*
Summary: Cocktail sort is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than a bubble sort, and solves the problem of turtles in bubble sorts.
The various names of cocktail sort are bidirectional bubble sort, cocktail shaker sort, shaker sort, ripple sort, shuffle sort, shuttle sort or happy hour sort.
Complexity - O(n^2)
*/

#include <stdio.h>
#define MAX 8
int main()
{
 int data[MAX];
 int i, j, n, c;

 printf("\nEnter the data");
 for (i = 0; i < MAX; i++)
 {
  scanf("%d", &data[i]);
 }

 n = MAX;
 do
 {
/*Rightward pass will shift the largest element to its correct place at the end*/
  for (i = 0;  i < n - 1; i++)
  {
   if (data[i] > data[i + 1])
   {
    data[i] = data[i] + data[i + 1];
    data[i + 1] = data[i] - data[i + 1];
    data[i] = data[i] - data[i + 1];
   }
  }

  n = n - 1;
/* Leftward pass will shift the smallest element to its correct place at the beginning*/
  for (i= MAX - 1, c = 0; i >= c; i--)
  {
   if(data[i] < data[i - 1])
   {
    data[i] = data[i] + data[i - 1];
    data[i - 1] = data[i] - data[i - 1];
    data[i] = data[i] - data[i - 1];
   }
  }

  c = c + 1;
 } while (n != 0 && c != 0);

 printf("The sorted elements are:");
 for (i = 0; i < MAX; i++)
 {
  printf("%d\t", data[i]);
 }

 return 0;
}

/*
Summary: Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.
Complexity - O(n^2)
*/

#include <stdio.h>
#define MAXSIZE 10

int main()
{
 int array[MAXSIZE];
 int i, j, num, temp;

 printf("Enter the value of num \n");
 scanf("%d", &num);

 printf("Enter the elements one by one \n");
 for (i = 0; i < num; i++)
 {
  scanf("%d", &array[i]);
 }

   /*   Bubble sorting begins */
 for (i = 0; i < num; i++)
 {
  for (j = 0; j < (num - i - 1); j++)
  {
   if (array[j] > array[j + 1])
   {
    temp = array[j];
    array[j] = array[j + 1];
    array[j + 1] = temp;
   }
  }
 }

 printf("Sorted array is...\n");

 for (i = 0; i < num; i++)
 {
  printf("%d\n", array[i]);
 }

 return 0;
}

/*
Summary: Alphabetical sort is a program whereby strings of characters are placed in order based on the position of the characters in the conventional ordering of an alphabet.
*/

#include <stdio.h>
#include <string.h>
#include <conio.h>
int main()
{
 char name[10][8], tname[10][8], temp[8];
 int i, j, n;

 printf("Enter the value of n \n");
 scanf("%d", &n);
 printf("Enter %d names ", n);

 for (i = 0; i < n; i++)
 {
  scanf("%s", name[i]);
  strcpy(tname[i], name[i]);
 }
 for (i = 0; i < n - 1 ; i++)
 {
  for (j = i + 1; j < n; j++)
  {
   if (strcmp(name[i], name[j]) > 0)
   {
    strcpy(temp, name[i]);
    strcpy(name[i], name[j]);
    strcpy(name[j], temp);
   }
  }
 }

 printf("\n----------------------------------------\n");
 printf("Input Names\tSorted names\n");
 printf("------------------------------------------\n");

 for (i = 0; i < n; i++)
 {
  printf("%s\t\t%s\n", tname[i], name[i]);
 }

 printf("------------------------------------------\n");

 return 0;
}