# What is Sorting in Data Structure?

Sorting

Sorting means arranging the elements of an array so that they placed in some specific order which may be either ascending or descending.

For example; it is easy to look in the dictionary for a word if it is arranged (or sorted) in alphabetic order A sorting algorithm is defined as an algorithm that puts the elements of an array in a certain order (lexicographical order) and any user defined order.

Let A be a list of n elements A1, A2, ....... An in memory. Sorting of list A refers to the operation of rearranging the contents of A so that they are in increasing (or decreasing) order (numerically or lexicographically); A1 < A2 < A3 < ...... < An. Since A has n elements, the contents in A can appear in n! ways. These ways correspond precisely to the n! permutations of 1,2,3, ...... n. Each sorting algorithm must take care of these n! possibilities.

#### There are two types of sorting.:-

·        Internal
·        External

Internal  sorting:- Which deals with the data stored in the computer memory.

External sorting:-  Which deals with sorting the data stored in the file.

External sorting is implied where there is huge data, that can not be stored in the memory.

### Types of sort

·       Merge sort

·       Bubble sort

·       Selection sort

·       Insertion sort

#### Merge sort

Merge sort is the sorting algorithm that uses the divide, conquer and

combine algorithm technique.

These three concepts are as follows:-

·        Divide :-  That means partitioning the n element array to be sorted into two arrays of n/2 elements. If an array containing 0 or 1 element, then it is already sorted but if there are no elements in the array then divide by n/2 sub-arrays, each containing about half of the element of the original array.

·        Conquer :- that means sorting the two sub-arrays recursively using merge sort.

·        Combine :- merging the two sorted subarrays of size n/2 to produce the sorted array of n elements.

The basic steps of a merge sort algorithm are as follows:-

·        If the array is of length 0 or 1 then it is already sorted

·        Otherwise divide the unsorted array into two sub-arrays off about half of the size..

·        Else merge sort algorithm recursively to sort each sub-array.

·        Merge the two sub-array to form a single sorted list.

Algorithm for merge sort :-

Step 1: [initialized] set i=beg, j=mid, in=0

Step 2: repeat while (i<=mid) and (j<=end)

If a[i] <a[j]

Temp[in] =a[i]

Increment i++.

Else

Temp [in] =a[j]

Increment j

Set in=in+ 1

[end of the loop]

Step 3: [copy of remaining elements of right sub array in the temp, if any element left now]

Step 4: if i>mid

Repeat while (j<=end)

Set temp [in] =a[j]

Increment in

Increment j

[end of the loop ]

Step 5:- [copy of the remaining element of the left sub array in to temp, if any element left             now]

Step 6: else

Repeat while (i<=mid)

Temp [in] =a[j]

Increment in

Increment i

[end of loop]

Step 7: [copy the elements of temp to the array a]

Step 8: set i=0

Repeat while (i<in)

A[i] =temp[i]

[end of the loop]

Step 9:end

Merge sort (a[], beg, end)

Step 1: [initialize] set beg, mid, end, in

Step 2: if (beg<mid)

Set mid=(beg + end)/2

Call_merge sort (a, beg, mid)

Else

Call_merge sort (a, mid-1, end )

Call_merge sort (a, beg, mid, end)

[end of loop]

Step 3: end

#### The complexity of merge sort:-

The running time of the merge sort in the average case and in the worst case it can be given as O(nlogn), in the worst-case efficiency is given O(n log n). But merge sort needs an additional space of O(n) for the temporary array (temp).

#### Program of merge sort

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

void mergesort(int [],int,int);

void merge(int [],int,int,int);
void main()
{
int n ,arr,i,j;
clrscr();
printf("\nenter the size of array:-");
scanf("%d",&n);
printf("\nenter the data in the array");
for(i=0;i<n;i++)
{
printf("enter the %dth element",i+1);
scanf("%d",&arr[i]);
}
printf("\n display of array");
for(i=0;i<n;i++)
{
printf("\n%d",arr[i]);
}
mergesort(arr,0,n-1);
printf("\nafter merge sort") ;
for(i=0;i<n;i++)
{
printf("%d",arr[i]);
}
getch();

}           void mergesort( int arr[], int beg, int end)
{
int i,j,temp,mid;
if(beg<end)
{
mid=(beg+end)/2;
mergesort(arr,beg,mid);
mergesort(arr,mid+1,end);
merge(arr,beg,mid,end);
}
}

void merge (int arr[],int beg,int mid,int end)
{
int i=beg,j=mid+1,in=beg,temp,k;

while((i<=mid)&&(j<=end))
{
if(arr[i]<arr[j])
{
temp[in]=arr[i];
i++;
}
else
{
temp[in]=arr[j];
j++;
}in++;
}
if(i>mid)
{
while(j<=end)
{
temp[in]=arr[j];
j++;
in++;
}
}
else
{
while (i<=mid)
{
temp[in]=arr[i];
i++;
in++;
}
}
for(i=0;i<in;i++)
{
arr[i]=temp[i];
}
}

#### BUBBLE SORT

