באלגוריתמים הדבר נחוץ כי לעיתים קרובות פעולות על קלט ממוין הן מסיבוכיות נמוכה יותר. למשל, ניתן למצוא את הערך המקסימלי והמינימלי (או בכלל, ה-formula_1 בגודלו) במערך ממוין בסיבוכיות זמן של formula_2 ולמצוא איבר כללי במערך בסיבוכיות לוגריתמית. (באמצעות חיפוש בינארי, למשל)
אלגוריתמי מיון מבוססי השוואות.
ישנם אלגוריתמי מיון רבים, הנבדלים זה מזה בסיבוכיות הזמן והזיכרון שלהם, בפשטות מימושם ובהנחה על הפעולות הבסיסיות. חלוקה מקובלת היא בין אלגוריתמי המיון המבוססים על פעולת השוואה בין האיברים הנתונים לבין אלה המאפשרים פעולות כלליות על האיברים. כל אלגוריתמי המיון המבוססים על פעולת השוואה דורשים לפחות formula_3 פעולות השוואה במקרה הגרוע על-מנת לבצעם.
ניתן להגיע למסקנה זו על ידי התבוננות ב"עץ השוואות" המתאר מיון כללי, בו כל קודקוד מסמן השוואה בין שני איברים, כל קשת מסמלת תוצאה אחרת של אותה השוואה וכל עלה מייצג את סיום פעילות האלגוריתם ואת הסדר בו יש לסדר את הנתונים.
מאחר שקיימות לכל formula_4 איברים formula_5 דרכים לסדרם, הרי שמספר העלים בעץ יהיה formula_5, ומכיוון שדרגת העץ חסומה, לפי משפט מתורת הגרפים גובה העץ (מספר ההשוואות שהאלגוריתם יאלץ לעשות לפני שיגיע לעלה) יהיה formula_7. ניתן לראות ש-formula_8 (באמצעות נוסחת סטירלינג) ומכאן נובע החסם.
רשימת אלגוריתמי מיון.
מיונים מבוססי השוואות:
מיונים עם הנחות נוספות על הקלט:
במיונים הללו (מנייה, סלים, בסיס) בעזרת מידע נוסף על הקלט סיבוכיות האלגוריתם יורדת אל מתחת לסיבוכיות המינימלית של אלגוריתם מיון מבוסס השוואות עד לformula_19 במקום formula_15.
ג'ון קולטריין
ג'וֹן ויליאם קוֹלְטְרֵיין (באנגלית: John William Coltrane; 23 בספטמבר 1926 – 17 ביולי 1967) היה מוזיקאי ג'אז אמריקאי, שנמנה עם הגדולים והמשפיעים בקרב הסקסופוניסטים ועולם הג'אז בכלל. השפעתו רבה במיוחד בתחומי נגינה בסקסופון טנור וסופרן, הרחבת אפשרויות האלתור, שילוב זרמי מוזיקת עולם בג'אז ויצירת נתיבי התפתחות חדשים כהארד בופ, ג'אז מודאלי וג'אז חופשי. אף על פי שפעל כמוזיקאי יוצר רק מעט למעלה מעשור, נחשב בעיני רבים למוזיקאי בעל ההשפעה הרבה ביותר על התפתחות הג'אז לאחר מהפכת הבי בופ.
שנים ראשונות וראשית הקריירה.
ג'ון קולטריין נולד לג'ון ר. קולטריין, חייט ומוזיקאי חובב, ואליס בלייר קולטריין. אבי אמו, ויליאם בלייר, היה כומר וקולטריין הצעיר קיבל ממנו חינוך דתי. הוא גדל בצפון קרוליינה, ולאחר שסיים את בית הספר היסודי ב-1939 מת אביו והותירו עם אמו ודודתו. אמו הרבתה לעבוד מחוץ לבית על מנת לפרנס את המשפחה, ולכן לא שהתה במחיצתו זמן רב. בשנה שבה החל ללמוד בחטיבת הביניים, הצטרף קולטריין ללהקה קהילתית וניגן שם בקלרינט ובקרן יער. כשסיים את החטיבה והגיע לתיכון הצטרף לתזמורת הביג בנד של בית הספר, שם ניגן בסקסופון אלט. במהלך מלחמת העולם השנייה התדרדר מצבה הכלכלי של המשפחה ואמו ודודתו עברו לניו ג'רזי כדי למצוא עבודה שם תוך שהן משאירות אותו לגדול עם יתר בני המשפחה בצפון קרוליינה. כשסיים את בית הספר התיכון, ב-1943, עבר גם הוא צפונה, לפילדלפיה, שם התאחד עם אמו.
באותו הזמן לא עבד קולטריין באופן רציף כמוזיקאי, העבודות הקבועות שלו לא היו קשורות לתחום. הוא נרשם לבית הספר למוזיקה "אורנשטיין" וניגן מעט במועדונים, מקור ההשפעה עליו בתקופה זו היה ג'וני הודג'ס. ב-1945 הצטרף לחיל הים של ארצות הברית והוצב בבסיס בהוואי. תפקידו לא היה קרבי. הוא המשיך לנגן והוציא את התקליט הראשון שלו עם ארבעה חיילים אחרים ב-13 ביולי 1946. ב-1946 שוחרר מן הצבא וחזר לפילדלפיה.
הוא הצטרף ללהקתו של ג'ו ווב ואחר כך ללהקתו של קינג קולאקס. במהלך 1946 עבר מסקסופון אלט לסקסופון טנור. בראיון חשוב עמו coltrane on coltrane
שהתפרסם ב-דאון ביט בספטמבר 1960) סיפר שבתקופה זו שמע לראשונה את צ'ארלי פארקר ("בירד") מנגן והדבר היווה עבורו "מכה בין העיניים". הוא סבר שפארקר מיצה את רוב האפשרויות בסקסופון אלט. באותה תקופה הצטרף קולטריין ללהקתו של , שהיה נגן סקסופון אלט, ולכן הייתה זו סיבה נוספת להחלפת כלי הנגינה שלו לטנור. באמצע 1948 עבר ללהקתו של ג'ימי הית', שהתפתחה מאוחר יותר ונקראה על שמו של האוורד מקג'י עד ל-1949, אז חזר לפילדלפיה. בסוף 1949 הצטרף לביג בנד של דיזי גילספי ונשאר עמה עד ל-1951. ב-1951 הוקלט קולטריין לראשונה מנגן סולו עם דיזי גילספי בשיר "We love boogie".
עם מיילס דייוויס.
קולטריין עבד בפילדלפיה כנגן חופשי (free lancer, שאינו קשור בקשר חוזי עם אף תזמורת). הוא התמכר להרואין, מה שהקשה עליו למצוא עבודה קבועה בתחום המוזיקה. בשנות החמישים המוקדמות נשכר ופוטר מספר פעמים, ממספר להקות. ב-1955 פגש את מיילס דייוויס, שהשתקם באותה תקופה מהתמכרותו לסמי שינה, והצטרף לחמישייה שלו, המכונה "החמישייה הראשונה", שכללה, בנוסף לדייוויס ולקולטריין את פול צ'יימברס בקונטרבס, פילי ג'ו ג'ונס בתופים ורד גרלנד בפסנתר. זו הייתה הפריצה הגדולה של קולטריין, ואפשר להגיד שהתגלה בזכות דייוויס. מאז שניגן איתו הוא נחשב למוזיקאי ג'אז גדול וזכה לדקות ארוכות של נגינת סולו אנרגטית. קולטריין הקליט תקליטים רבים עם ההרכב ("Cookin' with the Miles Davis Quintet", "Relaxin' with the Miles Davis Quintet", "Workin' with the Miles Davis Quintet", ו- "Steamin' with the Miles Davis Quintet") אולם חסר היה את היציבות ובמקרים רבים לא הגיע לחזרות ולהופעות. הרפרטואר של החמישייה היה בי בופ שכלל בעיקר עיבודים לסטנדרטים מוכרים. באפריל 1956 נאלץ דייוויס לפטר את קולטריין עקב מצב ההתמכרות הקשה שלו להרואין.
בתחילת 1959 חתם קולטריין חוזה הקלטות עם "פרסטיז'" וחזר ללהקתו של דייוויס, אך באפריל של אותה שנה שב פרש ממנה. ב-31 במאי 1957, הקליט קולטריין סוף-סוף את תקליטו הראשון כאמן מוביל, שנקרא בפשטות "קולטריין".
"העשור המופלא" כיוצר עצמאי.
מונק ומיילס.
ביוני של אותה שנה, קולטריין הצטרף לרביעיית ת'לוניוס מונק שהופיעה במועדון ה- Five Spot בניו-יורק והסולואים שלו התארכו. מהופעות אלה כמעט ולא נותרו הקלטות סבירות אלא מספר בוטלגים שחברת בלו נוט הצליחה להפיק מהם תקליטים באיכות סאונד סבירה סביב 2006. בספטמבר של אותה השנה הקליט קולטריין את אלבומו היחיד בחברת "בלו נוט" - "Blue Train", שיצא לאור בדצמבר. באלבום משתתפים לי מורגן בחצוצרה, קרטיס פולר בטרומבון, פול צ'יימברס בבס, קני דרו בפסנתר ופילי ג'ו ג'ונס בתופים; קולטריין עצמו מנגן בתקליט זה בסקסופון טנור. כל הקטעים בתקליט, למעט אחד, הם פרי עטו של קולטריין. התקליט מסווג כאחת מ"אבני הפינה" של סגנון ההארד בופ. הקטע "Lazy Bird" מדגים לראשונה את הפיתוח הייחודי של קולטריין באלתור שנודע כקולטריין צ'יינג'ס.
באותו החודש (ספטמבר 1957), הצטרף שוב קולטריין למיילס דייוויס, שצירף אליו גם את קנונבול אדרלי בסקסופון אלט, בעמדת המתופף הציב את ג'ימי קוב ובפסנתר את ביל אוונס. הוא הקליט עם השישייה את האלבום החשוב "Kind of Blue", שכל הקטעים בו עובדו על ידי ביל אוונס ושנחשב לאחד ממגדירי סגנון הג'אז המודאלי. המלודיות הפשוטות יחסית שרובן הולחנו על ידי מיילס דייוויס קיבלו גוון ייחודי בזכות האלתורים של קולטריין, הנחשבים בעיני רבים לגאוניים. במאמר בדאון ביט טבע המבקר איירה גיטלר את הביטוי "גיליונות צליל" (sheets of sound) כדי לתאר את המרקם הצלילי שיצר קולטריין בתקליט זה - "מפלים" של מאות תווים בדקה. עוד הקליט עד אפריל 1960 יחד עם דייוויס את "Milestones" ואת "Miles &amp; Monk at Newport" שהוא חגיגה של בי בופ שוצף ללחנים של ת'לוניוס מונק, צ'ארלי פארקר, דיזי גילספי ומיילס דייוויס. לאחר הקלטות אלה לא ישוב עוד קולטריין לבי בופ.
Giant Steps.
ממחצית 1960 פתח קולטריין בקריירה עצמאית, אשר, לדברי המוזיקולוג שי כהן, נבעה כתוצאה מהשפעו של ניקולס סלונימסקי. המסמן הראשון של דרכו החדשה של קולטריין היה תקליטו "Giant Steps" שיצר בAtlantic Records. התקליט, שכולו לחנים של קולטריין, שכמה מהם, כמו "נעימה" ("Naima"), "Giant Steps", "Cousin Mary", "Countdown" ו-"Mr. P.C" הפכו לסטנדרטים של ג'אז מודרני. אלתוריו של קולטריין החלו להשמע כסילסולים של מוזיקה ערבית, אליה נחשף באמצעות אשתו נעימה וחברו יוסף לטיף והמבנים ההרמוניים שהקים היו מן המורכבים והמסובכים ביותר שנשמעו עד אז. תקליט זה מסמל את תחילת מסע החיפוש הבלתי נגמר של קולטריין אחר צלילים חדשים ואפשרויות ביטוי נרחבות יותר. לדברי איש הג'אז הישראלי יוסי אקצ'וטי "'Giant Steps' היא כותרת מטעה במובן הזה. קולטריין עשה צעד אחרי צעד, הוא לא קפץ ולא צלל, ובכך הוא הדגיש יותר מכל מוזיקאי ג'אז לפניו את החשיבות של התהליך.".