Sorting algorithms for arrays

How many types of sorting Algorithms for arrays? Why we need to sort the numbers?  In our daily life there are many cases where we need to sort (arrange in ascending or descending order) the data. For example, in a library we want to place the books in racks in specific order or we want to compile the result to see which students is on top. So sorting algorithms are necessary for such purposes.

Types of sorting algorithms

Different sorting algorithms that are available are given as:

• Bubble sort
• Quick sort
• merge sort
• selection sort
• insertion sort
• Radix Sort

What is the Bubble Sort? 

This sorting algorithm is not considered much efficient specially when we have larger numbers to sort. It takes the approach of comparing two consecutive numbers. If the two numbers are not in order (ascending or descending) then they are swapped otherwise they remain as it is and the index value is incremented for the comparison of next two numbers. Consider the following list of numbers and see how bubble sort works on it.

-2 5 0 9 3 1 7

First two numbers will be compared. As -2 is smaller than 5 so they remain as it is. Nest 5 and 0 are compared and they are swapped as 5 is greater than 0.

-2 5 0 9 3 1 7

After swapping them we will have -2 0 5 9 3 1 7

so it goes like that

1st Phase

-2 0 5 9 3 1 7 (no change)

-2 5 0 9 3 1 7 (comparison)

-2 5 0 3 9 1 7 (swapped)

-2 5 0 3 1 9 7 (comparison)

-2 5 0 3 9 1 7 (swapped)

-2 5 0 3 9 1 7 (no change)

If we notice here, the array is not yet sorted so it continues again and again.

2nd phase

-2 5 0 3 9 1 7 (no change)

-2 5 0 3 9 1 7 (comparison)

-2 0 5 3 9 1 7 (swapped)

-2 5 0 3 9 1 7 (comparison)

-2 5 0 3 9 1 7 (no change)

-2 5 0 3 9 1 7 (comparison and no change)

-2 5 0 3 9 1 7 (comparison)

-2 5 0 3 1 9 7 (swapped)

-2 5 0 3 1 9 7 (comparison and no change)

3rd phase

-2 5 0 3 1 9 7 (comparison and no change)

-2 5 0 3 1 9 7 (comparison)

-2 0 5 3 1 9 7 (changed)

-2 0 5 3 1 9 7 (comparison)

-2 0 3 5 1 9 7 (swapped)

-2 0 3 5 1 9 7 (comparison)

-2 0 3 1 5 9 7 (swapped)

-2 0 3 5 1 9 7 (comparison and no swap)

-2 0 3 5 1 9 7 (comparison and no swap)

4th phase

-2 0 3 5 1 9 7 (comparison and no swap)

-2 0 3 5 1 9 7 (comparison and no swap)

-2 0 3 5 1 9 7 (comparison and no swap)

-2 0 3 5 1 9 7 (comparison)

-2 0 3 1 5 9 7 (swapped)

-2 0 3 1 5 9 7 (comparison and no swap)

-2 0 3 1 5 9 7 (comparison and no swap)

5th phase

-2 0 3 1 5 9 7 (comparison and no swap)

-2 0 3 1 5 9 7 (comparison and no swap)

-2 0 3 1 5 9 7 (comparison)

-2 0 1 3 5 9 7 (swapped)

-2 0 1 3 5 9 7 (comparison and no swap)

-2 0 1 3 5 9 7 (comparison and no swap)

-2 0 1 3 5 9 7 (comparison)

-2 0 1 3 5 7 9 (swapped)

Although the array has been sorted but this algorithm still runs for n-1 times where n is the number of elements in an array.

6th phase

-2 0 1 3 5 7 9 (comparison and no swap)

-2 0 1 3 5 7 9 (comparison and no swap)

-2 0 1 3 5 7 9 (comparison and no swap)

-2 0 1 3 5 7 9 (comparison and no swap)

-2 0 1 3 5 7 9 (comparison and no swap)

-2 0 1 3 5 7 9 (comparison and no swap)

C++ code for Bubble Sort Algorithm

Write down a C++ code for sorting array elements in the ascending order.

Answer

void main()

{

clrscr();

int a[6], temp;

cout<<“elements of array before sorting”<<endl;

for(int i=0;i<6;i++)

{

cin>>a[i]

}

for(int j=0;j<6;j++)

{

for(int k=0;k<5;k++)

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

{

temp=a[j+1];

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

a[j]=temp;

}

}

}

cout<<“elements after sorting are”<<endl;

for(int u=0;u<6;u++)

{

cout<<a[u]<<endl;

}

Selection Sort:

The next algorithm for sorting the array elements is selection sort. As it name indicates it will sort the elements by “selecting” the minimum element from the array under consideration. Hence, at the end the array will be sorted in the ascending order. For arranging the array elements in descending order we will have to find the “maximum” element first and then we can extend this approach again for selecting the maximum element in rest of the array. 

Also read here 

• what is the scope of a variable? How you define the lifetime of local and global variables in programming?
• How do you define classes and objects in C++?
• what is the switch Statement in C++?
• How many types of inheritance are here in C++?
• What are the decision making statements in C++?
• How to use rand() function in C++?
• What are the strings in C++?
• Design a matrix calculator in c++
• How to define structures in C++? What is meant by structures within structures?
• How to define and call functions in C++?
• What is the difference between if and if-else statement ?
• What is the inheritance in C++?