In bubble sort, each element is compared with its adjacent element. If the first element is larger than the second one, then the positions of the elements are interchanged, otherwise, it is not changed. Then next element is compared with its adjacent element and the same process is repeated for all the elements in the array until we get a sorted array

Let A be a linear array of n numbers. Sorting of A means rearranging the elements

of A so that they are in order. Here we are dealing with ascending order. i.e.,

A < A < A < ...... A[n].

Suppose the list of numbers A, A, ………… A[n] is an element of array A.

The bubble sort algorithm works as follows

Step 1:

Compare A and A and arrange them in the (or desired) ascending order,

that A < A .that is if A is greater than A then interchange the position

of data by

swap  =  A ;

A  =  A;

A  =  swap.

Then compare A and A and arrange them so that A < A.

Step 2:

Repeat step 1 with one less comparison that is, now stop comparison at A [n – 1]

and possibly rearrange A[N – 2] and A[N – 1] and so on.

The following figures will depict the various steps (or PASS) involved in  the sorting of an array of 5 elements.

The elements of an array A to be sorted are:

42, 33, 23, 74, 44

FIRST PASS

33 swapped    33                       33                            33

42                      23 swapped     23                            23

23                      42                       42 no swapping    42

74                      74                       74                             44 swapped

44                      44                       44                              74

Second pass

23 swapped    23                          23

33                     33 no swapping  33

42                      42                         42 no swapping

44                     44                           44

74                     74                           74

Third pass

23                      23

33                      33 no swapping

42                      42

44                      44

74                      74

Fourth pass

23

33

42

44

74

Thus the sorted array is 23, 33, 42, 44, 74.

ALGORITHM

Let A be a linear array of n numbers. Swap is a temporary variable for swapping (or interchange) the position of the numbers.

(1)      Input n numbers of an array A

(2)      Initialise i = 0 and repeat through step 4 if (i < n)

(3)      . Initialize j = 0 and repeat through step 4 if (j < n – i – 1)

(4)      If (A[j] > A[j + 1])

(a)  Swap = A[j]

(b)A[j] = A[j + 1]

(c) A[j + 1] = Swap

(5)      Display the sorted numbers of array A

(6)      Exit.

//PROGRAM TO IMPLEMENT BUBBLE SORT USING ARRAYS

//CODED AND COMPILED IN TURBO C

#include<stdio.h>

#include<conio.h>

void main()

{

int n,arr,i,j,temp=0;

clrscr();

//here first  enter the size of the array

printf("enter the size of array");

scanf("%d",&n);

// enter the  data in array

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

{

printf("\nenter the %d th data=",i+1);

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

}

//bubble sorting can  be implemented here

for(i=0;i<n;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;

}

}

}  //  after sorting  display of the sorted list

printf("\nafter sorting");

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

{

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

}

getch();

}

## SELECTION SORT

There are a number of applications in which we are interested in identifying a single element in terms of its rank relative to an ordering of the entire set. Examples include identifying the minimum and maximum elements, but we may also be interested in, say, identifying the median element, that is, the element such that half of the other elements are smaller and the remaining half are larger. In general, queries that ask for an element with a given rank are called order statistics.

# Deﬁning the Selection Problem

In this section, we discuss the general order-statistic problem of selecting the kth smallest element from an unsorted collection of n comparable elements. This is known as the selection problem. Of course, we can solve this problem by sorting the collection and then indexing it into the sorted sequence at index k−1. Using the best comparison-based sorting algorithms, this approach would take O(nlogn) time, which is obviously overkilled for the cases where k = 1 or k = n (or even k = 2, k = 3, k = n−1, or k = n−5), because we can easily solve the selection problem for these values of k in O(n) time. Thus, a natural question to ask is whether we can achieve an O(n) running time for all values of k (including the interesting case of ﬁnding the median, where k =n/2).

Step 1:

Find the smallest element in the array of n numbers A, A, ...... A[n]. Let LOC is the location of the smallest number in the array.

Then interchange A[LOC] and A by swap = A[LOC];

A[LOC] = A; A = Swap.

Step 2:

Find the second smallest number in the sub list of n – 1 element A  A  ...... A [n – 1] (the first element is already sorted). Now we concentrate on the rest of the elements in the array.

Again A [LOC] is the smallest element in the remaining array and LOC the corresponding location then interchange A [LOC] and A .

Now A  and A  is sorted since A  less than or equal to A .

Step 3:

Repeat the process by reducing one element each from the array

Step n – 1:

Find the n – 1 smallest number in the sub array of 2 elements

(i.e., A(n– 1), A (n)).

Consider A [LOC] is the smallest element and LOC is its corresponding position.

Then interchange A [LOC] and A(n – 1).

Now the array A , A , A , A ,………..A [n] will be a sorted array.

Sort  five numbers 42, 33, 23, 74, 44 :

First pass:

A=42                                   A=23

A=33     LOC=3                  A =33       LOC =2

A=23                                   A=42

A=74                                   A=74

A=44                                   A=44

SECOND PASS:                                    THIRD PASS:

A= 23                                                    A= 23

A= 33      LOC=2                                  A=33       LOC=3

A=42                                                     A= 42

