## Sorting

1.   Internal sort

Internal Sorting

Internal Sorting takes place in the main memory of a computer. The internal sorting methods are applied to small collection of data. It means that, the entire collection of data to be sorted in small enough that the sorting can take place within main memory.

We will study the following methods of internal sorting.

Insertion Sort

In this sorting we can read the given elements from 1 to n, inserting each element into its proper position. For example, the card player arranging the cards dealt to him. The player picks up the card and inserts them into the proper position. At every step, we insert the item into its proper place.

This sorting algorithm is frequently used when n is small. The insertion sort algorithm scans A from A[l] to A[N], inserting each element A[K] into its proper position in the previously sorted subarray A[l], A[2], . . . , A[K-1]. That is:

Pass 1. A[l] by itself is trivially sorted.

Pass 2. A[2] is inserted either before or after A[l] so that: A[l], A[2] is sorted.

Pass 3. A[3] is inserted into its proper place in A[l], A[2], that is, before A[l],

between A[l] and A[2], or after A[2], so that: A[l], A[2], A[3] is sorted.

Pass 4. A[4] is inserted into its proper place in A[l], A[2], A[3] so that:

A[l], A[2], A[3], A[4] is sorted.

………………………………………………………

Pass N. A[N] is inserted into its proper place in A[l], A[2], . . . , A[N - 1] so

that: A[l], A[2], . . . ,A[N] is sorted.

`#include "stdio.h"`

`void main( )`
`{`
`               int arr[5] = { 25, 17, 31, 13, 2 } ;`
`               int i, j, k, temp ;`

`               printf ( "Insertion sort.\n" ) ;`
`               printf ( "\nArray before sorting:\n") ;`

`               for ( i = 0 ; i <= 4 ; i++ )`
`                               printf ( "%d\t", arr[i] ) ;`

`               for ( i = 1 ; i <= 4 ; i++ )`
`               {`
`                               for ( j = 0 ; j < i ; j++ )`
`                               {`
`                                              if ( arr[j] > arr[i] )`
`                                              {`
`                                                             temp = arr[j] ;`
`                                                             arr[j] = arr[i] ;`

`                                                             for ( k = i ; k > j ; k-- )`
`                                                                            arr[k] = arr[k - 1] ;`

`                                                             arr[k + 1] = temp ;`
`                                              }`
`                               }`
`               }`

`               printf ( "\n\nArray after sorting:\n") ;`

`               for ( i = 0 ; i <= 4 ; i++ )`
`                               printf ( "%d\t", arr[i] ) ;`

`}`

Selection Sort

`#include "stdio.h"`

`void main( )`
`{`
`               int arr[5] = { 25, 17, 31, 13, 2 } ;`
`               int i, j, temp ;`
`               for ( i = 0 ; i <= 3 ; i++ )`
`               {`
`                               for ( j = i + 1 ; j <= 4 ; j++ )`
`                               {`
`                                              if ( arr[i] > arr[j] )`
`                                              {`
`                                                             temp = arr[i] ;`
`                                                             arr[i] = arr[j] ;`
`                                                             arr[j] = temp ;`
`                                              }`
`                               }`
`               }`

`               printf ( "\n\nArray after sorting:\n") ;`

`               for ( i = 0 ; i <= 4 ; i++ )`
`                               printf ( "%d\t", arr[i] ) ;`
`}`

Merge Sort

Combing the two lists is called as merging. For example A is a sorted list with r elements and B is a sorted list with s elements. The operation that combines the elements of A and B into a single sorted list C with n = r + s elements is called merging. After combing the two lists the elements are sorted by using the following merging algorithm Suppose one is given two sorted decks of cards. The decks are merged as in Fig.

That is, at each step, the two front cards are compared and the smaller one is placed in the combined deck. When one of the decks is empty, all of the remaining cards in the other deck are put at the end of the combined deck. Similarly, suppose we have two lines of students sorted by increasing heights, and suppose we want to merge them into a single sorted line. The new line is formed by choosing, at each step, the shorter of the two students who are at the head of their respective lines. When one of the lines has no more students, the remaining students line up at the end of the combined line.

