Рубрики

Цикл сортировки

Циклическая сортировка — это алгоритм сортировки на месте, нестабильный алгоритм сортировки, сортировка сравнения, теоретически оптимальная с точки зрения общего числа записей в исходный массив.

  • Это оптимально с точки зрения количества записей в память. Он минимизирует количество операций записи в память для сортировки (каждое значение либо записывается ноль раз, если оно уже находится в правильной позиции, либо записывается один раз в правильную позицию.)
  • Он основан на идее, что сортируемый массив можно разбить на циклы. Циклы можно представить в виде графика. У нас есть n узлов и ребро, направленное от узла i к узлу j, если элемент по i-му индексу должен присутствовать по j-му индексу в отсортированном массиве.
    Cycle in arr [] = {2, 4, 5, 1, 3}

    Cycle in arr [] = {4, 3, 2, 1}

Мы один за другим рассмотрим все циклы. Сначала рассмотрим цикл, включающий первый элемент. Мы находим правильное положение первого элемента, помещаем его в правильное положение, скажем, j. Мы рассматриваем старое значение arr [j] и находим его правильную позицию, продолжаем делать это до тех пор, пока все элементы текущего цикла не будут размещены в правильной позиции, то есть мы не вернемся к начальной точке цикла.

Пояснение:

 arr[] = {10, 5, 2, 3}
 index =  0   1   2   3
cycle_start = 0 
item = 10 = arr[0]

Find position where we put the item  
pos = cycle_start
while (arr[i] < item)  
    pos++;

We put 10 at arr[3] and change item to 
old value of arr[3].
arr[] = {10, 5, 2, 10} 
item = 3 

Again rotate rest cycle that start with index '0' 
Find position where we put the item = 3 
we swap item with element at arr[1] now 
arr[] = {10, 3, 2, 10} 
item = 5

Again rotate rest cycle that start with index '0' and item = 5 
we swap item with element at arr[2].
arr[] = {10, 3, 5, 10 } 
item = 2

Again rotate rest cycle that start with index '0' and item = 2
arr[] = {2, 3,  5, 10}  

Above is one iteration for cycle_stat = 0.
Repeat above steps for cycle_start = 1, 2, ..n-2

CPP

// C ++ программа для реализации сортировки цикла
#include <iostream>

using namespace std;

  
// Функция сортировки массива с использованием Cycle sort

void cycleSort(int arr[], int n)

{

    // подсчитываем количество записей в память

    int writes = 0;

  

    // пройти элементы массива и поместить его в

    // правильное место

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

        // инициализируем элемент как начальную точку

        int item = arr[cycle_start];

  

        // Находим позицию, в которую мы помещаем предмет. Мы в основном

        // посчитаем все меньшие элементы на правой стороне элемента.

        int pos = cycle_start;

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

            if (arr[i] < item)

                pos++;

  

        // Если элемент уже находится в правильном положении

        if (pos == cycle_start)

            continue;

  

        // игнорируем все повторяющиеся элементы

        while (item == arr[pos])

            pos += 1;

  

        // положить элемент в правильное положение

        if (pos != cycle_start) {

            swap(item, arr[pos]);

            writes++;

        }

  

        // Повернуть остаток цикла

        while (pos != cycle_start) {

            pos = cycle_start;

  

            // Находим позицию, куда мы помещаем элемент

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

                if (arr[i] < item)

                    pos += 1;

  

            // игнорируем все повторяющиеся элементы

            while (item == arr[pos])

                pos += 1;

  

            // положить элемент в правильное положение

            if (item != arr[pos]) {

                swap(item, arr[pos]);

                writes++;

            }

        }

    }

  

    // Количество операций записи или замены памяти

    // cout << пишет << endl;

}

  
// Программа драйвера для проверки вышеуказанной функции

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;

}

Джава

// Java-программа для реализации сортировки цикла

  

import java.util.*;

import java.lang.*;

  

class GFG {

    // Функция сортировки массива с использованием Cycle sort

    public static void cycleSort(int arr[], int n)

