Skip to main content

Python Bubble Sort

Here you will learn about Python bubble sort.

In Bubble Sort, all we have to do is pick the first two elements of the array and compare them if first one is greater than the second one then swap them. After it, pick next two elements and compare them and so on.

After travelling the array once, the greatest number will be placed on the last index.

To sort entire array we have to travel the array (n-1) times where n is the length of the array.

Python Bubble Sort

Example

Let’s  consider we have an array:

21,14,18,25,9

Python Bubble Sort 1

Pass-1:

As we know 14 is less than 21 so swap them and pick next two elements.

Python Bubble Sort 2

Again 18 is less than 21, so we have to swap them, and pick next two elements.

Python Bubble Sort 3

25 is greater than 21 so we doesn’t need to swap them, now pick next two elements

Python Bubble Sort 4

9 is less than 25, swap them.

Python Bubble Sort 5

So here we have been traveling array once and the largest number is placed at last index.

As we mentioned above that to sort the entire array we have to travel array (n-1) times, where n is the length of array.

So we name it Pass-1.

Let’s start Pass-2.

Pass-2:

This time we doesn’t need to check the last index, because it is sorted after Pass-1.

Python Bubble Sort 6

Python Bubble Sort 7 Python Bubble Sort 8

Python Bubble Sort 9

After completing Pass-2 the last two elements have been sorted. So in Pass-3 we don’t have to check them.

Pass-3:Python Bubble Sort 10

Python Bubble Sort 11

Python Bubble Sort 12

After completing Pass-3 , the last 3 elements of array are in sorted order.

Pass-4:

Python Bubble Sort 13

Python Bubble Sort 14

We have  been traveled array (n-1) times. Array has been sorted.

As after every step the largest element tend to move up into the correct order like bubbles rising to the surface, that’s why it is called as BUBBLE SORT.”

Algorithm

we have an array Arr[n], where n is number of elements.

Step:1-  set pass =1

Step:2- set index = 0

Step:3- if Arr[index]>Arr[index+1]

Then swap Arr[index] with Arr[index+1]

Increase index by 1.

Step:4- Go to Step:3 till index<=n-pass-1

[pass will prevent  checking of the sorted element again]

Step:5- increase pass by 1 and go to Step:2 till pass<=n-1

Program for Bubble Sort in Python

Arr = [21,14,18,25,9]
n = len(Arr)   #length

Pass = 1

while(Pass<=n-1):
  index = 0
  while(index<=n-Pass-1):
    if Arr[index]>Arr[index+1]:
          Arr[index],Arr[index+1] = Arr[index+1],Arr[index]    #swapping
  
    index = index+1
  
  Pass =Pass + 1

for item in Arr:
  print item,

Output

9 14 18 21 25

The post Python Bubble Sort appeared first on The Crazy Programmer.



from The Crazy Programmer https://www.thecrazyprogrammer.com/2017/12/python-bubble-sort.html

Comments

Popular posts from this blog

dotnet sdk list and dotnet sdk latest

Can someone make .NET Core better with a simple global command? Fanie Reynders did and he did it in a simple and elegant way. I'm envious, in fact, because I spec'ed this exact thing out in a meeting a few months ago but I could have just done it like he did and I would have used fewer keystrokes! Last year when .NET Core was just getting started, there was a "DNVM" helper command that you could use to simplify dealing with multiple versions of the .NET SDK on one machine. Later, rather than 'switching global SDK versions,' switching was simplified to be handled on a folder by folder basis. That meant that if you had a project in a folder with no global.json that pinned the SDK version, your project would use the latest installed version. If you liked, you could create a global.json file and pin your project's folder to a specific version. Great, but I would constantly have to google to remember the format for the global.json file, and I'd constan...

Rail Fence Cipher Program in C and C++[Encryption & Decryption]

Here you will get rail fence cipher program in C and C++ for encryption and decryption. It is a kind of transposition cipher which is also known as zigzag cipher. Below is an example. Here Key = 3. For encryption we write the message diagonally in zigzag form in a matrix having total rows = key and total columns = message length. Then read the matrix row wise horizontally to get encrypted message. Rail Fence Cipher Program in C #include<stdio.h> #include<string.h> void encryptMsg(char msg[], int key){ int msgLen = strlen(msg), i, j, k = -1, row = 0, col = 0; char railMatrix[key][msgLen]; for(i = 0; i < key; ++i) for(j = 0; j < msgLen; ++j) railMatrix[i][j] = '\n'; for(i = 0; i < msgLen; ++i){ railMatrix[row][col++] = msg[i]; if(row == 0 || row == key-1) k= k * (-1); row = row + k; } printf("\nEncrypted Message: "); for(i = 0; i < key; ++i) f...

Data Encryption Standard (DES) Algorithm

Data Encryption Standard is a symmetric-key algorithm for the encrypting the data. It comes under block cipher algorithm which follows Feistel structure. Here is the block diagram of Data Encryption Standard. Fig1: DES Algorithm Block Diagram [Image Source: Cryptography and Network Security Principles and Practices 4 th Ed by William Stallings] Explanation for above diagram: Each character of plain text converted into binary format. Every time we take 64 bits from that and give as input to DES algorithm, then it processed through 16 rounds and then converted to cipher text. Initial Permutation: 64 bit plain text goes under initial permutation and then given to round 1. Since initial permutation step receiving 64 bits, it contains an 1×64 matrix which contains numbers from 1 to 64 but in shuffled order. After that, we arrange our original 64 bit text in the order mentioned in that matrix. [You can see the matrix in below code] After initial permutation, 64 bit text passed throug...