`#include <stdio.h>`
`    void merge(int *left,int *right,int *result,int nl,int nr)`
`    {`
`        int i=0,j=0,k=0;`
`        while(nl>0 && nr>0)`
`        {`
`            if(left[i] <= right[j])`
`            {`
`                result[k] = left[i];`
`                i++;`
`                k++;`
`                nl--;`
`            }`
`            else`
`            {`
`                result[k] = right[j];`
`                j++;`
`                k++;`
`                nr--;`
`            }`
`        }`
`        while(nl>0)`
`        {`
`            result [k] = left[i];`
`            i++;`
`            k++;`
`            nl--;`
`        }`
`        while(nr>0)`
`        {`
`            result[k] = right[j];`
`            j++;`
`            k++;`
`            nr--;`
`        }`
`    }`

`    void main()`
`    {`
`        int a[] = {11,33,95};`
`        int b[] = {45,82,94};`
`        int c[6],i;`
`        printf("\n The first array is: {11,33,95}");`
`        printf("\n The second array is: {45,82,94}");`
`        merge(a,b,c,3,3);`
`        printf("\n The sorted list is: ");`

`        for(i=0;i<6;i++)`
`            printf("\n %d",c[i]);`
`    }`

Radix sort is the method that many people intuitively use or begin to use when alphabetizing a large list of names. Specifically, the list of names is first sorted according to the first letter of each name. That is, the names are arranged in 26 classes, where the first class consists of those names that begin with “A,” the second class consists of those names that begin with “B,” and so on.

During the second pass, each class is alphabetized according to the second letter of the name. And so on. If no name contains, for example, more than 12 letters, the names are alphabetized with at most 12 passes.

The radix sort is the method used by a card sorter. A card sorter contains 13 receiving pockets labeled as follows:

9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 12, R (reject)

Each pocket other than R corresponds to a row on a card in which a hole can be punched.

Decimal numbers, where the radix is 10, are punched in the obvious way and hence use only the first 10 pockets of the sorter. The sorter uses a radix reverse-digit sort on numbers. That is, suppose a card sorter is given a collection of cards where each card contains a 3-digit number punched in columns 1 to 3.

The cards are first sorted according to the units digit. On the second pass, the cards are sorted according to the tens digit. On the third and last pass, the cards are sorted according to the hundreds digit.

#include<stdio.h>
#include<conio.h>

typedef struct queue
{
int front,rear;
int item[10];
}q;

void enqueue(q* qp,int val)
{
(qp)->rear++;
(qp)->item[(qp)->rear]=val;
return;
}
int dequeue(q* qp)
{
int val;
val=(qp)->item[(qp)->front];
(qp)->front++;
return val;
}
int empty(q* qp)
{
if((qp)->rear<(qp)->front)
return 1;
return 0;
}
{
q qu[10];
int i,j,r,d=1,k;
for(i=1;i<=m;i++)
{
for(j=0;j<10;j++)
{
qu[j].rear=-1;
qu[j].front=0;
}
for(j=0;j<n;j++)
{
r=a[j]%(d*10);
r=r/d;
enqueue(&qu[r],a[j]);
}
d*=10;
k=0;
for(j=0;j<10;j++)
{
while(empty(&qu[j])==0)
a[k++]=dequeue(&qu[j]);
}
}
return;
}

void main()
{
int a[10],i,no,max=a[0],count=0;
clrscr();
printf(“\n\n Enter no of elements..”);
scanf(“%d”,&no);
printf(“\n\n Enter the elements..”);
for(i=0;i<no;i++)
{
scanf(“%d”,&a[i]);
if(a[i]>max)
max=a[i];
}
while(max>0)
{
max=max/10;
count++;
}
printf(“\n\n The sorted elements are..”);
for(i=0;i<no;i++)
printf(“%d\t”,a[i]);
getch();
}

Quick Sort

This is the most widely used internal sorting algorithm. It is based on divide-and-conquer type i.e. Divide the problem into sub-problems, until solved sub problems are found.

Suppose A is the following list of 12 numbers:

(44) 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66

The quick sort algorithm finds the final position of one of the numbers; in this illustration, we use the first number, 44. This is accomplished as follows. Beginning with the last number, 66, scan the list from right to left, comparing each number with 44 and stopping at the first number less than 44.

