SORTING

4.1 PRELIMINARIES

A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms that require sorted lists to work correctly and for producing human - readable input.

Sorting algorithms are often classified by :

* Computational complexity (worst, average and best case) in terms of the size of the list (N).

For typical sorting algorithms good behaviour is O(NlogN) and worst case behaviour is O(N2)

and the average case behaviour is O(N).

* Memory Utilization

* Stability - Maintaining relative order of records with equal keys.

* No. of comparisions.

* Methods applied like Insertion, exchange, selection, merging etc.

Sorting is a process of linear ordering of list of objects.

Sorting techniques are categorized into

Internal Sorting

External Sorting

Internal Sorting takes place in the main memory of a computer.

eg : - Bubble sort, Insertion sort, Shell sort, Quick sort, Heap sort, etc.

External Sorting, takes place in the secondary memory of a computer, Since the number of objects to be sorted is too large to fit in main memory.

eg : - Merge Sort, Multiway Merge, Polyphase merge.

4.2 INSERTION SORT

Insertion sorts works by taking elements from the list one by one and inserting them in their current position into a new sorted list. Insertion sort consists of N - 1 passes, where N is the number of elements to be sorted. The ith pass of insertion sort will insert the ith element A[i] into its rightful place among A[1], A[2] --- A[i - 1]. After doing this insertion the records occupying A[1]....A[i] are in sorted order.

4




Data Structures 4.1


INSERTION SORT PROCEDURE

void Insertion Sort (int A[ ], int N)

{

int i, j, Temp;

for (i = 1; i < N; i++)

{

Temp = A[i];

for (j = i; j>0; j --)

if (A [j - 1] > Temp)

A[j] = A[ j - 1];

A[j] = Temp;

}

}

Example

Consider an unsorted array as follows,

20 10 60 40 30 15

PASSES OF INSERTION SORT

ORIGINAL 20 10 60 40 30 15 POSITIONS MOVED

After i = 1 10 20 60 40 30 15 1

After i = 2 10 20 60 40 30 15 0

After i = 3 10 20 40 60 30 15 1

After i = 4 10 20 30 40 60 15 2

After i = 5 10 15 20 30 40 60 4

Sorted Array 10 15 20 30 40 60

ANALYSIS OF INSERTION SORT

WORST CASE ANALYSIS - O(N2)

BEST CASE ANALYSIS - O(N)

AVERAGE CASE ANALYSIS - O(N2)

LIMITATIONS OF INSERTION SORT :

* It is relatively efficient for small lists and mostly - sorted lists.

* It is expensive because of shifting all following elements by one.




Data Structures 4.2


4.3 SHELL SORT

Shell sort was invented by Donald Shell. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. It works by arranging the data sequence in a two - dimensional array and then sorting the columns of the array using insertion sort.

In shell short the whole array is first fragmented into K segments, where K is preferably a prime number. After the first pass the whole array is partially sorted. In the next pass, the value of K is reduced which increases the size of each segment and reduces the number of segments. The next value of K is chosen so that it is relatively prime to its previous value. The process is repeated until K = 1, at which the array is sorted. The insertion sort is applied to each segment, so each successive segment is partially sorted. The shell sort is also called the Diminishing Increment Sort, because the value of K decreases continuously.

SHELL SORT ROUTINE

void shellsort (int A[ ], int N)

{

int i, j, k, temp;

for (k = N/2; k > 0 ; k = k/2)

for (i = k; i < N ; i++)

{

temp = A[i];

for (j = i; j >= k & & A [ j - k] > temp ; j = j - k)

{

A[j] = A[j - k];

}

A[j] = temp;

}

}

Example

Consider an unsorted array as follows.

81 94 11 96 12 35 17 95 28 58

Here N = 10, the first pass as K = 5 (10/2)

81 94 11 96 12 35 17 95 28 58


Data Structures 4.3


81 94 11 96 12 35 17 95 28 58

After first pass

35 17 11 28 12 81 94 95 96 58

In second Pass, K is reduced to 3

35 17 11 28 12 81 94 95 96 58

After second pass,

28 12 11 35 17 81 58 95 96 94

In third pass, K is reduced to 1

28 12 11 35 17 81 58 95 96 94

The first sorted array is

11 12 17 28 35 58 81 94 95 96

