Bubble Sort

Bubble Sort

Bubble Sort is an elementary sorting algorithm. It works by repeatedly exchanging adjacent elements, if necessary. When no exchanges are required, the file is sorted.

SEQUENTIAL BUBBLESORT (A)

for i ← 1 to length [A] do
    for j ← length [A] downto i +1 do
        If A[A] < A[j-1] then
            Exchange A[j] ↔ A[j-1]

Here the number of comparison made

            1 + 2 + 3 + . . . + (n - 1) = n(n - 1)/2 = O(n²)

Clearly, the graph shows the n² nature of the bubble sort.
In this algorithm the number of comparison is irrespective of data set i.e., input whether best or worst.

 

Memory Requirement

Clearly, bubble sort does not require extra memory.

 

 

Implementation

void bubbleSort(int numbers[], int array_size)
{
  int i, j, temp;

  for (i = (array_size - 1); i >= 0; i--)
  {
    for (j = 1; j <= i; j++)
    {
      if (numbers[j-1] > numbers[j])
      {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}

Algorithm for Parallel Bubble Sort

 

PARALLEL BUBBLE SORT (A)

1. For k = 0 to n-2
2. If k is even then
3.     for i = 0 to (n/2)-1 do in parallel
4.         If A[2i] > A[2i+1] then
5.             Exchange A[2i] ↔ A[2i+1]
6. Else
7.     for i = 0 to (n/2)-2 do in parallel
8.         If A[2i+1] > A[2i+2] then
9.             Exchange A[2i+1] ↔ A[2i+2]
10. Next k

 

Parallel Analysis

Steps 1-10 is a one big loop that is represented n -1 times. Therefore, the parallel time complexity is O(n). If the algorithm, odd-numbered steps need (n/2) - 2 processors and even-numbered steps require (n/2) - 1 processors. Therefore, this needs O(n) processors.

Links

• Bubble Sort
• Bubble Sort (Ordinary)
• Bubble Sort (Ordinary, with User Input)
• Bubble Sort (More Efficient)
• Bubble Sort (More Efficient, with User Input)
• Simple Sort
• Simple Sort (with User Input)

Browse More Articles

Tweet

Written by sutha

We are Creative Blogger Theme Wavers which provides user friendly, effective and easy to use themes. Each support has free and providing HD support screen casting.