שאלה על מיון מערך

[vinney]

המם...

מקרה סביר זה שאלה קשה. הוא תלוי באופי הנתונים. עקרונית לכל מימוש של QSORT ניתן למצוא סט של נתונים שבו הביצועים יהיו N^2, יעני הגרוע ביותר. אבל, אופטימיזציות של QSORT הן אלה שגורמות לביצועיו הטובים, ואת אלה אתה עושה משיקול הנתונים שיש לך. יש גם גורם אי ודאות (בחירת PIVOT רנדומלי) שיכול לעזור להמנע מסט נתונים גרוע. בגדול - ברוב מוחלט של המקרים (שניתנו בלי כוונה להכשיל את האלגוריתם) הוא יעבוד טוב. מערך דו מימדי זה מקרה פרטי של מערך חד מימדי.

 

[DadleFish]

כמה תשובות...

קודם כל, quicksort הוא שיטת מיון אחת מיני רבות שסדר הגודל הממוצע שלהן הוא NlogN - פשוט quicksort יותר מהיר פרקטית מכל השאר, ברוב המקרים. אין הגדרה למקרה סביר. התיאוריה מנתחת את האלגוריתם בצורה שמכריעה מהו המקרה הטוב ביותר, הגרוע ביותר, והממוצע. quicksort יפעל במקרה הממוצע ב-NlogN ובמקרה הגרוע ב-N^2, אבל לרוב יהיה פשוט יותר מהיר פרקטית מכל מיון אחר. מיון מערך דו מימדי - טוב, זו שאלה קצת יותר מורכבת, כי זה תלוי איך אתה רוצה את התוצאה. ויני אמר שמערך דו מימדי הוא מקרה פרטי של מערך חד מימדי. אז זו שיטה אחת - מערך של 10x10 אפשר למיין בתור מערך של 100 תאים; שיטה אחרת תהיה, למשל, למיין כל שורה (או כל טור) בפני עצמם. או אולי למיין כל שורה בפני עצמה, ואז לעשות מיון בין השורות לפי הממוצע שלהן, או החציון שלהן, או האיבר הראשון או האחרון... בקיצור, במערך N-מימדי יש הרבה יותר אופציות וזה מאוד תלוי בתוצאה שאתה מצפה לקבל.

 

[demultiplexer]

אני רוצה למיין מערך דו מימדי לפי אי

אני רוצה למיין מערך דו מימדי לפי איבר מסויים בתת המערך. לזה אני מתכוון:

for (outerCntr=0;outerCntr<arrayLength;outerCntr++){ for (cntr=1;arrayLength-cntr>outerCntr;cntr++){ if (soldiersInBusDetails[outerCntr][orderCritirea]>soldiersInBusDetails[(arrayLength-cntr)][orderCritirea]){ temp=soldiersInBusDetails[outerCntr]; soldiersInBusDetails[outerCntr]=soldiersInBusDetails[(arrayLength-cntr)]; soldiersInBusDetails[(arrayLength-cntr)]=temp; } } }​

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

 

[DadleFish]

האמת שאני כל כך עייף

שלא הסתכלתי על הדוגמה... אבל לעניין הקריטריון, הרעיון הוא פשוט. בגדול, המיון הוא "מבוסס השוואות". זה אומר שבהינתן שני אובייקטים A ו-B, יש להחליט מי יותר גדול (או קטן, לא משנה). עכשיו, נגיד שבאובייקטים שלך יש שם ומספר טלפון, ואתה רוצה למיין קודם לפי שם ואח"כ לפי מספר טלפון; אז אתה צריך פונקציה שתקבל A ו-B ותחזיר מי גדול מבין שניהם. היא תבדוק את השם, ואם הוא זהה ביניהם - תעבור להשוות את הטלפון. פשוט מאוד.

 

[demultiplexer]

בקשר למיון מהיר ומיון מערך דו מימדי

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

 

[DadleFish]

רגע, רגע...שוב אתה עושה בלאגן

QUICKSORT לא טוב במקרה הקיצוני שבו המערך כבר ממויין. נהוג לעשות איטרציה אחת של INSERTION SORT, תוך כדי לבדוק אם המערך ממויין, ואם לא - להפעיל QUICK SORT. הנה לינק מצוין לאנימציות של מיונים שונים, כולל קוד ב-JAVA. בכל אופן, מה הקשר למערך דו מימדי? שוב, תחזור למה שכתבתי קודם. מה התוצאה שאתה רוצה לקבל בדיוק?

 

[demultiplexer]

בתשובה שנתת קודם . . .

ענית לי על מיון עם כמה תנאים. עכשיו בלי קשר לשאלות הקודמות אני אומר שאני רוצה למיין מערך דו מימדי. אני רוצה למיין את כל תת המערכים (כלומר האיברים של המערך הדו מימדי) לפי איבר 0 של תת המערכים. כלומר תת המערך עם איבר 0 הכי גדול יהיה בתחילת המערך הדו מימדי. אני לא רוצה למיין איברים אלא תת מערכים. כמו שמופיע בקוד שכתבתי