competitive-programming/Sorting/cycleSort.cpp at master · kothariji/competitive-programming · GitHub

History

74 lines (61 loc) · 1.67 KB

Raw

// C++ program to implement cycle sort

//added comments to understand code better

#include <iostream>

using namespace std;

// Function sort the array using Cycle sort

void cycleSort(int arr[], int n)

{

// count number of memory writes

int writes = 0;

// traverse array elements and put it to on

// the right place

for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++) {

// initialize item as starting point

int item = arr[cycle_start];

// Find position where we put the item. We basically

// count all smaller elements on right side of item.

int pos = cycle_start;

for (int i = cycle_start + 1; i < n; i++)

if (arr[i] < item)

pos++;

// If item is already in correct position

if (pos == cycle_start)

continue;

// ignore all duplicate elements

while (item == arr[pos])

pos += 1;

// put the item to it's right position

if (pos != cycle_start) {

swap(item, arr[pos]);

writes++;

}

// Rotate rest of the cycle

while (pos != cycle_start) {

pos = cycle_start;

// Find position where we put the element

for (int i = cycle_start + 1; i < n; i++)

if (arr[i] < item)

pos += 1;

// ignore all duplicate elements

while (item == arr[pos])

pos += 1;

// put the item to it's right position

if (item != arr[pos]) {

swap(item, arr[pos]);

writes++;

}

// cout << writes << endl ;

}

// Driver program to test above function

int main()

{

int arr[] = { 1, 8, 3, 9, 10, 10, 2, 4 };

int n = sizeof(arr) / sizeof(arr[0]);

cycleSort(arr, n);

cout << "After sort : " << endl;

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

return 0;

}

competitive-programming/Sorting/cycleSort.cpp at master · kothariji/competitive-programming · GitHub

Expand file tree

Breadcrumbs

cycleSort.cpp

Latest commit

History

Breadcrumbs

cycleSort.cpp

File metadata and controls