הפתק הסגול :: צפייה בנושא

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

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

חשבתי על כיוון כזה

present_word<Min
while present_word <> Max do
find the next word in lexicographic order

Brick wall

שכחתי איך קוראים למיון הזה. הדבר שאיתו ממינים את המספרים בעשרוני (החל מהספרה האחרונה לכיוון הראשונה).
Bucket sort

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

שכחתי איך קוראים למיון הזה. הדבר שאיתו ממינים את המספרים בעשרוני (החל מהספרה האחרונה לכיוון הראשונה).
Bucket sort

כן מיון דלי\סלים
http://he.wikipedia.org/wiki/%D7%9E%D7%99%D7%95%D7%9F_%D7%93%D7%9C%D7%99

מה איתו? Smile

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

תשתמש במיון שלך (הרי מספר האותיות ידוע)

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

תשתמש במיון שלך (הרי מספר האותיות ידוע)

איזה?מה שתיארתי בהתחלה?

לדעתי הוא מתאים איכשהו לדרישות הסיבוכיות

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

לדעתי הוא מתאים איכשהו לדרישות הסיבוכיות

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

אגב אם אותו קובץ מכיל מספר שלם חיובי בהתחלת כל שורה
האלגוריתם שכתבתי יכול להתאים גם למיון הקובץ באותו זמןO(n)zzz רק ש n מציין את מספר הספרות במספרים?

אבל אתה יכול להוסיף סימן לא"ב שיקבל ערך הכי נמוך ואיתו למלא את שורות איפה שנדרש (כך שתקבל כל השורות באותו אורך)

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

אבל אתה יכול להוסיף סימן לא"ב שיקבל ערך הכי נמוך ואיתו למלא את שורות איפה שנדרש (כך שתקבל כל השורות באותו אורך)

?תוכל להסביר מה הכוונה

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

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

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

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

להשתמש באלגוריתם שאני רשמתי
present_word<Min
while present_word <> Max do
find the next word in lexicographic order

או במיון דלי?

בחלק השני: קובץ מכיל מספר שלם חיובי בהתחלת כל שורה
מיון הקובץ באותו זמןO(n)zzz רק ש n מציין את מספר הספרות במספרים

חשבתי אולי דווקא להשתמש בחלק זה לא במיון דלי אלא במיון בסיס-RadixSort
כמובן תחת ההנחה שכל המספרים שונים כי אם קיימים מספרים זהים אז אני לא רואה דרך לבצע את המיון של המערך בזמן O(n) כאשר n הוא מספר ספרות בכל המספרים

בחלק הראשון אתה עושה משהו כמו מיון בועות?
בשני לא זוכר מה זה RADIX

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

בחלק הראשון אתה עושה משהו כמו מיון בועות?
בשני לא זוכר מה זה RADIX

אתה חושב שכדי ללכת בחלק הראשון בכיוון של מיון דלי?

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

אבל צריך להניח כי כל המספרים הם בטווח בגודל k, בשל הנחה זו, מתבצע מיון בסיס בזמן ריצה של O(n*k)

אז לא קוראים לזה מיון דלי?
כי אני די משוכנע שעל זה דיברתי כל הזמן

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

אז לא קוראים לזה מיון דלי?
כי אני די משוכנע שעל זה דיברתי כל הזמן

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

נניח שהקבוע n חוסם את קבוצת המספרים. ניצור מערך A של מספרים שלמים בגודל n+1 (מ-0 עד n), ונאתחל את כל התאים בו לאפסים.

נעבור פעם אחת על כל איבר x בקבוצת המספרים, ונבצע: A[x] <- A[x] + 1

לאחר שעברנו כך על כל איברי הקבוצה, נעבור על המערך, מהתא שמספרו "אפס" ומעלה, ונדפיס עבור כל תא [A[i, את המספר i כמספר הפעמים התואם לערך התא [A[i.

טוב, אז התכוונתי מהתחלה למה שאתה קורה לו RADIX.
רק במימוש למחרוזות

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

טוב, אז התכוונתי מהתחלה למה שאתה קורה לו RADIX.
רק במימוש למחרוזות

אוקיי ובחלק השני גם להשתמש בRADIX?

חלק שני זה מספר במקום מחרוזת?

הצטרף בתאריך: 02/05/2008 ב- 06:59:39 הודעות: 189

--== dEmigOd ==-- כתב:

חלק שני זה מספר במקום מחרוזת?

כן חלק שני n מציין את מספר הספרות במספרים
וחלק ראשון n מציין את מספר התווים בתמליל

הצטרף בתאריך: 25/06/2009 ב- 18:04:23 הודעות: 3

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

עמוד ראשי -> עזרה בתרגילים -> מיון בסדר א"ב
	צפה בנושא הקודם :: צפה בנושא הבא