top of page
Caută
Poza scriitoruluioanaunciuleanu

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);
}

48 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no...

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

ความคิดเห็น


bottom of page