logo

TechCodeview

Sortare pe ciclu

Încercați-l pe GfG Practice Sortare pe ciclu' title=

Cycle sort este un algoritm de sortare instabil la locul lui, care este deosebit de util atunci când sortați tablouri care conțin elemente cu un interval mic de valori. A fost dezvoltat de W. D. Jones și publicat în 1963.

Ideea de bază din spatele sortării ciclului este de a împărți matricea de intrare în cicluri în care fiecare ciclu este format din elemente care aparțin aceleiași poziții în matricea de ieșire sortată. Algoritmul efectuează apoi o serie de schimburi pentru a plasa fiecare element în poziția sa corectă în cadrul ciclului său până când toate ciclurile sunt complete și matricea este sortată.

Iată o explicație pas cu pas a algoritmului de sortare pe ciclu:

  1. Începeți cu o matrice nesortată de n elemente.
  2. Inițializați un ciclu variabil Start la 0.
  3. Pentru fiecare element din matrice, comparați-l cu orice alt element din dreapta sa. Dacă există elemente mai mici decât elementul curent, increment cycleStart.
  4. Dacă cycleStart este încă 0 după compararea primului element cu toate celelalte elemente, treceți la următorul element și repetați pasul 3.
  5. Odată ce este găsit un element mai mic, schimbați elementul curent cu primul element din ciclul său. Ciclul este apoi continuat până când elementul curent revine la poziția inițială.

Repetați pașii 3-5 până când toate ciclurile au fost finalizate.



Matricea este acum sortată.

Unul dintre avantajele sortării pe ciclu este că are o amprentă de memorie redusă, deoarece sortează matricea la locul său și nu necesită memorie suplimentară pentru variabile sau buffer-uri temporare. Cu toate acestea, poate fi lent în anumite situații, în special atunci când matricea de intrare are o gamă largă de valori. Cu toate acestea, sortarea în ciclu rămâne un algoritm de sortare util în anumite contexte, cum ar fi atunci când sortați matrice mici cu intervale de valori limitate.

Cycle sort este un algoritm de sortare in loc algoritm de sortare instabil și un sort de comparație care este teoretic optim în ceea ce privește numărul total de scrieri în tabloul original. 
 

testarea de compatibilitate
  • Este optim din punct de vedere al numărului de scrieri în memorie. Ea minimizează numărul de scrieri în memorie pentru a sorta (Fiecare valoare este fie scrisă de zero ori dacă este deja în poziția corectă, fie scrisă o dată în poziția corectă.)
  • Se bazează pe ideea că matricea de sortat poate fi împărțită în cicluri. Ciclurile pot fi vizualizate ca un grafic. Avem n noduri și o muchie îndreptată de la nodul i la nodul j dacă elementul de la al-lea indice trebuie să fie prezent la al-lea indice din tabloul sortat. 
    Ciclu în arr[] = {2 4 5 1 3} 
     
Sortare pe cicluCiclu în arr[] = {2 4 5 1 3}
  • Ciclu în arr[] = {4 3 2 1} 
     
Ciclu în arr[] = {4 3 2 1} 


Considerăm unul câte unul toate ciclurile. Luăm în considerare mai întâi ciclul care include primul element. Găsim poziția corectă a primului element și o plasăm în poziția corectă, să zicem j. Luăm în considerare vechea valoare a lui arr[j] și găsim poziția sa corectă, continuăm să facem asta până când toate elementele ciclului curent sunt plasate în poziția corectă, adică nu ne întoarcem la punctul de pornire al ciclului.

fcfs

Pseudocod: 

Begin  
for  
start:= 0 to n - 2 do  
key := array[start]  
location := start  
for i:= start + 1 to n-1 do  
 if array[i] < key then  
 location: =location +1  
done  
if location = start then  
 ignore lower part go for next iteration  
while key = array[location] do  
 location: = location + 1  
done  
if location != start then  
 swap array[location] with key  
while location != start do  
 location start  
  
  
for i:= start + 1 to n-1 do  
 if array[i] < key then  
 location: =location +1  
done  
while key= array[location]  
 location := location +1  
 if key != array[location]  
 Swap array[location] and key  
 done  
 done  
End

Explicatie:  

 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  
