מיון מהיר ב- Java מוסבר

אמנת מחצית

כאשר מספר האלמנטים ברשימה הוא שווה, מחצית מהרשימה פירושה שהמחצית הראשונה של הרשימה היא המחצית הראשונה, והחצי השני המילולי של הרשימה הוא המחצית השנייה. האלמנט האמצעי (האמצעי) של הרשימה כולה, הוא המרכיב האחרון של הרשימה הראשונה. המשמעות היא שהמדד האמצעי הוא אורך / 2 - 1, שכן ספירת האינדקס מתחילה מאפס. אורך הוא מספר האלמנטים ברשימה. לדוגמה, אם מספר האלמנטים הוא 8, הרי שבמחצית הראשונה של הרשימה יש 4 אלמנטים ובמחצית השנייה של הרשימה יש גם 4 אלמנטים. זה בסדר. מאחר וספירת המדדים מתחילה מ- 0, המדד האמצעי הוא 3 = 8 /2 - 1.

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

חלוקה בדרך זו היא דוגמא לאריתמטיקה שלמה.

חציון של שלושה ערכים

שאלה: מה החציון של הרצף:

C B A

פִּתָרוֹן:
סדרו את הרשימה בסדר עולה:

א ב ג

המונח האמצעי, B, הוא החציון. הגודל הוא בין שני הגדלים האחרים.

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

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

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

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

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

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

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

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

C B A

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

ב ג א

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

A C B

שימו לב, הערכים של המדד הגבוה ביותר והמדד הנמוך ביותר השתנו. ההצהרה השלישית אם משווה C ו- B. אם C פחות מ- B, יש להחליף את העמדות של C ו- B. C הוא לא פחות מ- B, כך שלא תתבצע החלפה. ההסדר החדש נשאר כמו הקודם, כלומר:

A C B

B הוא החציון, כלומר A [גבוה], והוא הציר. לכן, הציר נולד בקצה הקיצוני של הרשימה או רשימת המשנה.

פונקציית ההחלפה

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

כאן, x ו- y מתייחסים לערכים בפועל ולא לעותקים.

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

תוכן המאמר

• אלגוריתם מיון מהיר
• פסאודוקוד של מחיצה
• איור של מיון מהיר
• קידוד Java
• סיכום

אלגוריתם מיון מהיר

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

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

השלבים לאלגוריתם ה- quicksort הם כדלקמן:

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

פסאודוקוד המיון המהיר הוא:

פסאודוקוד של מחיצה

פסאודוקוד המחיצה המשמש בשיעור זה הוא:

באיור של מיון מהיר להלן, נעשה שימוש בקוד זה:

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

שקול את הרשימה (המערך) הלא ממוינת הבאה של אותיות אלפביתיות:

Q W E R T Y U I O P

לפי בדיקה, הרשימה הממוינת היא:

E I O P Q R T U W Y

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

Q W E R T Y U I O P

הציר הראשון נקבע מ- arr [0] = Q, arr [4] = T, ו- arr [9] = P, והוא מזוהה כ- Q וממוקם בצד ימין קיצוני של הרשימה. אז הרשימה עם כל מיון פונקציות הציר הופכת ל:

P W E R T Y U I O Q

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

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

P O E R T Y U I W Q

הציר עדיין Q. הסריקה לכיוונים מנוגדים ממשיכה ועוצרת בהתאם. אם i עדיין לא שווה ל- j או גדול מ- j, אז שני הערכים שבהם הסריקה משני הקצוות הופסקה מוחלפים. הפעם, הסריקה משני הקצוות נעצרה ב- R ו- I. לכן, סידור הרשימה הופך להיות:

P O E I T Y U R W Q

הציר עדיין Q. הסריקה לכיוונים מנוגדים ממשיכה ועוצרת בהתאם. אם i עדיין לא שווה ל- j או גדול מ- j, שני הערכים שבהם הסריקה הופסקה מוחלפים. הפעם, הסריקה משני הקצוות נעצרה ב- T עבור i ואני עבור j. אני וג 'נפגשנו או חצינו. אז לא יכולה להיות החלפה. הרשימה נשארת זהה ל:

P O E I T Y U R W Q

בשלב זה יש להציב את הציר, Q, במיקומו הסופי במיון. זה נעשה על ידי החלפת arr [i] עם arr [high], החלפת T ו- Q. הרשימה הופכת:

P O E I Q Y U R W T

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

P O E I Q Y U R W T

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

לרשימת המשנה:

P O E I

הציר (החציון) עבור P, O ו- I נקבע. הציר יהיה O. עבור רשימת המשנה הזו, ומתייחסת לרשימה המלאה, הערך החדש [נמוך] הוא arr [0], והערך החדש [גבוה] הוא ה- arr האחרון [i-1] = arr [ 4-1] = arr [3], כאשר i הוא מדד הציר הסופי מהמחיצה הקודמת. לאחר קריאת הפונקציה pivot (), ערך הציר החדש, pivot = O. אל תבלבלו בין פונקציית הציר לבין ערך הציר. פונקציית הציר עשויה לבצע מיון קטן ולמקם את הציר בצד ימין קיצוני של רשימת המשנה. רשימת המשנה הזו הופכת,

I P E O

