מיון מחזור - מִיוּן

נסה את זה ב-GfG Practice מיון מחזור' title=

מיון מחזור הוא אלגוריתם מיון לא יציב במקום, שימושי במיוחד בעת מיון מערכים המכילים אלמנטים עם טווח קטן של ערכים. הוא פותח על ידי W. D. Jones ופורסם ב-1963.

הרעיון הבסיסי מאחורי מיון מחזור הוא לחלק את מערך הקלט למחזורים כאשר כל מחזור מורכב מאלמנטים השייכים לאותו מיקום במערך הפלט הממוין. לאחר מכן האלגוריתם מבצע סדרה של החלפות כדי למקם כל אלמנט במיקומו הנכון בתוך המחזור שלו עד שכל המחזורים יסתיימו והמערך ממוין.

להלן הסבר שלב אחר שלב של אלגוריתם מיון המחזור:

התחל עם מערך לא ממוין של n אלמנטים.
אתחול מחזור משתנה התחל ל-0.
עבור כל אלמנט במערך השווה אותו עם כל אלמנט אחר מימין לו. אם יש אלמנטים כלשהם שקטנים מהרכיב הנוכחי, הגדל מחזור התחל.
אם cycleStart עדיין 0 לאחר השוואת האלמנט הראשון עם כל האלמנטים האחרים, עבור לאלמנט הבא וחזור על שלב 3.
ברגע שנמצא אלמנט קטן יותר, החלף את האלמנט הנוכחי עם האלמנט הראשון במחזור שלו. לאחר מכן המחזור נמשך עד שהאלמנט הנוכחי חוזר למיקומו המקורי.

חזור על שלבים 3-5 עד שכל המחזורים הושלמו.

המערך ממוין כעת.

אחד היתרונות של מיון מחזור הוא שיש לו טביעת זיכרון נמוכה שכן הוא ממיין את המערך במקום ואינו דורש זיכרון נוסף למשתנים או מאגרים זמניים. עם זאת זה יכול להיות איטי במצבים מסוימים במיוחד כאשר למערך הקלט יש מגוון גדול של ערכים. אף על פי כן, מיון מחזור נשאר אלגוריתם מיון שימושי בהקשרים מסוימים, כגון בעת מיון מערכים קטנים עם טווחי ערכים מוגבלים.

מיון מחזור הוא אלגוריתם מיון במקום אלגוריתם מיון לא יציב ומיון השוואה שהוא אופטימלי מבחינה תיאורטית מבחינת המספר הכולל של כתיבה למערך המקורי.

שחקן זינאט אמן

זה אופטימלי מבחינת מספר הכתיבה בזיכרון. זֶה ממזער את מספר הכתיבה בזיכרון למיין (כל ערך נכתב אפס פעמים אם הוא כבר נמצא במיקומו הנכון או נכתב פעם אחת למיקומו הנכון.)
הוא מבוסס על הרעיון שניתן לחלק את המערך שיש למיין למחזורים. ניתן להמחיש מחזורים כגרף. יש לנו n צמתים וקצה המכוון מהצומת i לצומת j אם האלמנט באינדקס i-th חייב להיות קיים באינדקס j-th במערך הממוין.
מחזור ב-arr[] = {2 4 5 1 3}

מחזור ב-arr[] = {2 4 5 1 3}

מחזור ב-arr[] = {4 3 2 1}

מחזור ב-arr[] = {4 3 2 1}

אנחנו בזה אחר זה שוקלים את כל המחזורים. ראשית, נבחן את המחזור הכולל את האלמנט הראשון. אנו מוצאים את המיקום הנכון של האלמנט הראשון וממקמים אותו במיקום הנכון שלו נגיד j. אנו מחשיבים את הערך הישן של arr[j] ומוצאים את המיקום הנכון שלו, אנו ממשיכים לעשות זאת עד שכל הרכיבים של המחזור הנוכחי ממוקמים במיקום הנכון, כלומר לא נחזור לנקודת ההתחלה של המחזור.

fcfs

פסאודוקוד:

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

הסבר:

 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

להלן יישום הגישה לעיל:

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# 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>

תְפוּקָה

After sort : 1 2 3 4 8 9 10 10

ניתוח מורכבות זמן :

המקרה הגרוע ביותר: עַל²)
מקרה ממוצע: עַל²)
המקרה הטוב ביותר: עַל²)

מרחב עזר: O(1)

מורכבות החלל היא קבועה מכיוון שהאלגוריתם הזה קיים ולכן אינו משתמש בזיכרון נוסף כדי למיין.

שיטה 2: שיטה זו ישימה רק כאשר ערכי מערך נתונים או אלמנטים נמצאים בטווח של 1 עד N או 0 עד N. בשיטה זו אין צורך לסובב מערך

גישה: כל ערכי המערך הנתונים צריכים להיות בטווח של 1 עד N או 0 עד N. אם הטווח הוא 1 עד N אז המיקום הנכון של כל רכיב מערך יהיה האינדקס == ערך-1 כלומר, ערך האינדקס ה-0 יהיה 1 באופן דומה במיקום האינדקס הראשון ערך 2 וכן הלאה עד הערך ה-n'י.

באופן דומה עבור 0 עד N ערכים מיקום האינדקס הנכון של כל רכיב או ערך של מערך יהיה זהה לערך שלו כלומר באינדקס 0 0 יהיה שם מיקום 1 1 יהיה שם.

הסבר:

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}

להלן יישום הגישה לעיל:

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)

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)

תְפוּקָה

Before sorting array: 3 2 4 5 1 Sorted array: 1 2 3 4 5

ניתוח מורכבות הזמן:

כמה מקשים יש למקלדות

המקרה הגרוע ביותר: עַל)
מקרה ממוצע: עַל)
המקרה הטוב ביותר: עַל)

מרחב עזר: O(1)

היתרון של מיון מחזור:

אין צורך באחסון נוסף.
אלגוריתם מיון במקום.
מספר מינימלי של כתיבה לזיכרון
מיון מחזור שימושי כאשר המערך מאוחסן ב-EEPROM או ב-FLASH.

חסרון של מיון מחזור:

לא נעשה בו שימוש בעיקר.
יש לו יותר מורכבות זמן o(n^2)
אלגוריתם מיון לא יציב.

יישום מסוג מחזור:

אלגוריתם מיון זה מתאים ביותר למצבים שבהם פעולות כתיבה או החלפה בזיכרון הן יקרות.
שימושי לבעיות מורכבות.

צור חידון