i=pos+1  
while(i  
if (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

Mai jos este implementarea abordării de mai sus:

CPP 
// C++ program to implement cycle sort #include    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++;  }  }  }  // Number of memory writes or swaps  // 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; }
Java 
// Java program to implement cycle sort import java.util.*; import java.lang.*; class GFG {  // Function sort the array using Cycle sort  public static 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) {  int temp = item;  item = arr[pos];  arr[pos] = temp;  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]) {  int temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  }  }  }  // Driver program to test above function  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] + ' ');  } } // Code Contributed by Mohit Gupta_OMG <(0_o)>
Python3 
# Python program to implement cycle sort def cycleSort(array): writes = 0 # Loop through the array to find cycles to rotate. for cycleStart in range(0 len(array) - 1): item = array[cycleStart] # Find where to put the item. pos = cycleStart for i in range(cycleStart + 1 len(array)): if array[i] < item: pos += 1 # If the item is already there this is not a cycle. if pos == cycleStart: continue # Otherwise put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos] item = item array[pos] writes += 1 # Rotate the rest of the cycle. while pos != cycleStart: # Find where to put the item. pos = cycleStart for i in range(cycleStart + 1 len(array)): if array[i] < item: pos += 1 # Put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos] item = item array[pos] writes += 1 return writes # driver code  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 = ' ') # Code Contributed by Mohit Gupta_OMG <(0_o)>
C# 
// C# program to implement cycle sort using System; class GFG {    // Function sort the array using Cycle sort  public static 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) {  int temp = item;  item = arr[pos];  arr[pos] = temp;  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]) {  int temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  }  }  }  // Driver program to test above function  public static void Main()  {  int[] arr = { 1 8 3 9 10 10 2 4 };  int n = arr.Length;    // Function calling  cycleSort(arr n);  Console.WriteLine('After sort : ');  for (int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');  } } // This code is contributed by Nitin Mittal
JavaScript 
<script> // Javascript program to implement cycle sort  // Function sort the array using Cycle sort  function cycleSort(arr n)  {    // count number of memory writes  let writes = 0;    // traverse array elements and put it to on  // the right place  for (let cycle_start = 0; cycle_start <= n - 2; cycle_start++)  {    // initialize item as starting point  let item = arr[cycle_start];    // Find position where we put the item. We basically  // count all smaller elements on right side of item.  let pos = cycle_start;  for (let 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)  {  let temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }    // Rotate rest of the cycle  while (pos != cycle_start)  {  pos = cycle_start;    // Find position where we put the element  for (let 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]) {  let temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  }  }  }   // Driver code   let arr = [ 1 8 3 9 10 10 2 4 ];  let n = arr.length;  cycleSort(arr n);    document.write('After sort : ' + '  
');  for (let i = 0; i < n; i++)  document.write(arr[i] + ' ');    // This code is contributed by susmitakundugoaldanga. </script>

Ieșire 
After sort : 1 2 3 4 8 9 10 10

Analiza complexității timpului : 

  • Cel mai rău caz: Pe2) 
  • Caz mediu: Pe2) 
  • Cel mai bun caz: Pe2)

Spațiu auxiliar: O(1)

  • Complexitatea spațiului este constantă, deoarece acest algoritm este în vigoare, astfel încât nu utilizează nicio memorie suplimentară pentru sortare.

Metoda 2: Această metodă este aplicabilă numai atunci când valorile sau elementele de matrice date sunt în intervalul de la 1 la N sau de la 0 la N. În această metodă nu este nevoie să rotim o matrice

10 ml este cât

Abordare: Toate valorile matricei date ar trebui să fie în intervalul de la 1 la N sau de la 0 la N. Dacă intervalul este de la 1 la N  atunci poziția corectă a fiecărui element de matrice va fi indicele == valoare-1, adică înseamnă că la a 0-a valoare a indexului va fi 1, în mod similar, la prima poziție a indexului, valoarea va fi 2 și așa mai departe până la a-a valoare.

în mod similar, pentru valorile de la 0 la N, poziția corectă a indexului fiecărui element sau valoare de matrice va fi aceeași cu valoarea sa, adică la al 0-lea indice 0 va fi acolo prima poziție 1 va fi acolo.

Explicatie:  

arr[] = {5 3 1 4 2}  
index = 0 1 2 3 4  
  
i = 0;  
while( i < arr.length)  
 correctposition = arr[i]-1;   
   
 find ith item correct position  
 for the first time i = 0 arr[0] = 5 correct index of 5 is 4 so arr[i] - 1 = 5-1 = 4  
   
   
 if( arr[i] <= arr.length && arr[i] != arr[correctposition])  
   
   
 arr[i] = 5 and arr[correctposition] = 4   
 so 5 <= 5 && 5 != 4 if condition true   
 now swap the 5 with 4   
   
   
 int temp = arr[i];  
 arr[i] = arr[correctposition];  
 arr[correctposition] = temp;  
   
 now resultant arr at this after 1st swap   
 arr[] = {2 3 1 4 5} now 5 is shifted at its correct position   
   
 now loop will run again check for i = 0 now arr[i] is = 2   
 after swapping 2 at its correct position   
 arr[] = {3 2 1 4 5}  
   
 now loop will run again check for i = 0 now arr[i] is = 3   
 after swapping 3 at its correct position   
 arr[] = {1 2 3 4 5}  
   
 now loop will run again check for i = 0 now arr[i] is = 1  
 this time 1 is at its correct position so else block will execute and i will increment i = 1;  
 once i exceeds the size of array will get array sorted.  
 arr[] = {1 2 3 4 5}  
   
   
 else  
   
 i++;  
loop end;  
  
once while loop end we get sorted array just print it   
for( index = 0 ; index < arr.length; index++)  
 print(arr[index] + ' ')  
