## Sorting Algorithm

A sorting algorithm is used to rearrange a set of un-ordered data in a regular fashion for example – in increasing or decreasing manner.

in an efficient way so that it consumes less time as well as space i.e. have less time and space complexity.

## Most important thing – Why sorting is performed?

The answer is simple

It reduces search time, as if it is known to us that how a data is Sorted we can search it easily and saves our lots of time.

there are many sorting techniques, we’ll learn each of them.

### 01. Bubble Sorting

It is the easiest sorting technique to understand.It sorts the data by continuous swapping of adjacent elments if they are placed in wrong manner.

Example for better understanding-

1. 3,8,1,4 first 3 & 8 will be compared 3<8 no swapping

2. 3,8,1,4 8>1 swapping takes place between 8 & 1

3. 3,1,8,4 8>4 again swapping takes place between 8 & 4

4. 3,1,4,8 again we will compare 3 & 1 3>1 swap 3 & 1

5. 1,3,4,8 3<4 no swapping

6. 1,3,4,8 4<8 no swapping

our data was already sorted in 5th step but i wrote all the step because the compiler does not know if it is sorted in 5th step it’ll do all the steps assigned to it.

code in C

**#include <stdio.h>**

**int main()**

**{**

** int i,j,a,b,arr[5]={5,7,1,9,2};**

** for(i=0;i<4;i++)**

** {**

** for(j=0;j<4-i;j++)**

** {**

** if(arr[j]>arr[j+1])**

** {**

** a=arr[j];**

** arr[j]=arr[j+1];**

** arr[j+1]=a;**

** }**

** }**

** }**

** for(i=0;i<=4;i++)**

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

**}**

we can also use swap function for swapping

like

**#include <stdio.h>**

**int swap(int *a,int *b)**

**{**

** *a=*a+*b;**

** *b=*a-*b;**

** *a=*a-*b;**

**}**

**int main()**

**{**

** int i,j,a,b,arr[5]={5,7,1,9,2};**

** for(i=0;i<4;i++)**

** {**

** for(j=0;j<4-i;j++)**

** {**

** if(arr[j]>arr[j+1])**

** {**

** swap(&arr[j],&arr[j+1]);**

** }**

** }**

** }**

** for(i=0;i<=4;i++)**

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

**}**

But in this code there is a problem its time complexity is always O(n^2) either data is already sorted or not

means best case=worst case=Avg case time complexity=O(n^2)

means both the for loop will iterate n times n*n=n^2

which is not surprising as we know that sorting techniques must be efficient so that it saves our time and space

so we want to stop if we see that the the data is already sorted

how can we do that?

also keep in mind of space complexity

we will introduce a flag value here which will help us in reducing time complexity

which will tell the compiler that the data is already sorted no need to iterate further

So,think what should be the data type of this flag value?

its should be of char type why?

because int data type requires 4 bytes(short int 2 bytes) but char data type requires only 1 byte same with boolean data type ,so we’ll be using char data type for our flag value

so here is the modified bubble sort

**#include <stdio.h>**

**int swap(int *a,int *b)**

**{**

** *a=*a+*b;**

** *b=*a-*b;**

** *a=*a-*b;**

**}**

**int main()**

**{**

** int i,j,a,b,arr[5]={5,7,1,9,2};**

** char flag;**

** for(i=0;i<4;i++)**

** {**

** flag=‘N’**

** for(j=0;j<4-i;j++)**

** {**

** if(arr[j]>arr[j+1])**

** {**

** swap(&arr[j],&arr[j+1]);**

** flag==‘Y’**

** }**

** }**

** if(flag==‘N’)**

** break;**

** }**

** for(i=0;i<=4;i++)**

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

**}**

Now a big change occurred in this code guess what?

now our best case time complexity becomes of the order O(n)

Average and Worst time complexities are of the order O(n^2)

space complexity O(1)

Its Advantages is ,It is simple to write only few lines of code clean overview ,can be easily understood

space complexity is O(1)

best case time complexity O(n)

In place sorting,less memory required even no stack space it takes

Stable

Disadvantages:

worst time complexity and Average time complexity is O(n^2) which is not efficient as other algorithm having time complexity of O(nlogn)

where Bubble sort is used?

In Computer graphics it is popular for its capability to detect a very small error(like swap of just two elements)in almost sorted arrays and fix it with just linear complexity (2n).For example,it is used in a polygon filling algorithm,where bounding lines are sorted by their x co-ordinate at a specific scan line( a line parallel to x axis) and with incrementing y their order changes(two elements are swapped)only at intersection of two lines