שלום,

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

את השליפה של הנתונים כבר עשיתי, כלומר יש בידי מערך של אינדקסים ומערך של השמות, וכתבתי כבר פונקציה שממיינת את השמות (באמצעות Merge Sort אם זה רלוונטי). אני רק צריך איכשהו לקשר בין השמות לאינדקסים.

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

אשמח לרעיונות,
תודה.

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

המערכים מסודרים כך ש-names[i]‎ מכיל את השם של הסטודנט שהנתונים שלו נמצאים ב-offset הנתון על-ידי indices[i]‎ עבור כל i?
אם כן, זה ממש פשוט. תייצר מערך של tuple-ים (או pair-ים, במקרה הספציפי הזה), מיין אותו לפי אלמנט השם ב-pair, ואז תפלוט את כל אלמנטי האינדקס של ה-pair-ים במערך.
(אם לא, תייצר את המערך של ה-pair-ים בכל מקרה. זו לא צריכה להיות בעיה.)

אם השאלה שלך היא טכנית, איך מייצרים pair ב-C וממיינים לפי אחד השדות שלו, התשובה היא: מייצרים struct foo { char * name; unsigned long index; };‎ וממיינים בעזרת qsort ופונקציית השווואה שנראית בערך כך :int bar(const void * left, const void * right) { return strcmp((struct foo*)left->name, (struct foo*)right->name); }‎ או משהו כזה...

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

כן, הבנת נכון.

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

תודה.

אין בעיה, אחי. תבוא כל יום!

היית מראש צריך לייצר את המערך ככה במקום שני מערכים נפרדים.

אם במקום להשתמש ב-qsort היית מממש את המיון לבד, או משתמש בפונקציית pasten_sort היפותטית שבמקום להחליף אלמנטים במערך על סמך פרמטר גודל האלמנט שהיא מקבלת, הייתה מקבלת גם פונקציית swapper (כמו שהיא מקבלת comparator), היית יכול למממש swapper שמחליף גם אלמנטים במערך שמתמיין וגם במערך השני.

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

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

האמת שמיממשתי את המיון לבד, השתמשתי ב-Merge Sort. אני לא רוצה להגיע למצב שבו (תיאורטית; ע"פ ויקיפדיה זה כמעט ולא קורה) זמן הריצה הוא n^2.

אבל ל-merge sort יש סיבוכיות מקום מטורפת (יחסית), ואף אחד לא אמר לך שהפונקציה qsort באמת עושה quicksort. התקן לא אומר שום דבר כזה (‎§7.20.5.2 ב-ISO/IEC 9899:1999). בנוסף, העף מבט בפוסטים האלה ב-SO:

• http://stackoverflow.com/questions/...qsort-recursive
• http://stackoverflow.com/questions/...sort-vs-stdsort

חלק מהקישורים שם שבורים, אז הנה הקישורים המתוקנים:

• Engineering a Sort Function (Bentley & McIlroy)‎
• Introspective Sorting and Selection Algorithms (Musser)‎
  
• http://en.wikipedia.org/wiki/Introsort

אתה מקבל סיבוכיות של [TEX]O(log_2(n))[/TEX] רק במקרה הגרוע, אם האלגוריתם נאיבי, או אם אתה מרשה שיעבדו עליך (כמו במאמר הזה שהוזכר באחת ההערות לשאלה השניה שקישרתי למעלה: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf). אחרת, אין כל-כך סיבה שזה יקרה.

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

וואלק אתה...
אני אסתכל על זה בעיון, תודה!