Data Structures (Bubble Sort in Data Structures)

-

 

Bubble sort 

👉 Bubble sort is the simplest sorting algorithm in data structures.
👉  In Bubble sort, Each element of the array is compared with its adjacent element.
👉  The algorithm processes the list in passes.
👉  A list with n elements requires n-1 passes for sorting.
👉  In every pass the highest element is places at the highest Index position in a list.

Technique :

👉  In Pass 1, A[0] is compared with A[1], A[1] is compared with A[2], A[2] is compared
with A[3] and so on. At the end of pass 1, the largest element of the list is placed at
the highest index of the list.
👉  In Pass 2, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the
end of Pass 2 the second largest element of the list is placed at the second highest
index of the list.
👉  In pass n-1, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At
the end of this pass. The smallest element of the list is placed at the first index of
the list.

Algorithm :

Step 1: Repeat Step 2 For i = 0 to N-1

Step 2: Repeat For J = i to N – i - 1

Step 3: IF A[J] > A[J+1]
SWAP A[J] and A[i]
[END OF INNER LOOP]
[END OF OUTER LOOP

Step 4: EXIT

Bubble sort complexity

1. Time Complexity

CaseTime Complexity
Best CaseO(n)
Average CaseO(n2)
Worst CaseO(n2)

2. Space Complexity

Space ComplexityO(1)
StableYES

Working of Bubble sort Algorithm:

Let the elements are -2,45,0,11,-9

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)

  1. Starting from the first index, compare the first and the second elements.
  2. If the first element is greater than the second element, they are swapped.
  3. Now, compare the second and the third elements. Swap them if they are not in order.
  4. The above process goes on until the last element.


After Completion of the first iteration the highest element of an array in the list is placed at the highest index position in the list.

2. Iteration-2


Put the 2nd largest element at the 2nd largest index position

In each iteration, the comparison takes place up to the last unsorted element.

After completion of the second iteration the second highest element of an array in the list is placed at the second highest index position in a list

3. Iteration-3



After completion of the second iteration the third highest element of an array in the list is placed at the third highest index position in a list

4. Iteration-4


The array is sorted if all elements are kept in the right order

After completion of the second iteration the fourth highest element of an array in the list is placed at the fourth highest index position in a list

👉 The array is sorted when all the unsorted elements are placed at their correct positions.
👉 In this example we are taking 5 elements in an array then the maximum number of iteration =( n-1) i.e (5-1) =4 iterations 

Implementation of Bubble sort

#include<stdio.h>
#include<conio.h>
void main()
{
int a[10],n,temp,i,j;
clrscr();
printf("Enter the size of an array");
scanf("%d",&n);
printf("Enter the values in to an array\n");
for(i=0;i<n;i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
//bubble sort logic
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("The array elements after implementing the bubble sort");
for(i=0;i<n;i++)
{
printf("\n%d",a[i]);
}
}

OTUPUT:







Comments

Post a Comment

Popular posts from this blog

String Functions in C Language(C Language)

-
  C String Functions There are many important string functions defined in "string.h" library. No. Function Description 1) strlen(string_name) returns the length of string name. 2) strcpy(destination, source) copies the contents of source string to destination string. 3) strcat(first_string, second_string) concats or joins first string with second string. The result of the string is stored in first string. 4) strcmp(first_string, second_string) compares the first string with second string. If both strings are same, it returns 0. 5) strrev(string) returns reverse string. 6) strlwr(string) returns string characters in lowercase. 7) strupr(string) returns string characters in uppercase. 8) strstr( st...
Read more

PHP Array Functions

-
  PHP  Array  Functions The array functions allow you to access and manipulate arrays. Simple and multi-dimensional arrays are supported. Function Description array() Creates an array array_column() Returns the values from a single column in the input array array_combine() Creates an array by using the elements from one "keys" array and one "values" array array_flip() Flips/Exchanges all keys with their associated values in an array array_pop() Deletes the last element of an array array_push() Inserts one or more elements to the end of an array array_replace() Replaces the values of the first array with the values from following arrays array_reverse() Returns an array in the reverse order array_search() Searches an array for a given value ...
Read more

Home Menu Options in Ms Word

-
Image
Microsoft Word Ribbon The following are the different options and tools listed in the Microsoft Word Ribbon for each of the tabs. Each section below is outlined first by the tab name, then by each section on the tab. Home tab                                    Undo Undo Typing  - Removes the last thing you typed. Repeat Typing  - If you accidentally hit undo typing, you can re-enter the previous text.                                      Clipboard Paste  - Pastes information from the  clipboard . Cut  - Removes information from the document and puts it in the clipboard. Copy  - Copies information from the document for the clipboard. Format Painter  - Applies formatting from another section of a docume...
Read more