ANALYSIS OF SHELL SORT :

WORST CASE ANALYSIS - O(N2)

BEST CASE ANALYSIS - O(N log N)

AVERAGE CASE ANALYSIS - O(N1.5)

ADVANTAGES OF SHELL SORT :

* It is one of the fastest algorithms for sorting small number of elements.

* It requires relatively small amounts of memory.











Data Structures 4.4


4.4 HEAP SORT

In heap sort the array is interpreted as a binary tree. This method has 2 phases. In phase 1, binary heap is constructed and In phase 2 delete min routine is performed.

Phase 1 :

Two properties of a binary Heap namely structure property and heap order property is achieved in phase 1.

Structure Property

For any element in array position i, the left child is in position 2i, the right child is in 2i + 1, (ie) the cell after the left child.

Heap Order Property

The key value in the parent node is smaller than or equal to the key value of any of its child node. To Build the heap, apply the heap order propery starting from the right most non - leaf node at the bottom level.

Phase 2 :

The array elements are sorted using deletemin operation, which gives the elements arranged in descending order.

For example. Consider the following array.

1 7 6 8 4 10 2

1 2 3 4 5 6 7

Phase 1 :

Binary Heap satisfying structure property

i = 1

2i = 1

2i +1 = 3


Data Structures 4.5


Binary heap satisfying heap order property

Phase 2 :-

Remove the smallest element from the heap and place it in the array.

Find the smallest child and swap with the root.


Data Structures 4.6


Reconstruct the heap till it satisfies the heap order property.

Remove the smallest element and place it in the array.


Data Structures 4.7


Reconstruct the heap till it satisfies the heap order property.

Swap (4) minimum & last element (10)

Place the value (4) in the array.


Data Structures 4.8


Similarly, apply the procedure for other elements.


Data Structures 4.9


Final array sorted in descending order using heapsort.

After the last deletemin, the array will contain the elements in descending order. To get the elements sorted in ascending order, Deletemax routine of heap is applied, in which the heap order property is changed. i.e. the parent has a larger key value then its children.

Consider the same example

1 7 6 8 4 10 2

1 2 3 4 5 6 7


Data Structures 4.10



Data Structures 4.11


Now the binary heap satisfies the heap order property.

Now, the root node contains the maximum key value, so apply delete max routine to this heap.

Remove the maximum element & place it in an array from the heap


Data Structures 4.12


Reconstruct the heap till it satisfies heap order property.

Remove the maximum element from the heap and place it in the array.


Data Structures 4.13


Reconstruct the heap till it satisfies the heap order property.

Remove the maximum element from the heap and place in the array.

Reconstruct the heap till it satisfies the heap order property.


Data Structures 4.14


Similarly, apply the procedure for other elements.


Data Structures 4.15


The deletion of last element in the heap gives array in an sorted order.

HEAP SORT USING DELETEMAX ROUTINE

void DeleteMax (int A [ ], int root, int bottom)

{

int maxchild, temp;

while (root *2 < = bottom)

{

if (root * 2 = = bottom)

maxchild = root * 2

else if (A[root * 2] > A [root * 2 +1])

maxchild = root * 2

else

maxchild = root * 2 + 1;

if (A [root] < A [maxchild])

{

swap (&A [root], &A [max child])

root = maxchild;

}

else

break;

}

}



Data Structures 4.16


void heapsort (int A[ ], int N)

