C Exercises: Sort numbers using Comb Sort method

C Programming Searching and Sorting Algorithm: Exercise-24 with Solution

Write a C program that sorts numbers using the Comb sort method.

From Wikipedia,
Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort.

Visualization of comb sort :

Animation credits : Jerejesse

Pseudocode

// Function to perform comb sort on an array
function combsort(array input) is
    // Initialize gap size
    gap := input.size
    // Set the gap shrink factor
    shrink := 1.3
    // Initialize flag to check if the array is sorted
    sorted := false

    // Main loop to continue sorting until the array is sorted
    loop while sorted = false
        // Update the gap value for the next comb
        gap := floor(gap / shrink)
        // If the gap is less than or equal to 1, set it to 1 and mark the array as sorted
        if gap ≤ 1 then
            gap := 1
            sorted := true // If there are no swaps this pass, we are done
        end if

        // A single "comb" over the input list
        i := 0
        // Loop to compare and swap elements with the given gap
        loop while i + gap < input.size // See Shell sort for a similar idea
            // Compare and swap elements if necessary
            if input[i] > input[i+gap] then
                swap(input[i], input[i+gap])
                // Mark the array as not sorted since a swap occurred
                sorted := false
                // If this assignment never happens within the loop,
                // then there have been no swaps and the list is sorted.
            end if

            // Move to the next pair of elements
            i := i + 1
        end loop
    end loop
end function

Sample Solution:

Sample C Code:

# include <stdio.h>
#include <stdlib.h>

#define SHRINK 1.3 // Set the gap shrink factor
int* comb_sort(int array_nums[], int size)
{
    int gap = size; // Initialize gap size
    while (gap > 1)  // gap = 1 means that the array is sorted
    {
        // Update the gap value for a next comb
		gap = gap / SHRINK;
        int i = 0;
        while ((i + gap) < size)
        {  // similiar to the Shell Sort
            if (array_nums[i] > array_nums[i + gap])
            {
                int tmp = array_nums[i];
                array_nums[i] = array_nums[i + gap];
                array_nums[i + gap] = tmp;
            }
            i++;
        }       
    }
    return array_nums; 
}

int main()
{
    int arr[100], i, n=0;    
	printf("Input number of elements you want to sort: ");
    scanf("%d", &n);
    if ( n >= 1)
    {
	printf("\nInput the numbers:\n");    
    for (i = 0; i < n; i++) scanf(" %d", &arr[i]);
    int* result_arra = comb_sort(arr, n);
    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
    {
        printf("%d ", result_arra[i]);
    }
    printf("\n");
    }
	return 0;
}

Sample Output:

Input number of elements you want to sort: 5

Input the numbers:
10 20 30 40 50 60 70 80 90
Sorted array:
10 20 30 40 50

--------------------------------
Process exited after 17.47 seconds with return value 0
Press any key to continue . . .

Flowchart:

C Programming Code Editor:

Previous: Write a C program that sort numbers using Multi-key quicksort method.
Next:Write a C program that sort numbers using Bucket sort method