Sorting on multiple keys
Sorting on multiple keys
The sorting algorithm may be applied on multiple keys such that if first field contains duplicate values, then sorting is done on a secondary field and so on. However, if the first field contains unique values, then sorting is not applied on secondary field. Say for example:
The input for the combination {studentname, feeamt}
{ (xyz,3000), (abc,1000), (xyz, 1000), (abc,3000)}; will result in the following output:
{ (abc,1000), (abc,3000), (xyz,1000), (xyz,3000) }.
Program to implement sorting on student names entered by the user followed by feeamt, such that wherever name is same, sorting is applicable on feeamt field is given below:
/*Sorting on multiple keys*/
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define MAX 5
struct student
{char name[25];
int feeamt;
};
void sort_multiplekeys(struct student[]);
void main()
{
struct student s[MAX];
int i;
clrscr();
for(i=0;i<MAX;i++)
{printf(“\nEnter name?”);
scanf(“%s”,s[i].name);
printf(“Enter fee amount?”);
scanf(“%d”,&s[i].feeamt);
}
sort_multiplekeys(s);
printf(“\nOutput sorted on name followed by feeamt:\n\n”);
for(i=0;i<MAX;i++)
{printf(“\nName = %s”,s[i].name);
printf(“\nFeeamt = %d”,s[i].feeamt);
}
}
void sort_multiplekeys(struct student s[])
{
int i,j;
char temp[25];
float x;
clrscr();
/*loop to arrange names in ascending order*/
for(i=0;i<MAX-1;i++)
for(j=i+1;j<MAX;j++)
{if(strcmp(s[i].name,s[j].name)>0)
{
/*swapping names*/
strcpy(temp,s[i].name);
strcpy(s[i].name,s[j].name);
strcpy(s[j].name,temp);
/*swapping feeamt*/
x=s[i].feeamt;
s[i].feeamt = s[j].feeamt;
s[j].feeamt = x;
}
}
/*loop to arrange second field-feeamt in ascending order*/
for(i=0;i<MAX-1;i++)
for(j=i+1;j<MAX;j++)
{if(strcmp(s[i].name,s[j].name)==0)
{if(s[i].feeamt>s[j].feeamt)
{
/*swapping feeamt*/
x=s[i].feeamt;
s[i].feeamt=s[j].feeamt;
s[j].feeamt=x;
}
}
}
}
Sorting – Address Calculation Sort (Hashing)
Sorting – Address Calculation Sort (Hashing)
- In this method a function f is applied to each key.
- The result of this function determines into which of the several subfiles the record is to be placed.
- The function should have the property that: if x <= y , f (x) <= f (y), Such a function is called order preserving.
- An item is placed into a subfile in correct sequence by placing sorting method – simple insertion is often used.
Example:
25 57 48 37 12 92 86 33
Let us create 10 subfiles. Initially each of these subfiles is empty. An array of pointer f(10) is declared, where f(i) refers to the first element in the file, whose first digit is i. The number is passed to hash function, which returns its last digit (ten’s place digit), which is placed at that position only, in the array of pointers.
num= 25 – f(25) gives 2
57 – f(57) gives 5
48 – f(48) gives 4
37 – f(37) gives 3
12 – f(12) gives 1
92 – f(92) gives 9
86 – f(86) gives 8
33 – f(33) gives 3 which is repeated.
Thus it is inserted in 3rd subfile (4th) only, but must be checked with the existing elements for its proper position in this subfile.
Arrangement of nodes in subfiles
Efficiency: If all the elements (n) are uniformly distributed over m subfiles then n/m is approximately 1, time of the sort is near O(n).
On the other hand if maximum elements accommodate in one or two subfiles, then n/m is much larger significant work is required to insert its proper subfile at its proper position and efficiency is O(n2).
Program to implement Address Calculation Sort:
/*Address Calculation Sort*/
/*It uses a hash function that can sort only 2 digit nos.*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 5
struct list
{int info;
struct list *next;
}*node[10]={NULL};
struct list *create()
{
struct list *temp=(struct list *)malloc(sizeof(struct list));
if(temp==NULL)
{printf(“\nMemory Allocation Error!”);
exit(1);
}
return temp;
}
struct list *makenode(int num)
{
struct list *temp;
temp=create();
temp->info=num;
temp->next=NULL;
return temp;
}
struct list *insert(struct list *s,int num)
{
struct list *ptr,*temp;
ptr=s;
temp=makenode(num);
if(s==NULL)
s=temp;
else
{
/*code for placing new node at appropriate
position in the subfile*/
while((ptr->next->info<=num) && (ptr->next!=NULL))
{ptr=ptr->next;
}
if(temp->info<ptr->info)
{temp->next=ptr;
s=temp;
}
else
{temp->next=ptr->next;
ptr->next=temp;
}
}
return s;
}
/*A hash function that operates upon two digit
numbers only*/
int hashfun(int n)
{return (n/10);
}
void addr_calc(int arr[],int size)
{
int i,j=0,pos;
for(i=0;i<size;i++)
{pos=hashfun(arr[i]);
node[pos]=insert(node[pos],arr[i]);
}
for(i=0;i<10;i++)
{while(node[i]!=NULL)
{arr[j++]=node[i]->info;
node[i]=node[i]->next;
}
}
printf(“\nSorted output is: “);
for(i=0;i<size;i++)
printf(“%d\t”,arr[i]);
getch();
}
void main()
{
int arr[MAX],i,n;
clrscr();
printf(“Enter total numbers to sort?”);
scanf(“%d”,&n);
printf(“Enter numbers?”);
for(i=0;i<n;i++)
scanf(“%d”,&arr[i]);
addr_calc(arr,n);
}
Sorting – Quick Sort (Partition Exchange Sort)
Sorting – Quick Sort (Partition Exchange Sort)
Suppose x be an array, n is the number of elements. Choose an element from a specific position within the array. Array x is partitioned so that y is placed into position j, and the following conditions hold:
1) Each of the elements in position 0 through (j-1) is less than or equal to y.
2) Each of the elements in position (j+1) through (n-1) is greater than or equal to y.
Example:
Let key element = lb = arr[0] = 14
Now i will move forward until arr[i] becomes greater than key value. Finally i is positioned at 15.
Similarly j shifts backward until arr[j] becomes lower than key value. Finally j is positioned at 11.
Now, swap(arr[i],arr[j]);
Now the same set of routines are again called with new values of i and j i.e. lb and ub.
Now i is positioned at 15, since 8 is less than 14. Similarly j is positioned at 8.
Now i<=j condition is false i.e. upper bound is lower than lower bound which must be higher.
Now swap(arr[j],key);
Then all smaller values (for key) are aligned to left and greater values to right. Now partition it in two parts (8,7,3,11) and (15,16,25). Repeat the same process again. Finally combine all segments – (left, key, right) to obtain sorted array.
Program to implement Quicksort:
#include <stdio.h>
#include <conio.h>
#define MAX 10
void quicksort(int arr[],int lb,int ub);
int partition(int arr[],int lb,int ub);
void main()
{
int arr[MAX],i,n,keyelement,lb,ub;
clrscr();
printf(“\nEnter total number of elements?”);
scanf(“%d”,&n);
printf(“\nEnter elements?”);
for(i=0;i<n;i++)
{scanf(“%d”,&arr[i]);
}
keyelement = arr[0];
lb=0;
ub=(n-1);
quicksort(arr,lb,ub);
printf(“\nSorted Array is: “);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}
void quicksort(int arr[],int lb,int ub)
{
int j;
if(lb>=ub)
return;
j=partition(arr,lb,ub);
quicksort(arr,lb,j-1);
quicksort(arr,j+1,ub);
return;
}
int partition(int arr[],int lb,int ub)
{
int a,down,temp;
a=arr[lb];
down=lb;
while(lb<ub)
{while((arr[lb]<=a) && (lb<ub))
lb++;
while(arr[ub]>a)
ub–;
if(lb<ub)
{temp=arr[lb];
arr[lb]=arr[ub];
arr[ub]=temp;
}
}
temp=arr[ub];
arr[ub]=a;
arr[down]=temp;
return ub;
}
Sorting – Merge Sort
Sorting – Merge Sort
Merging:- Merging is the process of combining two or more sorted files into a third sorted file. An example of a routine that accepts two sorted arrays a and b of n1 and n2 elements respectively and merges them into a third array c containing n3 (n1+n2) elements.
Steps for Merge Sort:
- Divide the file n subfiles of size 1 and merge adjacent pair of files.
- We then have approximately n/2 files of size 2.
- Repeat this process until there is only file of size n.
- An auxillary array aux, of size n is required to hold the results of merging two subarrays of x. The variable size contains the size of the subarrays being merged. Since at any time the two files being merged are both subarrays of x, lower and upper bounds are required to indicate the subfiles of x being merged. l1 and u1 represents the lower and upper bounds of the first file and l2 and u2 represents the lower and upper bounds of the second file respectively. i and j are used to reference elements of the source files being merged and k indexes the destination file aux.
Program to merge two sorted arrays to result in another sorted array:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 10
int checksort(int arr[],int n)
{
int i,j,temp,flag=1;
for(i=0;i<n-1;i++)
{for(j=i+1;j<n;j++)
{if(arr[i]>arr[j])
{flag=0;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
return flag;
}
void mergearr(int a[], int b[], int c[], int n1,int n2,int n3)
{
int al,bl,cl,ah,bh,ch,i;/*l for low, h for high*/
ah=n1-1;
bh=n2-1;
ch=n3-1;
if(n1+n2!=n3)
{printf(“\nArray bounds not proper!”);
exit(1);
}
al=0;
bl=0;
for(i=0;al<=ah && bl<=bh;i++)
{if(a[al]<b[bl])
c[i]=a[al++];
else
c[i]=b[bl++];
}
while(al<=ah)
c[i++]=a[al++];
while(bl<=bh)
c[i++]=b[bl++];
}
void main()
{
int a1[MAX],a2[MAX],a3[MAX],n1,n2,n3,i;
clrscr();
printf(“\nEnter the size of first array?”);
scanf(“%d”,&n1);
printf(“\nEnter the size of second array?”);
scanf(“%d”,&n2);
printf(“\nEnter elements of first array?”);
for(i=0;i<n1;i++)
{scanf(“%d”,&a1[i]);
}
printf(“\nEnter elements of second array?”);
for(i=0;i<n2;i++)
{scanf(“%d”,&a2[i]);
}
n3=n1+n2;
if(!checksort(a1,n1))
{printf(“\nMerging operates on sorted array.”);
printf(“\nFirst Array you entered is not sorted.”);
printf(“\nSorting array 1….”);
printf(“\nPress any key to continue!”);
getch();
}
if(!checksort(a2,n2))
{printf(“\n\nMerging operates on sorted array.”);
printf(“\nSecond Array you entered is not sorted.”);
printf(“\nSorting array 2….”);
printf(“\nPress any key to continue!”);
getch();
}
printf(“\n\nNow Merging both the sorted arrays…\n”);
mergearr(a1,a2,a3,n1,n2,n3);
printf(“\nMerged sorted array is:”);
for(i=0;i<n3;i++)
printf(“%d\t”,a3[i]);
getch();
}
Program to implement Merge sort:
#include <stdio.h>
#include <conio.h>
#define MAX 10
void mergesort(int x[], int n)
{
int aux[MAX],i,j,k,l1,l2,u1,u2,size;
size=1;/*initially size is 1.*/
while(size<n)
{
l1=0;
k=0;/*k is the index of auxillary array.*/
while((l1+size)<n)
{l2=l1+size;
u1=l2-1;
u2=((l2+size-1)<n)?(l2+size-1):n-1;
for(i=l1,j=l2;i<=u1 && j<=u2;k++)
{if(x[i]<=x[j])
aux[k]=x[i++];
else
aux[k]=x[j++];
}
/*Remaining elements of first array*/
for(;i<=u1;k++)
aux[k]=x[i++];
/*Remaining elements of second array*/
for(;j<=u2;k++)
aux[k]=x[j++];
/*Advance l1 to the start of the next pair of files.*/
l1=u2+1;
}
for(i=l1;k<n;i++)
aux[k++]=x[i];
for(i=0;i<n;i++)
x[i]=aux[i];
size *= 2;
}
}
void main()
{
int array[MAX],i;
clrscr();
printf(“Enter array elements?”);
for(i=0;i<MAX;i++)
scanf(“%d”,&array[i]);
mergesort(array,MAX);
printf(“Sorted elements are: “);
for(i=0;i<MAX;i++)
printf(“%d\t”,array[i]);
getch();
}
Sorting – Radix Sort
Sorting – Radix Sort
Radix Sort sorts the number in scans equal to the number of digits of maximum number.
eg. 45, 3, 235, 89, 150, then maximum scans = 3.
Thus radix sort operates three times.
Radix sort uses 10 queues to sort the given numbers.
- Begin with least significant digit, ending with most significant digit.
- Fetch a number from the array and place it in one of the queues depending upon its value say 2 means it is placed in node[2]. If a number already exists at that position than the correct ordered position for the new number is determined.
- Retrieve these elements from the queue from 0 to n back into array.
- Repeat this process till most significant bit.
- Display the array which is finally sorted.
Program to implement Radix Sort:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 5
struct queue
{int info;
struct queue *next;
}*node[10]={NULL};
struct queue *front=NULL,*rear=NULL;
struct queue *create()
{
struct queue *temp=(struct queue*)malloc(sizeof(struct queue));
if(temp==NULL)
{printf(“\nMemory Allocation Error!”);
exit(1);
}
return temp;
}
struct queue *makenode(int num)
{
struct queue *temp=create();
temp->info=num;
temp->next=NULL;
return temp;
}
struct queue *insert(struct queue *s,int num)
{
struct queue *ptr=s;
struct queue *temp=makenode(num);
if(s==NULL)
s=temp;
else
{while((ptr->next->info<=num) && (ptr->next!=NULL))
ptr=ptr->next;
if(temp->info<ptr->info)
{temp->next=ptr;
s=temp;
}
else
{temp->next=ptr->next;
ptr->next=temp;
}
}
return s;
}
int digits_count(int num)
{
int rmdr,quot,ct=0;
quot=num/10;
rmdr=num%10;
ct++;
while(quot!=0)
{
num=quot;
quot=num/10;
rmdr=num%10;
ct++;
}
return ct;
}
int max_element(int arr[],int n)
{
int max,i;
max=arr[0];
for(i=1;i<n;i++)
{if(arr[i]>max)
max=arr[i];
}
return max;
}
int return_ith_digit(int num,int pos)
{
int i, ndigits, rmdr;
ndigits = digits_count(num);
if(pos>ndigits)
return 0;
rmdr=num%10;
for(i=0;i<pos;i++)
{
num=num/10;
rmdr=num%10;
}
return rmdr;
}
void radixsort(int arr[], int n)
{
int i,j,digits,max,y;
int k=0,p=0;
max=max_element(arr,n);
digits = digits_count(max);
for(i=0;i<digits;i++)
{
for(j=0;j<n;j++)
{
y=return_ith_digit(arr[j],i);
node[y]=insert(node[y],arr[j]);
}
for(p=0;p<10;p++)
{
while(node[p]!=NULL)
{
arr[k++]=node[p]->info;
printf(“%d->”,node[p]->info);
node[p]=node[p]->next;
}
}
printf(“\b\b “);
}
}
void main()
{
int arr[MAX],i,n;
clrscr();
printf(“\nEnter total number of elements?”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
radixsort(arr,n);
getch();
}
Sorting – Straight Selection Sort
Sorting – Straight Selection Sort
- Begin from the first element, taking i=0 to n-1.
- Find the minimum number in the first scan.
- Interchange ith element with the minimum number.
- Start searching minimum element again from i+1 to n.
- The number of scans is equal to the number of elements.
- Stop scan when the last element remains to be replaced with min.
- Display the output which is now sorted.
Though this method requires only half the number of comparisons required by simple selection sort, but the time complexity is still O(n2).
Program to implement Straight Selection Sort:
#include <stdio.h>
#include <conio.h>
#define MAX 5
void straightselectionsort(int arr[],int n)
{
int i,j,k;
float min,temp;
for(i=0;i<n-1;i++)
{
min=arr[i];
k=i;
for(j=i+1;j<n;j++)
{if(arr[j]<min)
{min=arr[j];
k=j;
}
}
arr[k]=arr[i];
arr[i]=min;
}
}
void main()
{
int arr[MAX];
int i,n;
clrscr();
printf(“\nEnter the value of n?”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{printf(“\nEnter the value of x?”);
scanf(“%d”,&arr[i]);
}
printf(“\n\nArray you have entered is:\n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
straightselectionsort(arr,n);
printf(“\n\nSorted Array is: \n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}
Sorting – General Selection Sort
Sorting – General Selection Sort
Steps:
- Fetch the numbers to be sorted in an array.
- Push these numbers one by one to a priority queue. (Any priority-lower or higher may be considered).
Case 1: Lower values with high priority for ascending order.
Case 2: Higher values with high priority for descending order.
3. Pop all the elements from the priority queue to the array one by one.
4. Display the array, which is now in sorted order.
Example: Let us consider that lower values are given high priority.
Program to implement General Selection Sort:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 5
struct queue
{
int arr[MAX];
int front,rear;
};
void push(struct queue *q,int x)
{int f,r,j;
if(q->front==-1)
{
q->arr[0]=x;
q->front=q->rear=0;
return;
}
f=q->front;
r=q->rear;
if(q->rear==MAX-1)
{
printf(“\nQueue full! Overflow.”);
exit(1);
}
while(f<=r && q->arr[f]<x)
{f++;
}
for(j=r;j>=f;j–)
q->arr[j+1]=q->arr[j];
q->arr[f]=x;
q->rear++;
}
int pop(struct queue *q)
{
if(q->front==-1)
{printf(“\nQueue empty! Underflow.”);
exit(1);
}
return(q->arr[(q->front)++]);
}
void display(struct queue *q)
{
int f,r;
if(q->front == -1)
{
printf(“\nQueue empty…!”);
exit(1);
}
f=q->front;
r=q->rear;
while(f!=r)
printf(“%d\t”,q->arr[f++]);
printf(“%d\t”,q->arr[f]);
}
void main()
{
int arr[MAX], i;
struct queue q;
q.front=q.rear=-1;
clrscr();
for(i=0;i<MAX;i++)
{
printf(“\nEnter array elements?”);
scanf(“%d”,&arr[i]);
}
for(i=0;i<MAX;i++)
{push(&q,arr[i]);
}
printf(“\n\nDisplaying queue elements…!\n\t”);
display(&q);
printf(“\n\nSorted Array is:”);
for(i=0;i<MAX;i++)
{
arr[i]=pop(&q);
printf(“%d\t”,arr[i]);
}
getch();
}
Sorting – Insertion sort
Insertion Sort
Sorts a set of records by comparing the next record with all the previous elements. Compare next element with previous. If next element is smaller than previous element, then swap both the elements. i.e.
if(arr[j]>arr[i])
swap(arr[j],arr[i);
Example:
The loop may be written as follows:
for I = 2 to n
for j = I-1 to >=1
if(arr[I] < arr[j])
swap(arr[i],arr[j]);
Insertion sort is considered best if most of the data is in sorted order.
Efficiency:
I j number of times
2 1 to 1 1
3 2 to 1 2
4 3 to 1 3
– —— –
– —— –
– —— –
(n-1) (n-2) to 1 (n-2)
n (n-1) to 1 (n-1)
Sum of terms: 1+2+3+…………..+(n-2)+(n-1)
=(n-1)(n-1+1)/2
=n(n-1)/2
=n2/2-n/2
=0.5n2-0.5n
=O(n2)
Note:
An insertion sort may be viewed as a general selection sort in which the priority queue is implemented as an ordered array. We have to only insert elements in priority queue. Once the elements have been inserted, they are already sorted, so that no selection is necessary.
Shell sort is an improvised form of insertion sort, as for k=1, most of the data which is processed is already sorted.
Insertion Sort Program:
#include <stdio.h>
#include <conio.h>
#define MAX 10
void main()
{
int arr[MAX];
int i,j,temp,num,ct;
clrscr();
for(i=0;i<MAX;i++)
{printf(“Enter array elements?”);
scanf(“%d”,&arr[i]);
}
for(i=1;i<MAX;i++)
{
num=arr[i];
ct=i;
for(j=i-1;j>=0;j–)
{if(num<arr[j])
{
temp=arr[ct];
arr[ct]=arr[j];
arr[j]=temp;
ct=j;
}
}
}
printf(“Sorted array using insertion sort is:\n”);
for(i=0;i<MAX;i++)
printf(“%d\t”,arr[i]);
getch();
}
Sorting – Bubble sort
Bubble sort:
Two consecutive elements are compared. It sorts the elements in right to left fashion. Thus, (n-i) comparisons are made.
Example:
Frequency:
i j number of times
———————————————————————————————
1 1 to n-i n-1
2 1 to n-i n-2
3 1 to n-i n-3
– – –
– – –
– – –
n-1 1 to n-(n-1) 1
Thus, 1+2+……………+(n-3)+(n-2)+(n-1)
which is sum of (n-1) terms.
=(n-1)(n-1+1)/2
=(n-1)n/2
=n2/2 – n/2
=0.5n2-0.5n
Thus, efficiency in Big(O) Notation is O(n2).
i) Best Case: Data is already in sorted form. Thus no interchange occurs.
Number of comparisons may be reduced as follows:
for i=1, j=n-i ie. (n-1)
Frequency is (n-1), which is achieved if we quit after scan, when no interchange occurs.
Hence, efficiency is O(n).
ii) Worst Case: Data is in reverse order. Each value gets interchanged. Hence number of comparisons will be same as calculated above. i.e.
Efficiency = O(n2)
iii) Average Case:
(Best Case + Worst Case)/2
= ((n-1) + n2)/2
=(n/2)-(1/2)+(n2/2)
Efficiency = O(n2)
Bubble sort program with n2 frequency and an efficiency of O(n2)
#include <stdio.h>
#include <conio.h>
#define n 10
void main()
{
int arr[n], i,j,temp;
clrscr();
printf(“\nInitializing array…!”);
for(i=0;i<n;i++)
{
printf(“\nEnter elements?”);
scanf(“%d”,&arr[i]);
}
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
printf(“\nSorted array using Bubble sort is:\n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}
Bubble sort program with best efficiency O(n) and frequency (n-1)
#include <stdio.h>
#include <conio.h>
#define n 5
void main()
{
int arr[n], i,j,temp,sort=0;
/*sort=0 for false and sort=1 for true i.e. sorted array*/
clrscr();
printf(“\nInitializing array…!”);
for(i=0;i<n;i++)
{
printf(“\nEnter elements?”);
scanf(“%d”,&arr[i]);
}
for(i=0;i<n-1 && sort!=1;i++)
{
for(j=0;j<n-i-1;j++)
{
sort=1;
if(arr[j]>arr[j+1])
{
sort=0;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
printf(“\nSorted array using Bubble sort is:\n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}
Sorting – Shell sort
Shell Sort:
Shell sort is quite similar to that of insertion sort with the only difference that in shell sort, higher values of k are considered. Whereas insertion sort assumes k to be 1. If k=4, then every 4th element is compared, if it is 3 then every 3rd element is compared. Thus k=m means every mth element gets compared with each other and is swapped.
The value of k is decremented after each scan. The file is sorted, when k becomes 1 and swapping is performed for k = 1. The difference in original and decremented value(i.e. difference in k) may be generated using a hash function, which returns the number of decrements in k. say k=4, then k=2 and finally k=1. k=3 is skipped. or (k=8, k=4, k=2, k=1) or (k=4, k=3, k=2, k=1).
If k is taken as 1 only, then it is no more shell sort, it becomes insertion sort.
Example:
/*Program to implement Shell Sort*/
#include <stdio.h>
#include <conio.h>
#define MAX 5
void shellsort(int x[],int n,int incrmnts[],int numinc)
{
int incr,j,k,span,y;
for(incr=0;incr<numinc;incr++)
{
span=incrmnts[incr];
for(j=span;j<n;j++)
{
y=x[j];
for(k=j-span;k>=0 && y<x[k]; k-=span)
x[k+span]=x[k];
x[k+span]=y;
}
}
}
/*
A hash function may be defined as follows:
Let n be the size of the array (total number of elements).
Then begin from (n-3) upto 1.
Example: Let there are 8 elements, then n=8
increments array will hold 5,3,1 for (n-3), (n-5), (n-7) respectively.
and ct=3, where ct is numinc.
*/
int hash(int arr[],int n)
{
int i,j=0,ct=0;
for(i=3;(n-i)>0;i+=2)
{
arr[j++]=n-i;
ct++;
}
if(arr[j-1]!=1)
{arr[j]=1;
ct++;
}
return ct;
}
void main()
{
int arr[MAX],i,incrmnts[MAX], total_incr;
for(i=0;i<MAX;i++)
{
incrmnts[i]=0;
printf(“Enter value?”);
scanf(“%d”,&arr[i]);
}
total_incr = hash(incrmnts,MAX);
shellsort(arr,MAX,incrmnts,total_incr);
printf(“Sorted array is: “);
for(i=0;i<MAX;i++)
{
printf(“%d\t”,arr[i]);
}
getch();
}
