What is Sorting in Data Structures ? Selection Sorting,Bubble Sorting

Sorting :Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.

Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily.

Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy.

For example, suppose we have a record of students, every such record will have the following data:

Roll No.
Name
Age
Class

Types of Sorting Techniques

There are many types of Sorting techniques, differentiated by their efficiency and space requirements. Following are some sorting techniques which we will be covering in next sections.

Bubble Sort
Insertion Sort
Selection Sort
Quick Sort
Merge Sort
Heap Sort

How Bubble Sort Works?

We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we’re keeping it short and precise.

Bubble sort starts with very first two elements, comparing them to check which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one iteration, the array should look like this −

To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this −

Notice that after each iteration, at least one value moves at the end.

And when there’s no swap required, bubble sorts learns that an array is completely sorted.

Now we should look into some practical aspects of bubble sort.

We assume list is an array of n elements. We further assume that swap function swaps the values of the given array elements.

Selection Sorting

for(int i=0; i<4; i++)
{
for(int j=0; j<4; j++)
{
if(array[j]>array[j+1])
{
temp=array[j+1];
array[j+1]=array[j];
array[j]=temp;
}
}
}

Bubble Sorting

for (int i = 0; i < 4; i++)
for (int j = i; j < 4; j++)
if (data[i] > data[j+1])
{ tmp = data[j+1];
data[j+1]=data[i];
data[i] = tmp;
}

Bubble sorting in Linked List

void sorting()
{
for(temp=start;temp->ptr!=NULL;temp=temp->ptr)
{
for(temp1=start;temp1->ptr!=NULL;temp1=temp1->ptr)
{
if(temp1->data > temp1->ptr->data)
{
int temp2=temp1->data;
temp1->data=temp1->ptr->data;
temp1->ptr->data=temp2;
}}}}

Selection sorting in Linked List

void sorting()
{
for(temp=start;temp->ptr!=NULL;temp=temp->ptr)
{
for(temp1=temp->ptr;temp1!=NULL;temp1=temp1->ptr)
{
if(temp->data > temp1->data)
{ int tmp;
tmp=temp->data;
temp->data=temp1->data;
temp1->data=tmp;
}}}}