הצעה: שיטת מיון מהירה למערכים קטנים של מספרים שלמים

[DXT]

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

[N N C]

מה דעתך על זה (יושם בפסקל, לא יודע בקשר ל-C)

נניח ויש לך מערך עם מספרים נתונים ואתה רוצה למיין אותו

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

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

[toxigun]

במקרה זה לא Selection Sort?

[slider]

במקרה זה לא Selection Sort?

כן זה SELECTION SORT...

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

לדעתי כדאי לנסות ולראות אם זה באמת ככה!

וד"א, אני לא חושב שהמתרגל שלך המציא את האלגוריתם הזה מפני שזהו אלגוריתם די ידוע... :

[DXT]

שלא לדבר על חוסר יעילותו בשל זלילת זכרון ענקית... :

[toxigun]

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

בכל מקרה, אם הסיבוכיות היא לינארית אז הוא יותר איטי מ-quicksort, מפני שלכל n>10 מתקים:

n < n*log(n)

[slider]

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

בכל מקרה, אם הסיבוכיות היא לינארית אז הוא יותר איטי מ-quicksort, מפני שלכל n>10 מתקים:

n < n*log(n)

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

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

נניח שאלגוריתם א' הוא בעל זמן ריצה של 000 ,100,000,000* n ולכן סיבוכיותו היא O(n)

ואלגוריתם ב' הוא בעל זמן ריצה n^2 ולכן גם סיבוכיותו היא O(n^2).

ולכן קל לראות שעבור n < 100,000,000,000 אלגוריתם ב' יפעל יותר מהר מאלגוריתם א' למרות שלאלגוריתם א' סיבוכיות יותר קטנה!

וברור שבפועל לא נקבל קלט כל כך ארוך (למי שיש ספק, אפשר להוסיף עוד אפסים 8))

יש מבין?

[toxigun]

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

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

[slider]

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

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

(כך למשל, אם נקח את ה quicksort בגירסתו המקורית, הסיבוכיות במקרה הממוצע ובמקרה הטוב ביותר היא n*logn ואילו במקרה הגרוע (שקורה כאשר המערך ממוין בסדר הפוך), הסיבוכיות היא n^2)

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

[toxigun]

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

[slider]

נו בסדר... :smoke:

[B.D.B]

complexity is always worst case, btw. and it's 100% bullshit, by the time it'll take you to calculat it you could benchmark every other way possible.

[toxigun]

Benchmarks are ok, but they are machine specific

A little taste of academic studies will change your mind :-)

[slider]

complexity is always worst case, btw.

now that's bullshit!!!

מי אמר לך את זה?

[toxigun]

Because this is the definition of the term in computer science called "Complexity". It's like "Circle" is defined to be a set of points that are placed in equal distance from the center.