C program to implement cycle sort algorithm

Here, we are going to learn how to implement cycle sort algorithm using C program?
Submitted by Nidhi, on August 16, 2021

Problem Solution:

Here, we will create an array of integers then we will read array elements from the user and implement a cycle sort algorithm to arrange array elements in ascending order.

Cycle Sort Algorithm:

Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.

Program:

The source code to implement the cycle sort algorithm is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to implement cycle sort algorithm

#include <stdio.h>

#define MAX 8

void cycleSort(int* arr)
{
    int tmp = 0;
    int item = 0;
    int pos = 0;

    int i = 0;
    int j = 0;
    int k = 0;

    while (i < MAX) {
        item = arr[i];
        pos = i;
        do {
            k = 0;
            for (j = 0; j < MAX; j++) {
                if (pos != j && arr[j] < item)
                    k++;
            }

            if (pos != k) {
                while (pos != k && item == arr[k])
                    k++;

                tmp = arr[k];
                arr[k] = item;
                item = tmp;

                pos = k;
            }

        } while (pos != i);
        i++;
    }
}

int main()
{
    int arr[MAX];
    int i = 0;

    printf("Enter array elements:\n");
    while (i < MAX) {
        printf("Element[%d]: ", i);
        scanf("%d", &arr[i]);
        i++;
    }

    cycleSort(arr);

    printf("Sorted Array: \n");
    i = 0;
    while (i < MAX) {
        printf("%d ", arr[i]);
        i++;
    }
    printf("\n");

    return 0;
}

Output:

Enter array elements:
Element[0]: 13 
Element[1]: 56
Element[2]: 75
Element[3]: 98
Element[4]: 45
Element[5]: 63
Element[6]: 34
Element[7]: 67
Sorted Array: 
13 34 45 56 63 67 75 98

Explanation:

Here, we created two functions cycleSort() and main(). The cycleSort() function is used to arrange array elements in ascending order.

In the main() function, we created an array of integers arr. Then we sorted the elements of the array using the cycleSort() function and printed the sorted array on the console screen.

Comments and Discussions!

Top MCQs

Top Programs/Examples