/* related posts with thumb nails */

procedure for Bubble sort:

Sorting is a technique used to arrange the elements of an array in either ascending order or descending order. To implement “sorting”, there are several logics such as “bubble sort”, “selection sort” and etc.

Consider the example:

int a[]={20,13,40,50,2}

After sorting the elements of the array in ascending order the elements will be {2,13,20,40,50}

Bubble sort logic: The simplest and the best known sorting technique is the bubble sort. To sort a sequence of n elements, bubble sort makes n - 1 passes thorough the data. In each pass two elements are compared and swapped if necessary. For example, the first and the second elements of the set are compared and exchanged if the first element is greater than the second element; next, the first and the third are compared and swapped if necessary and so on.

Complexity: The time complexity of bubble sort is shown below in three different cases and worst-case space complexity.

Worst Case

Best Case

Average Case

Worst case Space Complexity

O(n2)

O(n)

O(n2)

Example: The arrangement of elements is shown for each pass for a set of sample elements. It compares first element with the second, first with the third and so on. And, in every comparison, It also interchanges if first element is greater than the second. Notice that after the first pass the smallest element in the sequence has bubbled up into the first position. In This fashion it sorts all other elements one by one in each pass. In every pass, the sorted elements are ignored and comparison is continued for the remaining list.
The following example shows how bubble sort technique sorts elements in each pass.







Program:

The following program uses bubble sort algorithm to sort the elements of the array.

import java.io.*;

class BubbleSort

{

public static void main(String as[]) throws Exception

{

int i,j,n,t,a[]=new int[10];

InputStreamReader isr=new InputStreamReader(System.in);

BufferedReader br=new BufferedReader(isr);

System.out.println("How many values:");

n=Integer.parseInt(br.readLine());


System.out.println("Enter Values:");

for(i=0;i

a[i]=Integer.parseInt(br.readLine());

for(i=0;i

for(j=i+1;j

if(a[i]>a[j])

{

t=a[i];

a[i]=a[j];

a[j]=t;

}

System.out.println("After Sorting");

for(i=0;i

System.out.print("\t"+a[i]);

}

}

Output:

How many values: 4

Enter Values:

45

36

87

12

After Sorting:

12 36 45 87


Related Topics:

0 comments:

Post a Comment