Caută
  • oanaunciuleanu

Cycle Sort in C++




This algorithm is best suited when memory writes or swap operations are costly. It is a sorting algorithm that changes values in place. Each value is written either one time, when it has to be put in the correct position, or zero times, if it already is in its place.



// Cycle sort
#include <iostream>
using namespace std;


void cycleSort(int arrayOfNumbers[], int numberOfElements)
{
    int writes = 0;

    for (int cycle_start = 0; cycle_start <= numberOfElements - 2; cycle_start++)
    {
        // initialize the value of the first element
        int element = arrayOfNumbers[cycle_start];

        // Count all smaller values than our element
        int position = cycle_start;
        for (int i = cycle_start + 1; i < numberOfElements; i++)
        {
            if (arrayOfNumbers[i] < element)
            {
                position++;
            }
        }

        // If the element is already in the correct position
        if (position == cycle_start)
        {
            continue;
        }

        // Ignore duplicate elements
        while (element == arrayOfNumbers[position])
        {
             position += 1;
        }

        // Put the value in the right position
        if (position != cycle_start)
        {
            swap(element, arrayOfNumbers[position]);
            writes++;
        }

        // Cycle for the rest of elements
        while (position != cycle_start)
        {
            position = cycle_start;

            // Find position where we put the element
            for (int i = cycle_start + 1; i < numberOfElements; i++)
            {
                if (arrayOfNumbers[i] < element)
                {
                    position += 1;
                }
            }

            // Ignore duplicate elements
            while (element == arrayOfNumbers[position])
            {
                position += 1;
            }

            // Put the value in the right position
            if (element != arrayOfNumbers[position])
            {
                swap(element, arrayOfNumbers[position]);
                writes++;
            }
        }
    }
}

void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
  for (int i = 0; i < numberOfElements; ++i)
  {
    cout << arrayOfNumbers[i] << " ";
  }
  cout << endl;
}

int main()
{
  int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
  int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);

  cycleSort(arrayOfNumbers, numberOfElements);
  cout<<"The sorted array is: \n";
  printElementsOfArray(arrayOfNumbers, numberOfElements);
}

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.
Start Now