האם זה נחשב לחיפוש בינארי

BinaryS(A,x)
i<--length[A]

j<--|i/2|

do if A[j]>x

then j--<|j/2|

else if A[j]<x

then j-->|j+j/2|

else return j

until j<1 or j>i

return 0

ה-| | הכוונה לערך השלם הקטן

כן

כן

גם אני חשבתי כך אך איך ניתן לומר זאת באופן גורף?

חשבתי על זה שזמן הריצה במקרה הגרוע הוא

O(lgn)

כמו באלגוריתם חיפוש בינארי רגיל.

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

זה מלא באגים ופשוט יקרוס

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

זה מלא באגים ופשוט יקרוס

אילו באגים?

האלגוריתם פשוט לא נכון

תחשוב שמה שאתה מחפש נמצא בתא האחרון שמערך בגודל 12

בסיבוב הראשון j=6

בסיבוב השני j=9

בסיבוב השלישי j=13.5, אתה יוצא מהתחום של המערך והלך עליך

האלגוריתם פשוט לא נכון

תחשוב שמה שאתה מחפש נמצא בתא האחרון שמערך בגודל 12

בסיבוב הראשון j=6

בסיבוב השני j=9

בסיבוב השלישי j=13.5, אתה יוצא מהתחום של המערך והלך עליך

אבל רשמתי שה-| | הכוונה לערך השלם הקטן

ז"א

למשל |x| מציין את החלק השלם הגדול ביותר הקטן מ-X או שווה לו.

נו ברור

אבל עדיין j=13 נמצא מחוץ למערך

נו ברור

אבל עדיין j=13 נמצא מחוץ למערך

וואלה צודק

נניח i=12

j=6

x=11 -הערך שאנו מחפשים נמצא בתא האחרון

והמערך הוא

11 12 8 7 9 10 6 3 2 1 5 4

אז בסיבוב השני j=|6+6\2|=9 כי 6 קטן מ11

ואז בשלישי j=|9+9\2|=13 כי עדיין 7 קטן מ11

[br]פורסם בתאריך: 8.11.2008 בשעה 17:36:26

---

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

SELECTION SORT(A)
1. for i<-- n-1 to 1
2. do max<--i
3.  for j<--n to i+1
4. do if A[max]<A[j]
5.  then max<--j
6.   exchange A<--> A[max]

האם זה נכון מבחינה אלגוריתמית?

יש לך בויקיפדיה פסודו קוד של כל אלגוריתם מיון פופלארי:

http://en.wikipedia.org/wiki/Selection_sort#Pseudo-code

יש לך בויקיפדיה פסודו קוד של כל אלגוריתם מיון פופלארי:

http://en.wikipedia.org/wiki/Selection_sort#Pseudo-code

כן תודה ראיתי אבל אני רוצה לבנות אותו מחדש

למשל הוא היה נתון כך

SELECTION SORT(A)
1. for i<--1 to n-1
2. do min<--i
3.  for j<--i+1 to n
4. do if A[min]>A[j]
5.  then min<--j
6.   exchange A<--> A[min]

ואני רוצה שמיון הבחירה ימיין החל מהגדול ביותר לקטן ביותר