The number is 22. Interchange 44 and 22 to obtain the list (22) 33, 11, 55, 77, 90, 40, 60, 99, (44) 88, 66

(Observe that the numbers 88 and 66 to the right of 44 are each greater than 44.)

Beginning with 22, next scan the list in the opposite direction, from left to right, comparing each number with 44 and stopping at the first number greater than 44. The number is 55. Interchange 44 and 55 to obtain the list

22, 33, 11, (44) 77, 90, 40, 60, 99, (55), 88, 66 .

(Observe that the numbers 22, 33 and 11 to the left of 44 are each less than 44.)

Beginning this time with 55, now scan the list in the original direction, from right to left, until meeting the first number less than 44. It is 40. Interchange 44 and 40 to obtain the list 22, 33, 11, (40) 77, 90, (44) 60, 99, 55, 88, 66*

(Again, the numbers to the right of 44 are each greater than 44.)

Beginning with 40, scan the list from left to right. The first number greater than 44 is 77. Interchange 44 and 77 to obtain the list

22, 33, 11, 40, (44) 90, (77) 60, 99, 55, 88, 66

(Again, the numbers to the left of 44 are each less than 44.)

Beginning with 77, scan the list from right to left seeking a number less than 44. We do not meet such a number before meeting 44. This means all numbers have been scanned and compared with 44. Furthermore, all numbers less than 44 now form the sublist of numbers to the left of 44, and all numbers greater than 44 now form the sublist of numbers to the right of 44, as shown below:

22, 33, 11, 40, (44) 90, 77, 60, 99, 55, 88, 66

___________          ____________________

First sublist                        Second sublist

Thus 44 is correctly placed in its final position, and the task of sorting the original list A has now been reduced to the task of sorting each of the above sublists.

The above reduction step is repeated with each sublist containing 2 or more elements.

`#include "stdio.h"`

`int split ( int*, int, int ) ;`

`void main( )`
`{`
`               int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;`
`               int i ;`

`               void quicksort ( int *, int, int ) ;`

`               quicksort ( arr, 0, 9 ) ;`

`               printf ( "\nArray after sorting:\n") ;`

`               for ( i = 0 ; i <= 9 ; i++ )`
`                               printf ( "%d\t", arr[i] ) ;`

`}`

`void quicksort ( int a[ ], int lower, int upper )`
`{`
`               int i ;`
`               if ( upper > lower )`
`               {`
`                               i = split ( a, lower, upper ) ;`
`                               quicksort ( a, lower, i - 1 ) ;`
`                               quicksort ( a, i + 1, upper ) ;`
`               }`
`}`

`int split ( int a[ ], int lower, int upper )`
`{`
`               int i, p, q, t ;`

`               p = lower + 1 ;`
`               q = upper ;`
`               i = a[lower] ;`

`               while ( q >= p )`
`               {`
`                               while ( a[p] < i )`
`                                              p++ ;`

`                               while ( a[q] > i )`
`                                              q-- ;`

`                               if ( q > p )`
`                               {`
`                                              t = a[p] ;`
`                                              a[p] = a[q] ;`
`                                              a[q] = t ;`
`                               }`
`               }`

`               t = a[lower] ;`
`               a[lower] = a[q] ;`
`               a[q] = t ;`

`               return q ;`
`}`

Heap Sort

A heap is a complete binary tree, in which each node satisfies the heap condition.

Heap condition

The key of each node is greater than or equal to the key in its children. Thus the root node will have the largest key value.

MaxHeap

Suppose H is a complete binary tree with n elements. Then H is called a heap or maxheap, if the value at N is greater than or equal to the value at any of the children of N.

MinHeap

The value at N is less than or equal to the value at any of the children of N.

The operations on a heap

(i) New node is inserted into a Heap

(ii) Deleting the Root of a Heap

Bubble Sort

In this sorting algorithm, multiple swapping take place in one iteration. Smaller elements move or ‘bubble’ up to the top of the list. In this method ,we compare the adjacent members of the list to be sorted , if the item on top is greater than the item immediately below it, they are swapped.

`#include "stdio.h"`
`#include "conio.h"`

