ShellSort is mainly a variation of Insertion Sort.
In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved.
The idea of shellSort is to allow exchange of far items.
int shellSort(int arr[], int n)
{
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2)
{
// Do a gapped insertion sort for this gap size.
for (int i = gap; i < n; i++)
{
int temp = arr[i];
for (int j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}
Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc.
And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.
Category Archives: Sorting
Radix sort
The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit.
Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers,
for example, for decimal system, b is 10.
If k is the maximum possible value, then d would be O(Logb(k)). So overall time complexity is O((n + b) * Logb(k)) .
If we set b as n, we get the time complexity as O(n).
In other words, we can sort an array of integers with range from 1 to nc if the numbers are represented in base n (or every digit takes bits).
void radixsort(int *a, int n)
{
int i, b[MAX], m = a[0], exp = 1;
//Find the greatest value
for (i = 1; i < n; i++)
{
if (a[i] > m)
m = a[i];
}
//Loop until exp is bigger than the largest number
while (m / exp > 0)
{
int bucket[BASE] = { 0 };
for (i = 0; i < n; i++)
bucket[(a[i] / exp) % BASE]++;
//Add the count of the previous buckets to acquire the indexes after the
end of each bucket location in the array
for (i = 1; i < BASE; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % BASE]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
//Multiply exp by the BASE to get the next group of keys
exp *= BASE;
}
}
Bucket Sort
Bucket sort is mainly useful when input is uniformly distributed over a range.
Void Bucket_Sort(int X[n], int n)
{
int i,j, Y[n+1];
for (i = 0; i < n; i++) Y[i] = 0;
for (i = 0; i < n; i++) Y[X[i]]++;
for (i = 0, j = 0; i < n; i++)
while(Y[i]-- > 0) X[j++] = i
}
Runtime – O(n)
Quick Sort using Linked list
struct node
{
int data;
struct node *link;
struct node *plink;
};
struct node *first=NULL, *last=NULL;
void swap(struct node* a,struct node* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void qsort(struct node *low, struct node *high)
{
if(low==NULL || high==NULL || low == high || low->plink == high)
return ;
struct node *pivot=low, *tmp=low->link;
while(tmp != high->link)
{
if(tmp->data < low->data)
{
swap(pivot->link, tmp);
pivot = pivot->link;
}
tmp = tmp->link;
}
swap(low, pivot);
qsort(low, pivot->plink);
qsort(pivot->link, high);
}
Quicksort can be implemented for Linked List only when we can pick a fixed point as pivot. Random QuickSort cannot be efficiently implemented for Linked Lists.
Quick Sort using Double Linked list
struct node
{
int data;
struct node *next;
struct node *prev;
};
void swap(struct node* a,struct node* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void qsort(struct node *low, struct node *high)
{
if(low==NULL || high==NULL || low == high || low->next == high)
return ;
struct node *pivot=low, *tmp=low->next;
while(tmp != high-next)
{
if(tmp->data < low->data)
{
swap(pivot->next, tmp);
pivot = pivot->next;
}
tmp = tmp->next;
}
swap(low, pivot);
qsort(low, pivot->previous);
qsort(pivot->next, high);
}
Quick Sort
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
void QuickSort(int *array, int l, int h)
{
if(l >= h)return;
int pivot = array[l]; /*Pivot is the starting element */
int i = l, temp;
for(int j = l + 1;j <= h;j++)
{
if(array[j] < pivot)
{
i++;
swap(&array[i], &array[j]);
}
}
/*
_______________________i____________________
|pivot|....<=pivot......|....>=pivot......|
*/
swap(&array[i], &array[l]);
/*
____________________i______________________
|...<=pivot......|pivot|....>=pivot......|
*/
QuickSort(array, l, i-1);
QuickSort(array, i+1, h);
}
Although the worst case time complexity of QuickSort is O(n2)
which is more than many other sorting algorithms like Merge Sort and Heap Sort,
QuickSort is faster in practice, because its inner loop can be efficiently implemented on most architectures,
and in most real-world data. quicksort's sequential and localized memory references work well with a cache
Best Case and Average Case: O(nLogn)
QUICK SORT ITERATIVE
int partition (int arr[], int l, int h)
{
int x = arr[h];
int i = l;
for (int j = l+1; j <= h; j++)
{
if (arr[j] <= x)
{
i++;
swap (&arr[i], &arr[j]);
}
}
swap (&arr[i], &arr[h]);
return (i);
}
void quickSortIterative (int arr[], int l, int h)
{
int stack[ h - l + 1 ];
int top = -1;
stack[ ++top ] = l;
stack[ ++top ] = h;
while ( top >= 0 )
{
h = stack[ top-- ];
l = stack[ top-- ];
int p = partition( arr, l, h );
if ( p-1 > l ) {
stack[ ++top ] = l;
stack[ ++top ] = p - 1;
}
if ( p+1 < h ){
stack[ ++top ] = p + 1;
stack[ ++top ] = h;
}
}
}
Merge sort using Linked List
struct node
{
int data;
struct node* next;
};
void MergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;
if ((head == NULL) || (head->next == NULL)){
return;
}
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
if (a->data <= b->data){
result = a;
result->next = SortedMerge(a->next, b);
}
else {
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}
/* Split the nodes of the given list into front and back halves.
If the length is odd, the extra node should go in the front list. */
void FrontBackSplit(struct node* source, struct node** frontRef,
struct node** backRef){
struct node* fast;
struct node* slow;
if (source==NULL || source->next==NULL) {
*frontRef = source;
*backRef = NULL;
}
else {
slow = source;
fast = source->next;
/* Advance 'fast' two nodes, and advance 'slow' one node */
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
/* 'slow' is before the midpoint in the list, so split it in two
at that point. */
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
Merge Sort
int *temp = (int *)malloc(sizeof(int)*array_size);
int mergeSort(int arr[], int temp[], int left, int right)
{
if (right > left)
{
int mid = (right + left)/2;
mergeSort(arr, temp, left, mid);
mergeSort(arr, temp, mid+1, right);
merge(arr, temp, left, mid, right);
}
}
int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
i = left;
j = mid+1;
k = left;
while ((i <= mid) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i=left; i <= right; i++)
arr[i] = temp[i];
}
Time Complexity: O(nLog(n))
Heap Sort
void swap(int *a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
void minHeapify(int a[], int size, int i)
{
int l = 2*i + 1; //using zero based arrays
int r = 2*i + 2;
int smallest = i;
if(l<size && a[l]<a[smallest])
smallest = l;
if(r<size && a[r]<a[smallest])
smallest = r;
if(smallest!=i)
{
swap(&a[i],&a[smallest]);
minHeapify(a,size,smallest);
}
}
void buildMinHeap(int a[], int size) {
for(int i=size/2;i>=0;i--)
minHeapify(a,size,i);
}
void heapsort (int a[], int size)
{
buildMinHeap(a,size);
while (size > 1)
{
swap(&a[0], &ma[size - 1]);
-- size;
minHeapify(a,size,0);
}
}
void removeMin(int a[], int size)
{
if (isEmpty())
throw new HeapException("Heap is empty");
else {
a[0] = a[size - 1];
size--;
if (heapSize > 0)
minHeapify(a,size,0);
}
}
Insertion Sort
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
Time Complexity: O(n*n)
Uses: Insertion sort is uses when number of elements is small. It can also be useful when
input array is almost sorted, only few elements are misplaced in complete big array.
Bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
// IF no two elements were swapped by inner loop, then break
if (swapped == false)
break;
}
}
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
Time Complexity: O(n*n)
Learn By Coding 