עם תוכנית זו, הציר תמיד מסתיים בקצה הימני של רשימת המשנה או הרשימה לאחר קריאת הפונקציה שלה. הסריקה משני הקצוות מתחילה מ- arr [0] ומ- arr [3] עד שאני ו- j נפגשים או חוצים. ההשוואה נעשית עם pivot = O. התחנות הראשונות הן ב- P ו- E. הן מוחלפות, ורשימת המשנה החדשה הופכת:

I E P O

הסריקה משני הקצוות נמשכת, והתחנות החדשות נמצאות ב- P for i וב- E עבור j. עכשיו אני וג 'נפגשנו או חצו. אז רשימת המשנה נשארת זהה ל:

I E P O

חלוקת רשימת המשנה או הרשימה מסתיימת כאשר הציר הוצב במיקומו הסופי. לכן, הערכים החדשים עבור arr [i] ו- arr [גבוה] מוחלפים. כלומר, P ו- O מוחלפים. רשימת המשנה החדשה הופכת ל:

I E O P

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

I E O P

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

אני ה

זה יתחיל בחיפוש החציון של I ו- E. כאן, arr [low] = I, arr [mid] = I ו- arr [high] = E. אז החציון, הציר, צריך להיקבע על ידי אלגוריתם הציר כ- , I. עם זאת, פסאודוקוד הציר לעיל יקבע את הציר כ- E. שגיאה זו מתרחשת כאן מכיוון שהפסאודוקוד הנ'ל מיועד לשלושה יסודות ולא לשניים. ביישום להלן, יש התאמה מסוימת לקוד. רשימת המשנה הופכת,

E אני

הציר תמיד מסתיים בקצה הימני של רשימת המשנה או הרשימה לאחר קריאת הפונקציה שלה. הסריקה משני הקצוות מתחילה מ- arr [0] ו- arr [1] בלעדית עד שאני ו- j נפגשים או חוצים. ההשוואה נעשית עם pivot = I. התחנות הראשונות והיחידות הן ב- I ו- E: ב- I עבור i ו- ב- E עבור j. עכשיו אני וג 'נפגשנו או חצינו. אז, רשימת המשנה נשארת זהה ל:

E אני

חלוקת רשימת המשנה או הרשימה מסתיימת כאשר הציר הוצב במיקומו הסופי. לכן, הערכים החדשים עבור arr [i] ו- arr [גבוה] מוחלפים. קורה כאן ש- arr [i] = I ו- arr [high] = I. לכן אותו ערך מוחלף עם עצמו. רשימת המשנה החדשה הופכת ל:

E אני

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

E אני

כעת, הצירים עד כה היו Q, O ו- I. צירים מסתיימים בעמדותיהם האחרונות. רשימת משנה של אלמנט יחיד, כגון ה- P לעיל, מסתיימת גם במיקומה הסופי.

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

E I O P Q Y U R W T

רשימת המשנה הימנית הראשונה:

Y U R W T

עדיין צריך לסדר.

כיבוש רשימת המשנה הימנית הראשונה
זכור כי קריאת המיון המהיר לרשימת המשנה הימנית הראשונה צוינה ושמורה במקום לביצוע. בשלב זה הוא יבוצע. וכך, ה- arr [low] = arr [5] = arr [QPivotIndex+1], והערך החדש [high] נשאר arr [9]. מערך פעילויות דומה שקרה לרשימת המשנה השמאלית הראשונה יקרה כאן. ורשימת המשנה הימנית הראשונה הזו ממוינת לפי:

R T U W Y

והרשימה המקורית הלא ממוינת מסודרת לפי:

E I O P Q R T U W Y

קידוד Java

הצבת האלגוריתם ב- Java היא רק להכניס את כל מקטעי ה- pseudocode לעיל לשיטות ג'אווה במחלקה אחת. אל תשכח שצריכה להיות שיטה ראשית () בכיתה שתקרא לפונקציה quicksort () עם המערך הלא ממוין.

שיטת הציר ()

שיטת Java pivot () שמחזירה את הערך, pivot, צריכה להיות:

שיטת ההחלפה ()

שיטת ההחלפה () צריכה להיות:

שיטת ה- quicksort ()

שיטת ה- quicksort () צריכה להיות:

שיטת המחיצה ()

שיטת המחיצה () צריכה להיות:

השיטה העיקרית ()

השיטה העיקרית () יכולה להיות:

ניתן להכניס את כל השיטות הנ'ל למחלקה אחת.

סיכום

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

על הסופר

חרצית פורצ'ה

מגלה שילוב מתמטיקה מעקרונות ראשונים וסדרות נלוות. תואר שני בחינוך טכני, המתמחה באלקטרוניקה ותוכנות מחשב. BSc אלקטרוניקה. יש לי גם ידע וניסיון ברמת המאסטר במחשוב ותקשורת. מתוך 20,000 כותבים, הייתי הסופר ה -37 הטוב ביותר באתר devarticles.com. אני עובד בתחומים אלה במשך יותר מעשר שנים.

הודעות LINUX רלוונטיות

• השוואת מחרוזות ב- Java
• כיצד להשתמש ב- HashMap ב- Java
• מיון מהיר ב- Java מוסבר
• העברת הזמנות מראש של עץ בינארי בג'אווה
• מיזוג מיון ב- Java מוסבר
• כיצד להשתמש בסורק ב- Java
• Java לכתוב לקובץ