A=74                                                     A= 74

A=44                                                     A= 44

FOURTH PASS:

A=23

A=33       LOC=5

A=42

A=44

A=74

#### ALGORITHM

Let A be a linear array of n numbers A , A , A , ……… A [k], A [k+1], …….. A [n].

Swap be a temporary variable for swapping (or interchanging) the position of the numbers. Min is the variable to store the smallest number and Loc is the location of the smallest element.

(1)Input n numbers of an array A

(2)Initialize i = 0 and repeat through step5 if (i < n – 1)

(a ) min = a[i]

(b) loc = i

(3) Initialize j = i + 1 and repeat through step 4 if (j < n – 1)

(4) if (a[j] < min)

(a) min = a[j]

(b) loc = j

(5) if (loc ! = i)

(a) swap = a[i]

(b) a[i] = a[loc]

(c) a[loc] = swap

(6) Display “the sorted numbers of array A”

(7) Exit

#### //PROGRAM TO IMPLEMENT SELECTION SORT

//USING STATIC MEMORY ALLOCATION, THAT IS USING ARRAYS //CODED AND COMPILED IN TURBO C

#include<conio.h>

#include<stdio.h>

#define MAX 20

void main()

{

int arr[MAX], i,j,k,n,temp,smallest;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”, & n);

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

{

printf (“\nEnter element %d : ”,i+1);

scanf (“%d”, &arr[i]);

}

printf (“\nUnsorted list is : \n”);

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

printf (“%d ”, arr[i]); printf (“\n”);

/*Selection sort*/

for (i = 0; i < n – 1 ; i++) {

/*Find the smallest element*/

smallest = i;

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

{

if (arr[smallest] > arr[k])

smallest = k ;

}

if ( i != smallest )

{

temp = arr [i];

arr[i] = arr[smallest];

arr[smallest] = temp ;

}

printf (“\nAfter Pass %d elements are :  ”,i+1);

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

printf (“%d ”, arr[ j]);

printf (“\n”);

}/*End of for*/

printf (“\nSorted list is : \n”);

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

printf (“%d ”, arr[i]);

getch();

}

/*End of main()*/

INSERTION SORT

Insertion sort algorithm sorts a set of values by inserting values into an existing sorted file. Compare the second element with the first, if the first element is greater than the second, place it before the first one. Otherwise, the place is just after the first one. Compare the third value with the second. If the third value is greater than the second value then place it just after the second. Otherwise, place the second value to the third place. And compare the third value with the first value. If the third value is greater than the first value place the third value to second place, otherwise place the first value to second place. And place the third value to first place and so on.

Let A be a linear array of n numbers A , A , A ,  ...... A[n] . The algorithm scans the array A from A  to A [n], by inserting each element A[k], into the proper position of the previously sorted sub-list. A , A , A  ,  ......  A [k – 1]

Step 1:

As the single element A  by itself is sorted array.

Step 2:

A  is inserted either before or after A  by comparing it so that A, A is a sorted array.

Step 3:

A  is inserted into the proper place in A , A , that is A  will be compared with A  and A  and placed before A , between A  and A , or after A  so that A , A , A  is a sorted array.

Step 4:

A  is inserted in to a proper place in A , A , A  by comparing it; so that A , A , A , A  is a sorted array.

Step 5:

Repeat the process by inserting the element in the proper place in array

Step n:

A [n] is inserted into its proper place in an array A , A , A , ...... A [n – 1] so that A , A , A , ...... ,A [n] is a sorted array.  ALGORITHM

Let A be a linear array of n numbers A , A , A , ...... ,A [n]......Swap be a temporary variable to interchange the two values. Pos is the control variable to hold the position of each pass.

(1)   . Input an array A of n numbers

(2)   Initialize i = 1 and repeat through steps 4 by incrementing i by one.

(a)   If (i < = n – 1)

(b)   Swap = A [I]

(c)    Pos = i – 1

(3)   Repeat the step 3 if (Swap < A[Pos] and (Pos >= 0))

(a)   A [Pos+1] = A [Pos]

(b)   Pos = Pos-1

(4)   A [Pos +1] = Swap

(5)   EXIT

//PROGRAM TO IMPLEMENT INSERTION SORT USING ARRAYS

//CODED AND COMPILED IN TURBO C

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

#define MAX 20

void main()

{

int arr[MAX],i,j,k,n;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”,&n);

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

{

printf (“\nEnter element %d : ”,i+1);

scanf (“%d”, &arr[i]);

}

printf (“\nUnsorted list is :\n”);

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

printf (“%d ”, arr[i]);

printf (“\n”);

/*Insertion sort*/

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

{

k=arr[j];

/*k is to be inserted at proper place*/

for(i=j–1;i>=0 && k<arr[i];i--)

arr[i+1]=arr[i];

arr[i+1]=k;

printf (“\nPass %d, Element inserted in proper place: %d\n”,j,k);

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

printf (“%d ”, arr[i]);

printf (“\n”);               }

printf (“\nSorted list is :\n”);

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

printf (“%d ”, arr[i]);

getch();

}

/*End of main()*/