Implementation of Comb sort in Python
By Aayush DubeyHello Everyone!
In this tutorial, we will learn about Comb Sort and how to implement Comb Sort in Python.
The first algorithm which most of the students learn is Bubble Sort. It is simple and easy to implement. Comb Sort is nothing but an improvement over the Bubble Sort algorithm. In Bubble Sort, we compare each element with its next element and if it is bigger, we perform swap operation.
Comb Sort enhances the performance of Bubble Sort by taking a gap greater than 1. The algorithm starts with a large value of gap and decreases it by a factor of 1.3 in each iteration.
Steps to perform Comb Sort in Python
- Initially, the gap value is:
gap=length(list) - Create a while loop that runs till the value of gap is not equal to 1 or a swap was performed in the last iteration.
2.1 Set gap=int(gap/1.3). If the new gap value is less than one set gap =1.
2.2 Compare the elements with the new gap value using Bubble Sort.
2.3 If swap is performed set swapped=True. - Print the updated list.
Code
#Comb Sort in Python
#Initial list
arr = [ 28, -4, 108, 13, 404, 73, -26, 28, 0]
print("Origional List:",arr)
#Set gap
gap=len(arr)
swapped = True
temp=0
while gap!=1 or swapped == True:
swapped=False
# reducing gap by a factor of 1.3
gap = int(gap/1.3)
if gap < 1:
gap=1
for i in range(0, len(arr)-gap):
if arr[i] > arr[i + gap]:
temp=arr[i]
arr[i]=arr[i + gap]
arr[i + gap]=temp
swapped = True
#Sorted list
print ("Sorted List:",arr)
OUTPUT
Origional List: [28, -4, 108, 13, 404, 73, -26, 28, 0] Sorted List: [-26, -4, 0, 13, 28, 28, 73, 108, 404]
Hope you liked this tutorial!
Also read:
Leave a Reply