Comb Sort is mainly an improvement over Bubble Sort. Bubble sort always compares adjacent values. So all inversions are removed one by one. Comb Sort improves on Bubble Sort by using gap of size more than 1. The gap starts with a large value and shrinks by a factor of 1.3 in every iteration until it reaches the value 1. Thus Comb Sort removes more than one inversion counts with one swap and performs better than Bublle Sort.
The shrink factor has been empirically found to be 1.3 (by testing Combsort on over 200,000 random lists)
Although, it works better than Bubble Sort on average, worst case remains O(n2).
Screenshots:
Code:
import java.io.*;
import java.util.*;
class Solution {
public static void main (String[] args) {
Scanner sc= new Scanner(System.in);
int m = sc.nextInt();
for(int mi=0;mi<m;mi++){
int n = sc.nextInt();
int [] ar= new int [n];
for(int size=0;size<n;size++){
ar[size]=sc.nextInt();
}
CombSort(ar,n);
for (int k=0; k<ar.length; k++)
System.out.print(ar[k] + " ");
System.out.println();
}
}
public static void CombSort(int []ar,int n){
int gap=n;
boolean swapped= true;
while(gap!=1||swapped==true){
gap= getNextgap(gap);
swapped=false;
for (int i=0; i<n-gap; i++)
{
if (ar[i] > ar[i+gap])
{
// Swap arr[i] and arr[i+gap]
int temp = ar[i];
ar[i] = ar[i+gap];
ar[i+gap] = temp;
// Set swapped
swapped = true;
}
}
}
}
public static int getNextgap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;
if (gap < 1)
return 1;
return gap;
}
}
Time: 0.09 sec
Comments
Post a Comment