Data Structure: Bubble Sort

Unknown 7:03 AM , , , No comments

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(n2)
  

Clearly, the graph shows the n2 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.

No comments :

Post a Comment

Subscribe to: Post Comments ( Atom )