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

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

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

[עריכה] שאלה

נתון מערך 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

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