- Arranging the data in ascending or descending order is known as
**sorting.** - Sorting is very important from the point of view of our practical life.
- The best example of sorting can be phone numbers in our phones. If, they are not maintained in an alphabetical order we would not be able to search any number effectively.

1. Bubble sort

2. Selection sort

3. Insertion sort

4. Quick sort

5. Merge sort

6. Heap sort

7. Radix sort

8. Shell sort

Generally a sort is classified as

It can be

a) Time required by a programmer for coding a particular sorting program.

b) The machine time required for running the program.

c) Space required by the program.

- This is one of the most simple algorithm.
- The logic for this sort is that if the numbers are to be arranged in an ascending order then the largest number will be pushed at the end of the list.
- This process will be continued till all the numbers are placed in the proper order.
- Every number will be scanned with the succeeding number and they are swapped if the top number is larger than the succeeding number.
- If the list is scanned once, it is called as a pass.
- Even if the list is passed once only the largest number is pushed at the end the rest of the numbers are still not placed.
- For this, we may have to repeat this step many times to get the list sorted properly.

void bubblesort(int a[ ], int n)

{

int p, c, i, j, temp;

p = n-1;

c = n;

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

{

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

{

if(a[j] > a[j+1])

{

temp = a[j];

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

a[j+1] = temp;

}

}

}

}

- This method of sorting is faster than the bubble sort as the movement of data is minimized.
- Say we want to arrange data in ascending order, the largest number is selected and placed at the end of the list.
- When the next pass takes place the second largest number is selected and placed second last.
- This process is repeated until all the elements are placed in the correct order.
- With each pass the elements are reduced by 1 as one element is sorted and placed in a position.

void selectionsort (int x[], int n)

{

int i, index, j, l;

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

{

l=x[1];

i=1;

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

{

if(x[j] > l)

{

l = x[j];

index = j;

}

}

x[index] = x[i];

x[i]=l;

}

}

a) Simple insertion sort

b) List insertion sort

c) Insertion sort using binary search.

- It is more efficient than bubble sort.
- The logic for this is that every element is picked up and inserted in the proper place i.e. if we pick up one element for inserting, all the other elements will be put in the proper order.

void insertionsort (int x[], int n)

{

int i,j,k;

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

{

k=x[i];

for(j=i-1; j>=i && k<x[j]; j--)

{

x[j+1] = x[j];

}

x[j+1] = y;

}

}