Clasificación de peine

Comb Sort es principalmente una mejora sobre Bubble Sort. La ordenación de burbuja siempre compara valores adyacentes. Entonces todas las inversiones se eliminan una por una. Comb Sort mejora el Bubble Sort al usar un espacio de tamaño superior a 1. El espacio comienza con un valor grande y se reduce en un factor de 1,3 en cada iteración hasta que alcanza el valor 1. Por lo tanto, Comb Sort elimina más de una inversión . cuenta con un intercambio y funciona mejor que Bubble Sort.
Se ha encontrado empíricamente que el factor de reducción es 1.3 (al probar Combsort en más de 200,000 listas aleatorias) [Fuente: Wiki ]
Aunque en promedio funciona mejor que Bubble Sort, el peor de los casos sigue siendo O (n ² ).

diagrama de flujo

// C++ implementation of Comb Sort
#include<bits/stdc++.h>
using namespace std;
 
// To find gap between elements
int getNextGap(int gap)
{
    // Shrink gap by Shrink factor
    gap = (gap*10)/13;
 
    if (gap < 1)
        return 1;
    return gap;
}
 
// Function to sort a[0..n-1] using Comb Sort
void combSort(int a[], int n)
{
    // Initialize gap
    int gap = n;
 
    // Initialize swapped as true to make sure that
    // loop runs
    bool swapped = true;
 
    // Keep running while gap is more than 1 and last
    // iteration caused a swap
    while (gap != 1 || swapped == true)
    {
        // Find next gap
        gap = getNextGap(gap);
 
        // Initialize swapped as false so that we can
        // check if swap happened or not
        swapped = false;
 
        // Compare all elements with current gap
        for (int i=0; i<n-gap; i++)
        {
            if (a[i] > a[i+gap])
            {
                swap(a[i], a[i+gap]);
                swapped = true;
            }
        }
    }
}
 
// Driver program
int main()
{
    int a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
    int n = sizeof(a)/sizeof(a[0]);
 
    combSort(a, n);
 
    printf("Sorted array: \n");
    for (int i=0; i<n; i++)
        printf("%d ", a[i]);
 
    return 0;
}

// Java program for implementation of Comb Sort
class CombSort
{
    // To find gap between elements
    int getNextGap(int gap)
    {
        // Shrink gap by Shrink factor
        gap = (gap*10)/13;
        if (gap < 1)
            return 1;
        return gap;
    }
 
    // Function to sort arr[] using Comb Sort
    void sort(int arr[])
    {
        int n = arr.length;
 
        // initialize gap
        int gap = n;
 
        // Initialize swapped as true to make sure that
        // loop runs
        boolean swapped = true;
 
        // Keep running while gap is more than 1 and last
        // iteration caused a swap
        while (gap != 1 || swapped == true)
        {
            // Find next gap
            gap = getNextGap(gap);
 
            // Initialize swapped as false so that we can
            // check if swap happened or not
            swapped = false;
 
            // Compare all elements with current gap
            for (int i=0; i<n-gap; i++)
            {
                if (arr[i] > arr[i+gap])
                {
                    // Swap arr[i] and arr[i+gap]
                    int temp = arr[i];
                    arr[i] = arr[i+gap];
                    arr[i+gap] = temp;
 
                    // Set swapped
                    swapped = true;
                }
            }
        }
    }
 
    // Driver method
    public static void main(String args[])
    {
        CombSort ob = new CombSort();
        int arr[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
        ob.sort(arr);
 
        System.out.println("sorted array");
        for (int i=0; i<arr.length; ++i)
            System.out.print(arr[i] + " ");
 
    }
}
/* This code is contributed by Rajat Mishra */

# Python program for implementation of CombSort
 
# To find next gap from current
def getNextGap(gap):
 
    # Shrink gap by Shrink factor
    gap = (gap * 10)//13
    if gap < 1:
        return 1
    return gap
 
# Function to sort arr[] using Comb Sort
def combSort(arr):
    n = len(arr)
 
    # Initialize gap
    gap = n
 
    # Initialize swapped as true to make sure that
    # loop runs
    swapped = True
 
    # Keep running while gap is more than 1 and last
    # iteration caused a swap
    while gap !=1 or swapped == 1:
 
        # Find next gap
        gap = getNextGap(gap)
 
        # Initialize swapped as false so that we can
        # check if swap happened or not
        swapped = False
 
        # Compare all elements with current gap
        for i in range(0, n-gap):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap]=arr[i + gap], arr[i]
                swapped = True
 
 
# Driver code to test above
arr = [ 8, 4, 1, 3, -44, 23, -6, 28, 0]
combSort(arr)
 
print ("Sorted array:")
for i in range(len(arr)):
    print (arr[i],end=" ")
 
 
# This code is contributed by Mohit Kumra

// C# program for implementation of Comb Sort
using System;
 
class GFG
{
    // To find gap between elements
    static int getNextGap(int gap)
    {
        // Shrink gap by Shrink factor
        gap = (gap*10)/13;
        if (gap < 1)
            return 1;
        return gap;
    }
 
    // Function to sort arr[] using Comb Sort
    static void sort(int []arr)
    {
        int n = arr.Length;
 
        // initialize gap
        int gap = n;
 
        // Initialize swapped as true to
        // make sure that loop runs
        bool swapped = true;
 
        // Keep running while gap is more than
        // 1 and last iteration caused a swap
        while (gap != 1 || swapped == true)
        {
            // Find next gap
            gap = getNextGap(gap);
 
            // Initialize swapped as false so that we can
            // check if swap happened or not
            swapped = false;
 
            // Compare all elements with current gap
            for (int i=0; i<n-gap; i++)
            {
                if (arr[i] > arr[i+gap])
                {
                    // Swap arr[i] and arr[i+gap]
                    int temp = arr[i];
                    arr[i] = arr[i+gap];
                    arr[i+gap] = temp;
 
                    // Set swapped
                    swapped = true;
                }
            }
        }
    }
 
    // Driver method
    public static void Main()
    {
        int []arr = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
        sort(arr);
 
        Console.WriteLine("sorted array");
        for (int i=0; i<arr.Length; ++i)
            Console.Write(arr[i] + " ");
 
    }
}
 
// This code is contributed by Sam007

<script>
    // Javascript program for implementation of Comb Sort
     
    // To find gap between elements
    function getNextGap(gap)
    {
        // Shrink gap by Shrink factor
        gap = parseInt((gap*10)/13, 10);
        if (gap < 1)
            return 1;
        return gap;
    }
  
    // Function to sort arr[] using Comb Sort
    function sort(arr)
    {
        let n = arr.length;
  
        // initialize gap
        let gap = n;
  
        // Initialize swapped as true to
        // make sure that loop runs
        let swapped = true;
  
        // Keep running while gap is more than
        // 1 and last iteration caused a swap
        while (gap != 1 || swapped == true)
        {
            // Find next gap
            gap = getNextGap(gap);
  
            // Initialize swapped as false so that we can
            // check if swap happened or not
            swapped = false;
  
            // Compare all elements with current gap
            for (let i=0; i<n-gap; i++)
            {
                if (arr[i] > arr[i+gap])
                {
                    // Swap arr[i] and arr[i+gap]
                    let temp = arr[i];
                    arr[i] = arr[i+gap];
                    arr[i+gap] = temp;
  
                    // Set swapped
                    swapped = true;
                }
            }
        }
    }
     
    let arr = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0];
    sort(arr);
 
    document.write("sorted array" + "</br>");
    for (let i=0; i<arr.length; ++i)
      document.write(arr[i] + " ");
  
 // This code is contributed by decode2207
</script>