מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/אלגוריתמים למיון בזמן לינארי/תרגילים

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

שאילתות על מספר איברים בתחום[עריכה]

שאלה[עריכה]

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

  1. Init מקבלת את המערך A והערך , ומבצעת פעולות אתחול כלשהן.
  2. Range מקבלת שני מספרים a וb, ומחזירה כמה מאיברי A נמצאים בין שני המספרים.להלן דוגמה לשימוש אפשרי:
1	A = [1, 3, 2, 3, 3, 3, 15, 3]

	# Initializes whatever is needed
2	Init(A, 15)

	# Prints 8.
3	Print( Range(1, 16) )

	# Prints 1.
4	Print( Range(1, 1) )

	# Prints 1.
5	Print( Range(2, 2) )

	# Prints 7.
6	Print( Range(1, 14) )

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

תשובה[עריכה]

הפתרון דומה מאד למיון ספירה. ראשית, הנה הפסוודו-קוד לInit:

# A global array.
1	Count

Init(Values, k)
1	Count = Make-Array(k)

2	for i in [1, ..., k]
3		Count[i] = 0
	
4	for j in [1, ..., Length(Values))
5		value = Values[j]
6		++Count[value]
	
7	for i in [2, ..., k]
8		Count[i] = Count[i] + Count[i - 1]

המערך Count הוא משתנה גלובלי. הפונקציה Range מאתחלת אותו כך שהאיבר הi שלו מכיל את מספר האיברים הקטנים או שווים לi בA. בניתוח מיון ספירה ראינו שהסיבוכיות היא .

לאחר שאתחלנו את המערך Count, הפונקציה Range פשוטה מאד. כל שעלינו לעשות הוא לחסר את מספר האיברים הקטנים מa ממספר האיברים הקטנים או שווים לb:

Range(a, b)
	# First find the number of values less than a.
1	if a == 1
2		less-than-a = 0
3	else if a - 1  Length(Count)
4		less-than-a = Count[a - 1]
5	else
6		less-than-a = Count[Length(Count)]

	# Now find the number of values less than or equal to b.

7	if b  Length(Count)
8		at-most-b = Count[b] 
9	else
10		at-most-b = Count[Length(Count)]
	
	# The answer is obviously the difference between the two.
11	return at-most-b - less-than-a

קל לראות שהסיבוכיות היא .