CREATE OWN LIBRARY

Comb sort is a comparison based sorting technique almost similar to Bubble Sort. We can say that comb sort is a modified version of bubble sort. In bubble sort, an adjacent pairs of elements are compared and swapped (if needed), unlike the bubble sort in comb sort the elements are compared with a particular gap. 

The gap is decreased after each pass of sorting. The decreasing factor is 1.3 i.e. after each pass the gap is divided by 1.3 to get the new gap. It is an in-place sorting technique as it does not require any extra space to sort the data. The gapping of elements increases the efficiency of the sorting over bubble sort.

PROCEDURE WITH EXAMPLE:

Let take a 5 element array as follows:

The array is to be sorted in ascending order. For the first time, the gap is set to 5 i.e. the number of elements of the array.

Pass 1:

Before the first pass the array is:

In the first pass, the gap will be divided by 1.3.

So, the gap = 5/1.3 = 3. The elements at gap 3 will be compared with each other and will be swapped (if necessary).

Firstly, the starting index is 0 and it will be compared with the index (0 + 3) = 3.

So, here, 89 will be compared with 9, as 9 is lesser than 89 they will be swapped and we will get the array as:

After this, the element of index 1 will be compared with index (1 + 3) = 4, as -12 and 21 will be compared again but as -12 is already lesser than 21 then there will be no swap and the array will remain unchanged.

Next, index 2 should be compared with index (2 + 3) = 5 but as index 5 does not exist so the iteration will be ended and it will go for the next iteration.

Pass 2:

In the 2nd pass, the gap will be again divided by 1.3.

So, in this pass the gap = 3/1.3 = 2, so in a similar way, the elements at gap 2 will be compared with each other and will be swapped (if necessary).

At first, the element of starting index 0 will be compared with the element of the index (0 + 2) = 2. Here 9 is lesser than 17 so there will be no change.

After this the elements of index 1 and index (1 + 2) = 3 will be compared. In that case, -12 is already lesser than 89, so there will be no swapping. 

Next index 2 will be compared with index (2 + 2) = 4. Here now, 17 will be compared with 21, as 17 is lesser than 21 so there will be no swapping.

Next, index 3 should be compared with index (3 + 2) = 5 but as index 5 does not exist so the iteration will be ended and it will go for the next iteration.

Pass 3:

In the 3rd pass, the gap will be again divided by 1.3.

So, in this pass the gap = 2/1.3 = 1, so in a similar way, the elements at gap 1 will be compared with each other and will be swapped (if necessary).

For the first time index 0 will be compared with index (0 + 1) = 1. For this iteration, each pair of adjacent elements will be compared. Here 9 is compared with -12, as -12 is lesser than 9, so it will be swapped.

Here, the next two adjacent elements 9 and 17 will be compared and will not be swapped as they are already in sorted order. 

The next two adjacent elements are 17 and 89, they will be compared with each other but there will be no swapping. 

The last adjacent pair is 89 and 21, they will be compared with each other but as 89 is greater than 21 then there will be swapping and the array will be:

The array is already sorted after this pass.

For implementing the comb sort one flag is used in the loop to check whether any swapping has done or not. If there is any swapping then only the loop will go for the next pass. 

Hence, though the array is sorted we have to go for the next pass.

Pass 4:

Here the gap is 1/1.3 = 0.

That means each element of the array will be compared to itself only. There will be no swapping. So, the loop will stop executing. So, the final sorted array is:

INPUT: An unsorted array a[6,2,4,1,…………….,n]
OUTPUT: An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)

PROCESS:
Step 1: [Taking the inputs from the user]
	Read n
	for i=0 to n repeat
		read arr[i]
Step 2: [Sorting the elements using comb sort]
Set g<-n
Set f<-1
   	While g≠1 or f=1 repeat 
   	        Set g<-(g*10)/13
	        If g<1 then
         		Set g <- 1
	        [End of ‘If’]
     	       Set f<-0
    	       For i = 0 to n-g repeat 
         		If arr[i] > arr[i+g] then
            			Set t<-arr[i]
			Set arr[i]<-arr[i+g]
			Set arr[i+g]<-t
			Set f <- 1
      		[End of If]
	         [End of for loop]
      	[End of while loop]
   Step 3: [Displaying the array elements]
	For i=0 to n repeat
		Print arr[i]

Step 4: Stop.