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.
Monthly Archives: October 2014
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;
}
}
How is the complexity of bucket sort is O(n+k) if we implement buckets using linked lists?
Right now, you are correct that iterating across the input array to distribute the elements into buckets takes time O(n). However, you are slightly off when you say that the total amount of time required to assemble the array is O(k * (average number of elements per bucket)). Note that because there are n elements and k buckets, this would come out to O(k * (n / k)) = O(n), for a total runtime of O(n). It is not true that k * O(n / k) = O(n). The reason for this is that the term O(n / k) is hiding a constant factor. When you visit each bucket and take a look at the elements it contains, it doesn't take exactly n / k time, or even some constant multiple of n / k time. For example, what happens if the bucket is empty? In that case, you're still spending some amount of time looking at the bucket, since you have to determine that you shouldn't iterate over its elements. Thus a more accurate representation of the time required per bucket is something like c0(n / k) + c1, where c0 and c1 are implementation-specific constants. This expression is, of course, O(n / k). The catch is what happens when you multiply this expression by k to get the total amount of work done. If you compute k * (c0(n / k) + c1) You get c0n + c1k As you can see, this expression depends directly on k, so the total runtime is O(n + k).
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;
}
}
}
Count Inversions in an array
int *temp = (int *)malloc(sizeof(int)*array_size);
int mergeSort(int arr[], int temp[], int left, int right)
{
int count = 0;
if (right > left)
{
int mid = (right + left)/2;
count = mergeSort(arr, temp, left, mid);
count += mergeSort(arr, temp, mid+1, right);
count += merge(arr, temp, left, mid, right);
}
return count;
}
int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int count1 = 0;
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++];
count1 += (mid - i);
}
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i=left; i <= right; i++)
arr[i] = temp[i];
}
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))
Queue using linkedlist
struct Queue
{
int Data;
struct Queue* next;
}*rear, *front;
void enqueue (int value)
{
if (rear == NULL)
{
rear = (struct Queue *) malloc(sizeof(struct Queue));
rear->next = NULL;
rear->Data = value;
front = rear;
}
else
{
temp = (struct Queue *)malloc(sizeof(struct Queue));
rear->next = temp;
temp->Data = data;
temp->next = NULL;
rear = temp;
}
}
void dequeue()
{
front1 = front;
if (front1 == NULL)
{
printf(" Error: Trying to display elements from empty queue");
return;
}
else
if (front1->next != NULL)
{
printf("Dequed value : %d", front1->Data);
front1 = front1->next;
free(front);
front = front1;
}
else
{
printf("Dequed value : %d", front->Data);
free(front);
front = NULL;
rear = NULL;
}
}
void display()
{
struct Node *var = rear;
if(var == NULL)
printf("\nQueue is Empty");
else
{
while(var!=NULL)
{
printf("%d",var->Data);
var=var->next;
}
}
}
Learn By Coding 