## More Sorts in Data Structure

In this section of the tutorial, we will discuss a few more Sorting techniques, i.e.Radix Sort, Bucket Sort, Comb Sort, Shell Sort, Bitonic Sort, Cocktail Sort, Cycle Sort, and Tim Sort in Data Structure. We will learn a brief definition of these sorts which will explain their working and purpose. Further, we will implement these sorts in C++ to understand their working more clearly.

## Radix Sort in Data Structure

In Radix Sort, a list of data in the form of integer values is sorted on the basis of their individual digits, which means the sorting algorithm sorts the integer values with the least significant digit and works its way upto the most significant digit.

#### Implementation in C++

Code:

```#include <iostream>
#include <queue>
#include <list>
using namespace std;
int array[]={54,55,84,954,22,12,65,44,332,49,87};
char * Radix_POS [] = {
"ones", "tens", "hundreds", "thousands",
"ten thousands", "hundred thousands", "millions"
};
int FetchPosition(int number, int pos)
{
int DIG;
while (pos > 0)
{
DIG = number % 10;
number = number / 10;
pos--;
}
return DIG;
}
void DisplayEntryArray(int elements[], int count)
{
printf("Array elements: ");
for (int index = 0; index < count; index ++)
{
printf("%d, ",elements[index]);
}
printf("\n");
}
{
queue <int> *q[10];
int i, j, k, max = -2147483648;
for (i = 0; i < count; i++)
{
if (elements[i] > max)
{
max = elements[i];
}
}
i = 0;
while (max)
{
max = max /10;
i++;
}
max = i;
for (i = 0; i < max; i++)
{
(i < 7 )? Radix_POS[i]: "");
for (int j=0; j < 10; j++)
{
q[j] = new queue<int>;
}
for ( k=0; k < count; k++)
{
int DIG = FetchPosition(elements[k], i+1);
q[DIG]->push(elements[k]);
}
k = 0;
for ( j=0; j < 10; j++)
{
printf("Queue[%d]: ", j);
while (!q[j]->empty())
{
elements[k] = q[j]->front();
q[j]->pop();
printf("%d, ", elements[k]);
k++;
}
printf("\n");
}
for ( j=0; j < 10; j++)
{
delete q[j];
}
DisplayEntryArray(elements, count);
}
}
int main(int argc, char* argv[])
{
DisplayEntryArray(array, 11);
DisplayEntryArray(array, 11);
return 0;
}```

Output:

```Radix sort:
Array elements: 54, 55, 84, 954, 22, 12, 65, 44, 332, 49, 87,
Queue[0]:
Queue[1]:
Queue[2]: 22, 12, 332,
Queue[3]:
Queue[4]: 54, 84, 954, 44,
Queue[5]: 55, 65,
Queue[6]:
Queue[7]: 87,
Queue[8]:
Queue[9]: 49,
Array elements: 22, 12, 332, 54, 84, 954, 44, 55, 65, 87, 49,
Queue[0]:
Queue[1]: 12,
Queue[2]: 22,
Queue[3]: 332,
Queue[4]: 44, 49,
Queue[5]: 54, 954, 55,
Queue[6]: 65,
Queue[7]:
Queue[8]: 84, 87,
Queue[9]:
Array elements: 12, 22, 332, 44, 49, 54, 954, 55, 65, 84, 87,
Queue[0]: 12, 22, 44, 49, 54, 55, 65, 84, 87,
Queue[1]:
Queue[2]:
Queue[3]: 332,
Queue[4]:
Queue[5]:
Queue[6]:
Queue[7]:
Queue[8]:
Queue[9]: 954,
Array elements: 12, 22, 44, 49, 54, 55, 65, 84, 87, 332, 954,
Array elements: 12, 22, 44, 49, 54, 55, 65, 84, 87, 332, 954,```

## Bucket Sort in Data Structure

In Bucket Sort, the data elements are intially distributed in the form of several buckets on the insertion in the element’s key. Individual buckets are sorted if required and eventually the buckets are merged or concatenated.

## Bucket Sort Implementation

#### Implementation in C++

Code:

```#include<iostream>
#include<stdio.h>
#include<conio.h>
void Bucket_Sort(float* ,int );
int main()
{
int n,l;
float *a;
std::cout<<"Array Size: \n";
std::cin>>n;
std::cout<<"Enter array elements: \n";
a=new float[n];
for(int l=0;l<n;l++)
std::cin>>a[l];
std::cout<<"Sorted array: \n";
for(l=0;l<n;l++)
std::cout<<a[l]<<" ";
std::cout<<"\n" ;
Bucket_Sort(a,n);
getch();
}
class node
{
public:
float info;
node *SortUp,*Prev;
node(){SortUp=Prev=0;}
node(int n, node *p1=0, node *p2=0)
{
info=n;
SortUp=p1;
Prev=p2;
}
};
{
return;
float key;
node *j,*i, *q=0;

{
q=0;
key = i->info;
j=i->Prev;
while(j!=0 && key < (j->info) )
{
j->SortUp->info=j->info;
q = j;
j=j->Prev;
}
if(q!=0)
q->info = key;
}
}
void Bucket_Sort(float *a,int n)
{
node* *b = new node* [n];
for(int i=0; i<n;i++)
b[i]=0;
for(int i=0;i<n;i++)
{
int index=n*a[i];

node *temp=new node(sizeof(node));
temp->info=a[i];

if(b[index]==NULL)
{
b[index]=temp;
}
else
{
temp->SortUp=b[index];
b[index]->Prev=temp;
b[index]=temp;
}
}
for(int i=0; i<n;i++)
{
SortElements(b[i]);
}
std::cout<<"Sorted array: \n";
for(int i=0; i<n;i++)
{
{
}
}
}```

Output:

```Array Size:
5
Enter array elements:
45
99
112
4
22
Sorted array:
4 22 45 99 112```

## Comb Sort in Data Structure

Comb Sort is the improvised version of bubble sort when the sorting is done on the basis of comparison of elements, it continuously swaps elements that are not in order by iterating multiple sort passes.

## Comb Sort Implementation

#### Implementation in C++

Code:

```#include<bits/stdc++.h>
using namespace std;
int next(int interval)
{
interval = (interval*10)/13;
if (interval < 1)
return 1;
return interval;
}
void CombSort(int a[], int n)
{
int interval = n;
bool swapped = true;
while (interval != 1 || swapped == true)
{
interval = next(interval);
swapped = false;
for (int i=0; i<n-interval; i++)
{
if (a[i] > a[i+interval])
{
swap(a[i], a[i+interval]);
swapped = true;
}
}
}
}
int main()
{
int a[] = {44,545,7,99,10,51,23,4,2,65};
int n = sizeof(a)/sizeof(a[0]);
CombSort(a, n);
printf("Sorted array: \n");
for (int i=0; i<n; i++)
printf("%d ", a[i]);
return 0;
}```

Output:

```Sorted array:
2 4 7 10 23 44 51 65 99 545```

## Bitonic Sort in Data Structure

In Bitonic Sort, the algorithm sorts the data element by comparison method. It arranges an unsorted data list in ascending order and can be applied to elements such as numbers, words, and so on.

## Bitonic Sort Implementation

#### Implementation in C++

Code:

```#include<iostream>
#include<stdio.h>
#include<conio.h>
void BitonicSort(int*, int);
int main()
{
int a[] = {44,545,7,99,10,51,23};
int n = sizeof(a)/sizeof(a[0]);
BitonicSort(a, n);
printf("Sorted array: \n");
for (int i=0; i<n; i++)
printf("%d ", a[i]);
return 0;
}
void BitonicSort(int *data, int N)
{

int i, j, k;
int temp;

for (k = 2;k <= N;k = 2 * k)
{
for (j = k >> 1;j>0; j = j >> 1)
{
for (i = 0;i<N;i++)
{
int ixj = i^j;

if ((ixj)>i)
{
if ((i&k) == 0 && data[i] > data[ixj]) {
temp = data[i];
data[i] = data[ixj];
data[ixj] = temp;
}

if ((i&k) != 0 && data[i] < data[ixj]) {
temp = data[i];
data[i] = data[ixj];
data[ixj] = temp;
}

}
}
}
}

}```

Output:

```Sorted array:
7 10 23 44 51 99 545```

## Cocktail Sort in Data Structure

Cocktail Sort works in a way similar to the Bubble Sort by iterating multiple times for each element while comparing adjacent elements and swapping them in both directions, i.e. previous element and next element if required.

## Cocktail Sort Implementation

#### Implementation in C++

Code:

```#include <iostream>
using namespace std;
int temp;
void CocktailSort(int* , int);
int main()
{
int arr[] = {45,34,11,3,97,65};
int i;
int n = sizeof(arr) / sizeof(arr[0]);
CocktailSort(arr, n);
cout <<"Sorted array: \n";
for (i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<"\n";
return 0;
}
void CocktailSort(int a[], int n)
{
int swap = 1;
int start = 0,i;
int end = n - 1;
while (swap)
{
swap = 0;
for (i = start; i < end; ++i)
{
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
swap = 1;
}
}
if (!swap)
break;
swap = 0;
for (i = end - 1; i >= start; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
swap = 1;
}
}
++start;
}
}```

Output:

```Sorted array:
3 11 34 45 65 97```

## Cycle Sort in Data Structure

In Cycle Sort, the number of times sort passes are to be carried out is framed into cycles, which is can be eventually rotated to give the sorted list. It is efficient in terms of memory writes. Its value is either set to zero times if its position is correct in the list or the values are set to one if its position is incorrect in the list.

## Cycle Sort Implementation

#### Implementation in C++

Code:

```#include<iostream>
using namespace std;
void Swap(int &, int &);
void PrintData(int *, int);
void CycleSort(int *, int);
int main()
{
int n;
cout << "Size of array: ";
cin >> n;
int array1[n];
cout << "Enter array elements:" << endl;
for(int i = 0; i<n; i++)
{
cin >> array1[i];
}
cout << "Before Sorting: ";
PrintData(array1, n);
CycleSort(array1, n);
cout << "After Sorting: ";
PrintData(array1, n);
}
void Swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void PrintData(int *array, int size)
{
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void CycleSort(int *array, int n)
{
for(int start = 0; start<n-1; start++)
{
int key = array[start];
int location = start;
for(int i = start+1; i<n; i++)
{
if(array[i] < key)
location++;
}
if(location == start)
continue;
while(key == array[location])
location++;
if(location != start)
Swap(array[location], key);

while(location != start) {
location = start;

for(int i = start+1; i<n; i++)
{
if(array[i] < key)
location++;
}
while(key == array[location])
location++;
if(key != array[location])
Swap(key, array[location]);
}
}
}```

Output:

```Size of array: 5
Enter array elements:
12
99
4
65
-2
Before Sorting: 12 99 4 65 -2
After Sorting: -2 4 12 65 99```

## Tim Sort in Data Structure

Tim Sort is the fastest solving algorithm among all algorithms we have learnt so far. It is a hybrid and stable sorting algorithm. It works by analyzing the data pattern and then uses the most efficient and fast approach to sort the list.

## Tim Sort Implementation

#### Implementation in C++

Code:

```#include <iostream>
using namespace std;
const int exec = 32;

void InsertionSort(int arr[], int post, int pre)
{
for (int i = post + 1; i <= pre; i++)
{
int temp = arr[i];
int j = i - 1;
while (arr[j] > temp && j >= post)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
void MergeSort(int arr[], int l, int m, int r)
{
int x = m - l + 1, y = r - m;
int post[x], pre[y];
for (int i = 0; i < x; i++)
post[i] = arr[l + i];
for (int i = 0; i < y; i++)
pre[i] = arr[m + 1 + i];

int i = 0;
int j = 0;
int k = l;
while (i < x && j < y)
{
if (post[i] <= pre[j])
{
arr[k] = post[i];
i++;
}
else
{
arr[k] = pre[j];
j++;
}
k++;
}
while (i < x)
{
arr[k] = post[i];
k++;
i++;
}
while (j < y)
{
arr[k] = pre[j];
k++;
j++;
}
}
void TimSort(int arr[], int n)
{
for (int i = 0; i < n; i+=exec)
InsertionSort(arr, i, min((i+31), (n-1)));
for (int size = exec; size < n; size = 2*size)
{
for (int post = 0; post < n; post += 2*size)
{
int mid = post + size - 1;
int pre = min((post + 2*size - 1), (n-1));
MergeSort(arr, post, mid, pre);
}
}
}
void SortedArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d  ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {54, 6, 78, 43, -9};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Unsorted Array: \n");
SortedArray(arr, n);
TimSort(arr, n);
printf("Sorted Array: \n");
SortedArray(arr, n);
return 0;
}```

Output:

```Unsorted Array:
54  6  78  43  -9
Sorted Array:
-9  6  43  54  78```

In the next section of the tutorial, we will discuss the use of Linked List in Data Structure and its implementation in programs that will be used thoroughly in this Data Structure tutorial.