{

int i;

for (i = N/2; i > = 0; i--)

DeleteMax (A, i, N);

for (i = N - 1; i > 0 ; i - -)

{

swap (&A [0], & A [i];

DeleteMax (A, 0, i -1);

}

}

ANALYSIS OF HEAPSORT

WORST CASE ANALYSIS - O(N log N)

BEST CASE ANALYSIS - O(N log N)

AVERAGE CASE ANALSIS - O(N log N)

ADVANTAGES OF HEAPSORT :

1. It is efficient for sorting large number of elements.

2. It has the advantages of worst case O(N log N) running time.

LIMITATIONS

* It is not a stable sort.

* It requires more processing time

4.5 MERGE SORT

The most common algorithm used in external sorting is the mergesort. This algorithm follows divide and conquer strategy. In dividing phase, the problem is divided into smaller problem and solved recursively. In conquering phase, the partitioned array is merged together recursively. Merge sort is applied to the first half and second half of the array. This gives two sorted halves, which can then be recurrively merged together using the merging algorithm.

The basic merging algorithm takes two input arrays A and B and an output array C. The first element of A array and B array are compared, then the smaller element is stored in the output array C and the corresponding pointer is incremented. When either input array is exhausted the remainder of the other array is copied to an output array C.



Data Structures 4.17


MERGE SORT ROUTINE

void mergesort (int A [ ], int temp [ ], int n)

{

msort (A, temp, o, n-1);

}

void msort (int A [ ], int temp [ ], int left, int right)

{

int center;

if (left < right)

{

center = (right + left)/2;

msort (A, temp, left, center);

msort (A, temp, center + 1, right);

merge (A, temp, left, center + 1, right);

}

}

MERGE ROUTINE

void merge (int A [ ], int temp [ ], int left, int center, int right)

{

int i, left _ end, num_elements, tmp_pos;

left_end = center - 1;

tmp_pos = left;

num_elements = right - left + 1 ;

while (( left < = left_end) && (center < = right))

{

If (A [left] < = A[center])

{

temp [tmp_pos] = A [left];

tmp_pos++;

left++;

}



Data Structures 4.18


else

{

temp [tmp_pos] = A [center];

tmp_pos++;

center ++ ;

}

while (left < = left_end)

{

temp [tmp_pos] = A[left];

left ++;

tmp pos++;

}

while (center < = right)

{

temp [temp_pos] = A [center];

center ++ ;

tmp_pos++;

}

for (i = 0; i < = num_elements ; i++)

{

A[right] = temp [right];

right ++;

}

}

Example

For instance, to sort the eight element array 24, 13, 26. 1, 2, 27, 38, 15, we recursively sort the first four and last four elements, obtaining 1, 13, 24, 26, 2, 15, 27, 38 then these array is divided into two halves and the merging algorithm is applied to get the final sorted array.



Data Structures 4.19


24 13 26 1 2 27 38 15

24 13 26 1 2 27 38 15

24 13 26 1 2 27 38 15

24 13 26 1 2 27 38 15

13 24 1 26 2 27 15 38

1 13 24 26 2 15 27 38


Data Structures 4.20


Now, the merging algorithm is applied as follows,

Let us consider first 4 elements 1, 13, 24, 26 as A array and the next four elements 2, 15, 27, 38 as B array.

1 13 24 26 2 15 27 38

Aptr Bptr

A array B array

Cptr

C aray

First, the element 1 from A array and element 2 from B array is compared, then the smallest element 1 from A array is copied to an output array C. Then the pointers Aptr and Cptr is incremented by one.

1 13 24 26 2 15 27 38

Aptr Bptr

A array B array

1

Cptr

C aray

Next, 13 and 2 are compared and the smallest element 2 from B array is copied to C array and the pointers Bptr and Cptr gets incremented by one. This proceeds until A array and B array are exhausted, and all the elements are copied to an output array C.


Data Structures 4.21


1 13 24 26 2 15 27 38

Aptr Bptr

Cptr

1 13 24 26 2 15 27 38

Aptr Bptr

Cptr

1 13 24 26 2 15 27 38

Aptr Bptr

Cptr

1 13 24 26 2 15 27 38

Aptr Bptr

1

2

13

1

2

1 2 13 15


Data Structures 4.22


1 2 13 15 24

1 2 13 15 24 26

Cptr

1 13 24 26 2 15 27 38

Aptr Bptr

Cptr

Since A array is exhausted, the remaining elements of B array is then copied to C array.

1 13 24 26 2 15 27 38

Aptr Bptr

Cptr

Final Sorted Array

ANALYSIS OF MERGESORT

WORST CASE ANALYSIS : O(N log N)

BEST CASE ANALYSIS : O(N log N)

AVERAGE CASE ANALYSIS : O (N log N)

1 2 13 15 24

1 2 13 15 24 26

1 2 13 15 24 26 27 38

1 2 13 15 24 26 27 38


Data Structures 4.23


Limitations of Merge Sort

* Mergesort sorts the larger amount of data making use of

external storage device.

* It requires extra memory space

Advantages

* It has better cache performance

* Merge Sort is a Stable Sort

* It is simpler to understand than heapsort.

4.6 QUICK SORT

Quick Sort is the most efficient internal sorting technique. It posseses a very good average case behaviour among all the sorting techniques. It is also called partioning sort which uses divide and conquer techniques.

The quick sort works by partioning the array A[1], A[2].......A[n] by picking some keyvalue in the array as a pivot element. Pivot element is used to rearrange the elements in the array. Pivot element is used to rearrange the elements in the array. Pivot can be the first element of an array and the rest of the elements are moved so that the elements on left side of the pivot are lesser than the pivot, whereas those on the right side are greater than the pivot. Now, the pivot element is placed in its correct position. Now the quicksort procedure is applied for left array and right array in a recursive manner.

QUICK SORT ROUTINE

void qsort (int A[ ], int left, int right)

{

int i, j, pivot, temp ;

if (left < right)

{

pivot = left;

i = left + 1;

j = right;

while (i < j)

{

while (A [PIVOT] > = A[i])

i = i + 1;

while (A[PIVOT] < A[j])



Data Structures 4.24


{

temp = A[i]; // swap

A[i] = A[j]; // A[i] & A[j]

A[j] = temp;

}

}

temp = A[PIVOT]; // swap A[PIVOT] & A[j]

A[PIVOT] = A[j];

A[j] = temp;

qsort (A, left, j - 1);

qsort (A, j+1, right);

}

}

Example :-

Consider an unsorted array as follows,

40 20 70 14 60 61 97 30

Here PIVOT = 40, i = 20, j = 30

The value of i is incremented till a[i] Pivot and the value of j is decremented till a[j] > pivot, this process is repeated until i < j.

If a[i] > pivot and a[j] < pivot and also if i < j then swap a[i] and a[j].

If i > j then swap a[j] and a[pivot].

Once the correct location for PIVOT is found, then partition array into left sub array and right subarray, where left sub array contains all the elements less than the PIVOT and right sub array contains all the elements greater than the PIVOT

PASSES OF QUICK SORT

40 20 70 14 60 61 97 30

Pivot i j

40 20 70 14 60 61 97 30

Pivot i j

Swap (a[i], a[j], i.e As i < j

swap (70, 30)



Data Structures 4.25


40 20 30 14 60 61 97 70

Pivot i j

40 20 30 14 60 61 97 70

Pivot i

40 20 30 14 60 61 97 70

Pivot i

40 20 30 14 60 61 97 70

Pivot i j

40 20 30 14 60 61 97 70

Pivot i, j

40 20 30 14 60 61 97 70

Pivot i, j

40 20 30 14 60 61 97 70

Pivot j i

As i > j swap (a[j], a[pivot])

i.e swap (60, 40)

14 20 30 40 60 61 97 70

Now, the pivot element has reached its correct position. The elements lesser than the Pivot {14, 20, 30} is considered as left sub array. The elements greater than the pivot {60, 61, 97, 70} is considered as right sub array. Then the q sort procedure is applied recursively for both these arrays.

ANALYSIS OF QUICK SORT

WORST - CASE ANALYSIS = O[N2]

BEST - CASE ANALYSIS = O[N log N)

AVERAGE - CASE ANALYSIS = O(N log N)

Advantages of Quick Sort

1. It is faster than other O(N log N) algorithms.

2. It has better cache performance and high speed.

Limitation

* Requires More Memory space


Data Structures 4.26


4.7 External Sorting

It is used for sorting methods that are employed when the data to be sorted is too large to fit in primary memory.

Need for external storing

During the sorting, some of the data must be stored externally such as tape or disk

The cost of accessing data is significantly greater than either book keeping or comparison

costs.

If tape is used as external memory then the items must be accessed sequentially.

Steps to be followed

The basic external sorting algorithm uses the merge routine from merge sort.

1. Divide the file into runs that the size of a run is small enough to fit into main memory.

2. Sort each run in main memory

3. Merge the resulting runs together into successively bigger runs.

Repeat the steps until the file is sorted.

4.7.1 The Simple Algorithm (2 way Merge)

Let us consider four tapes Ta1, Ta2, Tb1, Tb2, which are two input and two output tapes. The a and b tapes can act as either input tapes or output tapes depending upon the algorithm.

Let the size of the run (M) is taken as3 to sort the following set of values.

Ta1 44 80 12 35 45 58 75 60 24 48 92 98 85

Ta2

Tb1

Tb2

Initial Run Construction

Step 1 : Read M records at a time from the i/p tape Ta1.

Step 2 : Sort the records internally and write the resultant records alternately to Tb1 and Tb2.

Ta1

Ta2

Tb1 12 44 80 24 60 75 85

Tb2 35 45 58 48 92 98


Data Structures 4.27


First 3 records from the input tape Ta1 is read and sorted internally as (12, 44, 80) and placed in Tb1.

Then, next 3 records (35, 45, 58) are read and the sorted records is placed in Tb2.

Similarly the rest of the records are placed alternatively in Tb1 and Tb2. Now Tb1 and Tb2 contain a group of runs.

number of runs = 4.

First Pass

First run of Tb1 & Tb2 are merged and the sorted records placed in Ta1.

Similarly the second run of Tb1 & Tb2 are merged and the sorted records placed in Ta2.

Ta1 12 35 44 45 58 80 85

Ta2 24 48 60 75 92 98

Tb1

Tb2

Here the number of run is reduced to 2, but the size of the runs are increased.

Second Pass

First run of Ta1 and Ta2 are merged and the sorted records is placed in Tb1 and the second run of Ta1 is placed in Tb2.

Ta1

Ta2

Tb1 12 24 35 44 45 48 58 60 75 80 92

Tb2 85

Third pass

In the third pass, run from Tb1 and Tb2 are merged and then sorted records is placed in Ta1.

Ta1 12 24 35 44 45 48 58 60 75 80 85 92

Ta2

Tb1

Tb2

This algorithm will require log (N/M) passes, plus the initial run constructing pass.


Data Structures 4.28


4.7.2 MULTIWAY MERGE

The number of passes required to sort an input can be reduced by increasing the number of tapes. This can be done by extending the 2 - way merge to k - way merge. The only difference is that, it is more complicated to find the smallest of the k elements, which can be overcome by using priority queues.

For the same input,

40 80 12 35 45 58 75 60 24 48 92 98 85

Let us consider 6 tapes Ta1, Ta2, Ta3, Tb1, Tb2, Tb3 & M = 3

Initial run constructing pass

Ta1

Ta2

Ta3

Tb1 12 44 80 48 92 98

Tb2 35 45 58 85

Tb3 24 60 75

In first pass, first run of Tb1, Tb2 and Tb3 are merged and sorted records are placed Ta1. Similarly, second run from Tb1 & Tb2 are merged and sorted records are then placed in Ta2.

FIRST PASS

Ta1 12 24 35 44 45 58 60 75 80

Ta2 48 85 92 98

Ta3

Tb1

Tb2

Tb3

In second pass, runs from Ta1 and Ta2 is merged and the sorted records is placed in Tb1, which contains the final sorted records.


Data Structures 4.29


SECOND PASS

Ta1

Ta2

Ta3

Tb1 12 24 35 44 45 48 58 60 75 80 85 92 98

Tb2

Tb3

For the same example, 2 - way merge requires 4 passes to get the sorted elements, whereas in Multiway - Merge it is reduced to 3 passes, which also includes the initial run constructing pass.

Note : - After the initial run construction phase, the no. of passes required using k - way merging is log k [N/M] because the runs get k times as large in each pass.

4.7.3 POLYPHASE MERGE

The k - way merge strategy requires 2k tapes to perform the sorting. In some application it is possible to get by only k + 1 tapes.

For example, let us consider 3 tapes T1, T2 and T3 and an input file on T1 that produce 8 runs.

The distribution of the runs in each tape various as follows,

Runs

1. Equal distribution (4 & 4)

2. Unequal distribution (7 & 1)

3. Fibonaci numbers (3 & 5)

Equal Distribution

Put 4 runs on each tapes T2 & T3, after applying merge routine, the resultant tape T1 has 4 runs, whereas other tapes T2 & T3 are empty which leads to adding an half pass for every pass.

Tapes Run After After After After After

Construction T2 + T3 Splitting T1 + T2 Split T2 + T3

T1 0 4 2 0 0 1

T2 4 0 2 0 1 0

T3 4 0 0 2 1 0

In first pass, all the runs (4) are placed in one tapes, so it is logically divided and placed half of the runs (2) in any of the other tapes.

UNEQUAL DISTRIBUTION

For instance, if 7 runs are placed on T2 and 1 run in T3. Then after the first merge T1 will hold 1 run and T2 will hold 6 runs. As it merge only one set of run, the process get slower resulting more number of passes





Data Structures 4.30











Data Structures 4.31

Tapes Run After After After After After After After

Const T2 +T3 T1 +T2 T2 +T3 T1 +T2 T2 +T3 T1 +T2 T2 +T3

T1 0 1 0 1 0 1 0 1

T2 7 6 5 4 3 2 1 0

T3 1 0 1 0 1 0 1 0


FIBONACCI NUMBERS

If the number of runs is the fibonacci number F(N), then the runs are distributed as 2 fibonaci numbers F(N - 1) & F(N - 2).

Here the number of runs is 8, a Fibonacci number, so it can be distributed as 3 runs in Tape T2 and 5 runs in T3.

Tape Run After After After After

Const T2 + T3 T1 + T3 T1 + T2 T2 + T3

T1 0 3 1 0 1

T2 3 0 2 1 0

T3 5 2 0 1 0

This method of distributing runs gives the optimal result, i.e less number of passes to sort the records than the other two methods.



Data Structures 4.32


Questions

Part A

1. Define Sorting

2. Differentiate Internal Sorting and External Sorting

3. Give examples for Internal Sorting and External Sorting

4. Sort the sequence 3, 4, 1, 5, 9, 2, 6 using insertion sort.

5. Write the routine for Insertion Sort.

6. What is diminishing Increment Sort?

7. What is the average number of comparison used to sort N distinct items using Heap Sort.

8. Name the Sorting technique which uses divide and conquer strategy.

9. What is the best case and average case analysis for quicksort?

10. What is the need for external sort?

11. Compare two - way merge and Multi - way Merge.

12. Write a note on polyphase merge.

13. What is the running time of heapsort for presorted input?

14. Determine the running time of mergesort for sorted input.

15. Sort 3, 4, 5, 9, 2, 6 using mergesort.

PART - B

1. Write down the shellsort algorithm Using this algorithm : trace the following numbers.

10 9 5 6 4 8 2 7 1

2. Explain QuickSort algorithm : with an example

3. Write the procedure for HeapSort and trace the given numbers,

18 13 10 8 5 15

4. What is external sorting? Give an example for Multiway merge and polyphase merging

strategy with three tapes T1, T2 and T3.


Data Structures 4.33


// C-Code for Insertion Sort

#include<stdio.h>

#include<conio.h>

void main()

{

int i,j,n,k,temp,a[10];

clrscr();

printf("Enter the array size");

scanf("%d",&n);

printf("Enter the elements to be sorted");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

printf("\nPasses of Insertion sort");

for(i=0;i<n;i++) // Insertion Sort Routine

{

temp=a[i];

for(j=i;j>0 && a[j-1]>temp;j—)

{

a[j]=a[j-1];

}

a[j]=temp;

for(k=0;k<n;k++) // Routine to print the passes

printf("%d\t",i,a[k]);

printf("\n");

}

printf("\nThe sorted elements are\n");

for(i=0;i<n;i++)

printf("%d\t",a[i]);

}

Sample Input and Output:

Enter the array size

6

Enter the elements to be sorted

20 10 60 40 30 15

Passes of Insertion sort

i=1 10 20 60 40 30 15

i=2 10 20 60 40 30 15

i=3 10 20 40 60 30 15

i=4 10 20 30 40 60 15

i=5 10 15 20 30 40 60

The sorted elements are

10 15 20 30 40 60


Data Structures


//C-Code for Shell Sort

#include<stdio.h>

#include<conio.h>

void main()

{

int i,j,n,k,temp,a[20],p;

clrscr();

printf("Enter the array size");

scanf("%d",&n);

printf("Enter the elements to be sorted");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

printf("\nPasses of Shell sort\n");

for(k=n/2;k>0;k=k/2) // Shell Sort Routine

for(i=k;i<n;i++)

{

temp=a[i];

for(j=i;j>=k && a[j-k]>temp;j=j-k)

{

a[j]=a[j-k];

}

a[j]=temp;

printf("\nk=%d\t",k);

for(p=0;p<n;p++) //Passes of Shell Sort

printf("%d\t",a[p]);

printf("\n");

}

printf("\nThe sorted elements are\n");

for(i=0;i<n;i++)

printf("%d\t",a[i]);

getch();

}

Sample Input and Output:

Enter the array size

9

Enter the elements to be sorted

81 94 11 96 15 30 20 70 40


Data Structures


Passes of Shell sort

k=4 15 94 11 96 81 30 20 70 40

k=4 15 30 11 96 81 94 20 70 40

k=4 15 30 11 96 81 94 20 70 40

k=4 15 30 11 70 81 94 20 96 40

k=4 15 30 11 70 40 94 20 96 81

k=2 11 30 15 70 40 94 20 96 81

k=2 11 30 15 70 40 94 20 96 81

k=2 11 30 15 70 40 94 20 96 81

k=2 11 30 15 70 40 94 20 96 81

k=2 11 30 15 70 20 94 40 96 81

k=2 11 30 15 70 20 94 40 96 81

k=2 11 30 15 70 20 94 40 96 81

k=1 11 30 15 70 20 94 40 96 81

k=1 11 15 30 70 20 94 40 96 81

k=1 11 15 30 70 20 94 40 96 81

k=1 11 15 20 30 70 94 40 96 81

k=1 11 15 20 30 70 94 40 96 81

k=1 11 15 20 30 40 70 94 96 81

k=1 11 15 20 30 40 70 94 96 81

k=1 11 15 20 30 40 70 81 94 96

The sorted elements are

11 15 20 30 40 70 81 94 96


Data Structures


//C-Code for Quick Sort

#include<stdio.h>

#include<conio.h>

int a[20],n;

void main()

{

int i;

void qsort(int,int);

clrscr();

printf("Enter the array size");

scanf("%d",&n);

printf("\nEnter the elements to be sorted\n");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

qsort(0,n-1);

printf("the Sorted elements are\n");

for(i=0;i<n;i++)

printf("%d\t",a[i]);

getch();

}

void qsort(int left,int right)

{

int i,j,pivot,temp,k;

if(left<right)

{

i=left+1;

j=right;

pivot=left;

for( ; ;)

{

while(a[pivot]>=a[i])

i=i+1;

while(a[pivot]<a[j])

j=j-1;

if(i<j)

{

temp=a[i];

a[i]=a[j];

a[j]=temp;

for(k=0;k<n;k++)


Data Structures


printf("%d\t",a[k]);

printf("\n");

}

else

break;

}

temp=a[pivot];

a[pivot]=a[j];

a[j]=temp;

for(k=0;k<n;k++)

printf("%d\t",a[k]);

printf("\n");

qsort(left,j-1);

qsort(j+1,right);

}

return;

}

SAMPLE INPUT AND OUTPUT:

Enter the array size 5

Enter the elements to be sorted

30 20 40 50 10

Passes of Quick Sort

30 20 10 50 40

10 20 30 50 40

10 20 30 50 40

10 20 30 40 50

the Sorted elements are

10 20 30 40 50

\


Data Structures


// C-Code for MERGE SORT

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

int A[20];

int temp[20];

void mergeSort(int A[], int temp[], int n);

void msort(int A[], int temp[], int left, int right);

void merge(int A[], int temp[], int left, int center, int right);

void main()

{

int i,n;

clrscr();

printf("Enter the Array Size : ");

scanf("%d",&n);

printf("Enter the values to be sorted");

for (i = 0; i < n; i++)

scanf("%d",&A[i]);

mergeSort(A, temp, n);

printf("Sorted Array Using MergeSort...\n");

for (i = 0; i < n; i++)

printf("%i\t", A[i]);

getch();

}

void mergeSort(int A[], int temp[], int n)

{

msort(A,temp,0,n - 1);

}

void msort(int A[], int temp[], int left, int right)

{

int center;

if (left < right)

{

center = (right + left) / 2;

msort(A, temp, left, center);

msort(A, temp, center+1, right);

merge(A, temp, left, center+1, right);

}

}

void merge(int A[], int temp[], int left, int center, int right)


Data Structures


{

int i, left_end, num_elements, tmp_pos;

left_end = center - 1;

tmp_pos = left;

num_elements = right - left + 1;

while ((left <= left_end) && (center <= right))

{

if (A[left] <= A[center])

{

temp[tmp_pos] = A[left];

tmp_pos++;

left++;

}

else

{

temp[tmp_pos] = A[center];

tmp_pos++;

center++;

}

}

while (left <= left_end)

{

temp[tmp_pos] = A[left];

left++;

tmp_pos++;

}

while (center <= right)

{

temp[tmp_pos] = A[center];

center++;

tmp_pos++;

}

for (i=0; i <= num_elements; i++)

{

A[right] = temp[right];

right—;

}

}


Data Structures


C-Code for Heap Sort

#include <stdlib.h>

#include <stdio.h>

#include<conio.h>

void heapSort(int A[], int N);

void DeleteMax(int A[], int , int );

int A[20];

void main()

{

int i,n;

clrscr();

printf("Enter the ArraySize :");

scanf("%d",&n);

printf("Enter the elements of Array\n");

for (i = 0; i < n; i++)

scanf("%d",&A[i]);

heapSort(A,n);

printf("Sorted Elements using Heap Sort...\n");

for (i = 0; i < n; i++)

printf("%i\n", A[i]);

getch();

}

void heapSort(int A[], int N)

{

int i, temp;

for (i = (N / 2)-1; i >= 0; i—)

DeleteMax(A, i, N);

for (i = N-1; i >= 1; i—)

{

temp = A[0];

A[0] = A[i];

A[i] = temp;

DeleteMax(A, 0, i-1);

}

}

void DeleteMax(int A[], int root, int bottom)


Data Structures


{

int maxChild, temp;

while ((root*2 <= bottom))

{

if (root*2 == bottom)

maxChild = root * 2;

else if (A[root * 2] > A[root * 2 + 1])

maxChild = root * 2;

else

maxChild = root * 2 + 1;

if (A[root] < A[maxChild])

{

temp = A[root];

A[root] = A[maxChild];

A[maxChild] = temp;

root = maxChild;

}

else

break;

}

}

SAMPLE IMPUT AND OUTPUT:

Enter the ArraySize :5

Enter the elements of Array

40 60 30 20 10

Sorted Elements using Heap Sort...

10 20 30 40 60


Data Structures


/* BINARY SEARCH*/

#include<stdio.h>

#include<conio.h>

void main()

{

int flag=0,a[20],n,pos,i,item,low,high,mid;

void sort(int[],int);

clrscr();

printf("enter the no. of numbers\n");

scanf("%d",&n);

printf("enter the numbers\n");

for(i=1;i<=n;i++)

scanf("%d",&a[i]);

sort(a,n);

printf("enter the data to be searched\n");

scanf("%d",&item);

low=1;

high=n;

while(low<=high)

{

mid=(low+high)/2;

if(item==a[mid])

{

flag=1;

break;

}

else if(item>a[mid])

low=mid+1;

else

high=mid-1;

}

if(flag==0)

printf("the element %d is not present in the array\n",item);

else

printf("the element %d is present in the array",item);

getch();

}


Data Structures


void sort(int a[],int n)

{

int i,j,temp;

for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

if(a[i]>a[j])

{

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

OUTPUT:

enter the no. of numbers

5

enter the numbers

7 8 2 4 9

enter the data to be searched

4

the element 4 is present in the array

RESULT:

Thus data is searched in an array using Binary Search.


Data Structures


/*DEPTH FIRST SEARCH*/

#include<stdio.h>

#include<conio.h>

int a[10][10],visited[10],n;

void main()

{

int i,j;

void searchfrom(int);

clrscr();

printf("enter the no. of nodes\n");

scanf("%d",&n);

printf("enter the adjacency matrix\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

scanf("%d",&a[i][j]);

for(i=1;i<=n;i++)

visited[i]=0;

printf("Depth First Path: ");

for(i=1;i<=n;i++)

if(visited[i]==0)

searchfrom(i);

}

void searchfrom(int k)

{

int i;

printf("%d\t",k);

visited[k]=1;

for(i=1;i<=n;i++)

if(visited[i]==0)

if(a[k][i]!=0)

searchfrom(i);

return;

}


Data Structures


OUTPUT:

enter the no. of nodes

4

enter the adjacency matrix

0 1 0 1

0 0 1 1

0 0 0 1

0 0 0 0

Breadth First Path

1 2 3 4

RESULT:

Thus a graph is traversed using Depth First Search.


Data Structures