    {

        // подсчитываем количество записей в память

        int writes = 0;

  

        // пройти элементы массива и поместить его в

        // правильное место

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

            // инициализируем элемент как начальную точку

            int item = arr[cycle_start];

  

            // Находим позицию, в которую мы помещаем предмет. Мы в основном

            // посчитаем все меньшие элементы на правой стороне элемента.

            int pos = cycle_start;

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

                if (arr[i] < item)

                    pos++;

  

            // Если элемент уже находится в правильном положении

            if (pos == cycle_start)

                continue;

  

            // игнорируем все повторяющиеся элементы

            while (item == arr[pos])

                pos += 1;

  

            // положить элемент в правильное положение

            if (pos != cycle_start) {

                int temp = item;

                item = arr[pos];

                arr[pos] = temp;

                writes++;

            }

  

            // Повернуть остаток цикла

            while (pos != cycle_start) {

                pos = cycle_start;

  

                // Находим позицию, куда мы помещаем элемент

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

                    if (arr[i] < item)

                        pos += 1;

  

                // игнорируем все повторяющиеся элементы

                while (item == arr[pos])

                    pos += 1;

  

                // положить элемент в правильное положение

                if (item != arr[pos]) {

                    int temp = item;

                    item = arr[pos];

                    arr[pos] = temp;

                    writes++;

                }

            }

        }

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

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

        int n = arr.length;

        cycleSort(arr, n);

  

        System.out.println("After sort : ");

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

            System.out.print(arr[i] + " ");

    }

}

  
// Код предоставлен Mohit Gupta_OMG <(0_o)>

python3

# Программа Python для реализации сортировки цикла

  

def cycleSort(array):

  writes = 0

    

  # Цикл по массиву, чтобы найти циклы для вращения.

  for cycleStart in range(0, len(array) - 1):

    item = array[cycleStart]

      

    # Найти, где поставить предмет.

    pos = cycleStart

    for i in range(cycleStart + 1, len(array)):

      if array[i] < item:

        pos += 1

      

    # Если элемент уже есть, это не цикл.

    if pos == cycleStart:

      continue

      

    # В противном случае, поместите элемент туда или сразу после любых дубликатов.

    while item == array[pos]:

      pos += 1

    array[pos], item = item, array[pos]

    writes += 1

      

    # Поверните остаток цикла.

    while pos != cycleStart:

        

      # Найти, где поставить предмет.

      pos = cycleStart

      for i in range(cycleStart + 1, len(array)):

        if array[i] < item:

          pos += 1

        

      # Поместите предмет туда или сразу после любых дубликатов.

      while item == array[pos]:

        pos += 1

      array[pos], item = item, array[pos]

      writes += 1

    

  return writes

    
# код водителя

arr = [1, 8, 3, 9, 10, 10, 2, 4 ]

n = len(arr) 

cycleSort(arr)

  

print("After sort : ")

for i in range(0, n) : 

    print(arr[i], end = ' ')

  
# Код предоставлен Mohit Gupta_OMG <(0_o)>

C #

// C # программа для реализации сортировки цикла

using System;

  

class GFG {

      

    // Функция сортировки массива с использованием Cycle sort

    public static void cycleSort(int[] arr, int n)

    {

        // подсчитываем количество записей в память

        int writes = 0;

  

        // пройти элементы массива и

        // положить его в нужное место

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

        {

            // инициализируем элемент как начальную точку

            int item = arr[cycle_start];

  

            // Находим позицию, в которую мы помещаем предмет.

            // Мы в основном считаем все меньшие элементы

            // на правой стороне элемента.

            int pos = cycle_start;

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

                if (arr[i] < item)

                    pos++;

  

            // Если элемент уже находится в правильном положении

            if (pos == cycle_start)

                continue;

  

            // игнорируем все повторяющиеся элементы

            while (item == arr[pos])

                pos += 1;

  

            // положить элемент в правильное положение

            if (pos != cycle_start) {

                int temp = item;

                item = arr[pos];

                arr[pos] = temp;

                writes++;

            }

  

            // Повернуть остаток цикла

            while (pos != cycle_start) {

                pos = cycle_start;

  

                // Находим позицию, куда мы помещаем элемент

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

                    if (arr[i] < item)

                        pos += 1;

  

                // игнорируем все повторяющиеся элементы

                while (item == arr[pos])

                    pos += 1;

  

                // положить элемент в правильное положение

                if (item != arr[pos]) {

                    int temp = item;

                    item = arr[pos];

                    arr[pos] = temp;

                    writes++;

                }

            }

        }

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

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

        int n = arr.Length;

          

        // вызов функции

        cycleSort(arr, n);

  

        Console.Write("After sort : ");

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

            Console.Write(arr[i] + " ");

    }

}

  
// Этот код предоставлен Нитином Митталом


Выход:

After sort : 
1 2 3 4 8 9 10 10 

Сложность времени : O (n 2 )
Худший случай: O (n 2 )
Средний случай: O (n 2 )
Лучший случай: O (n 2 )

Этот алгоритм сортировки лучше всего подходит для ситуаций, когда операции записи в память или подкачки являются дорогостоящими.

Ссылка:
https://en.wikipedia.org/wiki/Cycle_sort

Эта статья предоставлена Nishant Singh . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Цикл сортировки

0.00 (0%) 0 votes