About  Contact

Sorting

Sorting is one of the important operations done on array. Here the array elements are arranged in ascending or descending order. In this part we will study three different sorting techniques

• Bubble sort
• Selection sort
• Insertion sort

Bubble Sort:Let us start with an example - 1, 4, -1, 0, -8, 10, 3, 7, -2, 9, is our array content and we want to arrange it in ascending order. First of all the first number (1) is considered (bubbled) first as shown in the figure below. Then it is campared with the adjacent number (4), since we want to arrange them in ascending order so we need not change the position of the numbers (means the two 1, 4 numbers are already arranged). Next the bubble move to the next number (4) then we compare it with its adjacent number (-1) this time we have to change its position so 1 takes the position of 4 and 4 takes the position of 1 (1, 4). This process goes on till the bubble moves to the second last number. At the end of this process see that the largest number takes it position in the sorted array. This is called pass one. In the second pass it bubbles the first number and same process is applied and it goes till the third number from the last, at the end of this pass second largest number takes it position in the sorted array. In this way there will be n-1 passes, where n is the number of numbers in the array. See the figures - the first figure shows how each pass is carried out, second figure shows all the passes.



Now let us write the function to sort an array having 10 integers-

Program-70

#include <iostream.h>

void bubbleSort(int a[], int n){
   int i, j, t;
   for(i=1; i<=n-1; i++){
      for(j=0; j<=(n-1)-i; j++){
          if(a[j]>a[j+1]){
              t=a[j];
              a[j]=a[j+1];
              a[j+1]=t;
          }
      }
   } 
}

void main(){
  int a[10], i;
  for(i=0; i<= 9; i++){
	  cout<<"Enter the element :"<<i+1<<":";
     cin>>a[i];
  }
  bubbleSort(a,10);
  cout<<"The sorted array is as under:\n";
  for(i=0; i<=9; i++){
     cout<<a[i]<<"  ";
  }
}

In the "main()" function see that 10 is passed as number of element. In the function "bubbleSort()" the first loop counts the number of passes and the second loop bubbles the numbers, if necessary changes the position of the numbers. See that the second loop ranges from 0 (first number) to the second last number (n-1 is equal to 9, 9-i, i.e 9-1 equal to 8 which is the position of the second last number in the first pass); in the second pass it ranges from 0 to third last number and so on.

---