`void main( )`
`{`
`               int arr[5] = { 25, 17, 31, 13, 2 } ;`
`               int i, j, temp ;`
`               for ( i = 0 ; i <= 3 ; i++ )`
`               {`
`                               for ( j = 0 ; j <= 3 - i ; j++ )`
`                               {`
`                                              if ( arr[j] > arr[j + 1] )`
`                                              {`
`                                                             temp = arr[j] ;`
`                                                             arr[j] = arr[j + 1] ;`
`                                                             arr[j + 1] = temp ;`
`                                              }`
`                               }`
`               }`

`               printf ( "\n\nArray after sorting:\n") ;`

`               for ( i = 0 ; i <= 4 ; i++ )`
`                               printf ( "%d\t", arr[i] ) ;`
`}`

2. External sort

Sorting with Disks

We will first illustrate merge sort using disks. The following example illustrate the concept of sorting with disks

The file F containing 600 records is to be sorted. The main memory is capable of sorting of 1000 records at a time. The input file F is stored on one disk and we have in addition another scratch disk. The block length of the input file is 500 records.

We see that the file could be treated as 6 sets of 1000 records each. Each set is sorted and stored on the scratch disk as a run. These 5 runs will then be merged as follows.

Allocate 3 blocks of memory each capable of holding 500 records. Two of these buffers B1 and B2 will be treated as input buffers and the third B3 as the output buffer. We have now the following

1) 6 run R1, R2, R3, R4, R5, R6 on the scratch disk.

2) 3 buffers B1,B2 and B3

 Read 500 records from R1 into B1.

 Read 500 records from R2 into B2.

 Merge B1 and B2 and write into B3.

 When B3 is full- write it out to the disk as run R11.

 Similarly merge R3 and R4 to get run R12.

 Merge R5 and R6 to get run R13.

Thus, from 6 runs of size 1000 each, we have now 3 runs of size 2000 each.

The steps are repeated for steps R11 and R12 to get a run of size 4000.

This run is merged with R13 to get a single sorted run of size 6000

Sorting with Tapes

Sorting with tapes is essentially similar to the merge sort used for sorting with disks. The differences arise due to the sequential access restriction of tapes.

This makes the selection time prior to data transmission an important factor, unlike seek time and latency time. Thus is sorting with tapes we will be more concerned with arrangement of blocks and runs on the tape so s to reduce the selection or across time.

Example

A file of 6000 records is to be sorted. It is stored on a tape and the block length is 500. The main memory can sort unto a 1000 records at a time. We have in addition 4 search tapes T1-T4.

Inserting

How to insert or add an element in the array at specific or desired posting by using c programming language.
#include<stdio.h>

int main(){

int a[50],size,num,i,pos,temp;

printf(“\nEnter size of the array: “);

scanf(“%d”,&size);

printf(“\nEnter %d elements in to the array: “,size);

for(i=0;iscanf(“%d”,&a[i]);

printf(“\nEnter position and number to insert: “);

scanf(“%d %d”,&pos,&num);

i=0;

while(i!=pos-1)

i++;

temp=size++;

while(i{

a[temp]=a[temp-1];

temp–;

}

a[i]=num;

for(i=0;iprintf(” %d”,a[i]);

return 0;

}

Deletion process in arrays

Data structure’s C program to delete an element from the array. Enter the array size and then it’s elements. After this enter the location of the element you want to delete and the item will be deleted. Below is the code of the above program

#include<stdio.h>
#include<conio.h>

#define SIZE 50
int main()
{
int arr[SIZE];
int i,num,index;
printf(“Enter total number of element in array : “);
scanf(“%d”, &num);
for(i=0; i<num; i++)
{
printf(“Enter %d element : “,i+1);
scanf(“%d”,&arr[i]);
}
printf(“\nEnter element number which you want to delete : “);
scanf(“%d”, &index);
if(index >= num+1)
else
{
for(i=index-1; i<num-1; i++)
arr[i]=arr[i+1];
printf(“\n– After deletion new array list –\n\n”);
for(i=0; i<num-1; i++)
printf(“\t%d\n”,arr[i]);
}
getch();
return 0;
}

Name (required)

Email (required)

Feedback