sorted arr[] = {1 2 3 4 5}

Mai jos este implementarea abordării de mai sus:

C++ 
#include    using namespace std; void cyclicSort(int arr[] int n){  int i = 0;   while(i < n)  {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correct = arr[i] - 1 ;  if(arr[i] != arr[correct]){  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr[i] arr[correct]) ;  }else{  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++ ;  }  } } void printArray(int arr[] int size) {  int i;  for (i = 0; i < size; i++)  cout << arr[i] << ' ';  cout << endl; } int main() {  int arr[] = { 3 2 4 5 1};  int n = sizeof(arr) / sizeof(arr[0]);  cout << 'Before sorting array: n';  printArray(arr n);  cyclicSort(arr n);  cout << 'Sorted array: n';  printArray(arr n);  return 0; }
Java 
// java program to check implement cycle sort import java.util.*; public class MissingNumber {  public static void main(String[] args)  {  int[] arr = { 3 2 4 5 1 };  int n = arr.length;  System.out.println('Before sort :');  System.out.println(Arrays.toString(arr));  CycleSort(arr n);    }  static void CycleSort(int[] arr int n)  {  int i = 0;  while (i < n) {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correctpos = arr[i] - 1;  if (arr[i] < n && arr[i] != arr[correctpos]) {  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr i correctpos);  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  }  System.out.println('After sort : ');  System.out.print(Arrays.toString(arr));      }  static void swap(int[] arr int i int correctpos)  {  // swap elements with their correct indexes  int temp = arr[i];  arr[i] = arr[correctpos];  arr[correctpos] = temp;  } } // this code is contributed by devendra solunke
Python 
# Python program to check implement cycle sort def cyclicSort(arr n): i = 0 while i < n: # as array is of 1 based indexing so the # correct position or index number of each # element is element-1 i.e. 1 will be at 0th # index similarly 2 correct index will 1 so # on... correct = arr[i] - 1 if arr[i] != arr[correct]: # if array element should be lesser than # size and array element should not be at # its correct position then only swap with # its correct position or index value arr[i] arr[correct] = arr[correct] arr[i] else: # if element is at its correct position # just increment i and check for remaining # array elements i += 1 def printArray(arr): print(*arr) arr = [3 2 4 5 1] n = len(arr) print('Before sorting array:') printArray(arr) # Function Call cyclicSort(arr n) print('Sorted array:') printArray(arr) # This Code is Contributed by Prasad Kandekar(prasad264)
C# 
using System; public class GFG {  static void CycleSort(int[] arr int n)  {  int i = 0;  while (i < n) {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correctpos = arr[i] - 1;  if (arr[i] < n && arr[i] != arr[correctpos]) {  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr i correctpos);  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  }  Console.Write('nAfter sort : ');  for (int index = 0; index < n; index++)  Console.Write(arr[index] + ' ');  }  static void swap(int[] arr int i int correctpos)  {  // swap elements with their correct indexes  int temp = arr[i];  arr[i] = arr[correctpos];  arr[correctpos] = temp;  }  static public void Main()  {  // Code  int[] arr = { 3 2 4 5 1 };  int n = arr.Length;  Console.Write('Before sort : ');  for (int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');  CycleSort(arr n);  } } // This code is contributed by devendra solunke
JavaScript 
// JavaScript code for the above code function cyclicSort(arr n) {  var i = 0;  while (i < n)  {    // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  let correct = arr[i] - 1;  if (arr[i] !== arr[correct])  {    // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  [arr[i] arr[correct]] = [arr[correct] arr[i]];  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  } } function printArray(arr size) {  for (var i = 0; i < size; i++) {  console.log(arr[i] + ' ');  }  console.log('n'); } var arr = [3 2 4 5 1]; var n = arr.length; console.log('Before sorting array: n'); printArray(arr n); cyclicSort(arr n); console.log('Sorted array: n'); printArray(arr n); // This Code is Contributed by Prasad Kandekar(prasad264)

Ieșire 
Before sorting array: 3 2 4 5 1 Sorted array: 1 2 3 4 5

Analiza complexității timpului:

  • Cel mai rău caz: Pe) 
  • Caz mediu: Pe) 
  • Cel mai bun caz: Pe)

Spațiu auxiliar: O(1)

Avantajul sortării pe ciclu:

  1. Nu este necesară stocarea suplimentară.
  2.  algoritm de sortare in loc.
  3.  Un număr minim de scrieri în memorie
  4.  Sortarea ciclului este utilă atunci când matricea este stocată în EEPROM sau FLASH. 

Dezavantajul sortării pe ciclu:

  1.  Nu este folosit în mare parte.
  2.  Are o complexitate mai mare în timp o(n^2)
  3.  Algoritm de sortare instabil.

Aplicația  a sortării ciclului:

  • Acest algoritm de sortare este cel mai potrivit pentru situațiile în care operațiunile de scriere sau de schimbare a memoriei sunt costisitoare.
  • Util pentru probleme complexe. 
     
Creați un test