Algorithms and Data Structures in Python: Bubble Sort and its Optimization

Introduction

Sorting is one of the most basic algorithm types and it appears quite often in interview. Among them, bubble sort is probably the most fundamental one. The naive bubble sort is usually not that efficient, however, it’s important to understand how it works and how it can be optimized.

Naive Bubble Sort

Native bubble sort used a nested loop to iterate through the target array, and swap each pair of adjacent elements if…