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.
Radix Sort Implementation
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");
}
void RadixSort(int elements[], int count)
{
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++)
{
printf("Radix position: %s\n",
(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[])
{
printf("Radix sort:\n");
DisplayEntryArray(array, 11);
RadixSort(array, 11);
printf("Radix sort array:\n");
DisplayEntryArray(array, 11);
return 0;
}
Output:
Radix sort: Array elements: 54, 55, 84, 954, 22, 12, 65, 44, 332, 49, 87, Radix position: ones 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, Radix position: tens 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, Radix position: hundreds 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, Radix sort array: 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;
}
};
void SortElements(node *head)
{
if (head == 0)
return;
float key;
node *j,*i, *q=0;
for(i=head->SortUp;i!=0;i=i->SortUp)
{
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]);
}
node *HeadUp=0;
std::cout<<"Sorted array: \n";
for(int i=0; i<n;i++)
{
HeadUp = b[i];
while(HeadUp != 0)
{
std::cout<<HeadUp->info<<" ";
HeadUp = HeadUp->SortUp;
}
}
}
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.
