الترتيب بالعد

Go

/* الترتيب بالعد */
// تنفيذ بسيط، لا يصلح لترتيب الكائنات
func countingSortNaive(nums []int) {
	// 1. عدّ أكبر عنصر m في المصفوفة
	m := 0
	for _, num := range nums {
		if num > m {
			m = num
		}
	}
	// 2. عدّ مرات ظهور كل عدد
	// يمثّل counter[num] عدد مرات ظهور num
	counter := make([]int, m+1)
	for _, num := range nums {
		counter[num]++
	}
	// 3. اجتز counter، واكتب كل عنصر مرة أخرى في المصفوفة الأصلية nums
	for i, num := 0, 0; num < m+1; num++ {
		for j := 0; j < counter[num]; j++ {
			nums[i] = num
			i++
		}
	}
}

TypeScript

/* الترتيب بالعد */
// تنفيذ بسيط، لا يصلح لترتيب الكائنات
function countingSortNaive(nums: number[]): void {
    // 1. عدّ أكبر عنصر m في المصفوفة
    let m: number = Math.max(...nums);
    // 2. عدّ مرات ظهور كل عدد
    // يمثّل counter[num] عدد مرات ظهور num
    const counter: number[] = new Array<number>(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. اجتز counter، واكتب كل عنصر مرة أخرى في المصفوفة الأصلية nums
    let i = 0;
    for (let num = 0; num < m + 1; num++) {
        for (let j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

Go

/* الترتيب بالعد */
// تنفيذ كامل، يمكنه ترتيب الكائنات وهو ترتيب مستقر
func countingSort(nums []int) {
	// 1. عدّ أكبر عنصر m في المصفوفة
	m := 0
	for _, num := range nums {
		if num > m {
			m = num
		}
	}
	// 2. عدّ مرات ظهور كل عدد
	// يمثّل counter[num] عدد مرات ظهور num
	counter := make([]int, m+1)
	for _, num := range nums {
		counter[num]++
	}
	// 3. احسب المجموع البادئ لـcounter، وحوّل «عدد مرات الظهور» إلى «فهرس الذيل»
	// counter[num]-1 هو آخر فهرس يظهر فيه num في res
	for i := 0; i < m; i++ {
		counter[i+1] += counter[i]
	}
	// 4. اجتز nums بترتيب عكسي، وضع كل عنصر في المصفوفة الناتجة res
	// هيّئ المصفوفة res لتسجيل النتائج
	n := len(nums)
	res := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		num := nums[i]
		// ضع num عند الفهرس المقابل
		res[counter[num]-1] = num
		// قلّل المجموع البادئ بمقدار 1 للحصول على الفهرس التالي لوضع num
		counter[num]--
	}
	// استخدم المصفوفة الناتجة res لاستبدال المصفوفة الأصلية nums
	copy(nums, res)
}

TypeScript

/* الترتيب بالعد */
// تنفيذ كامل، يمكنه ترتيب الكائنات وهو ترتيب مستقر
function countingSort(nums: number[]): void {
    // 1. عدّ أكبر عنصر m في المصفوفة
    let m: number = Math.max(...nums);
    // 2. عدّ مرات ظهور كل عدد
    // يمثّل counter[num] عدد مرات ظهور num
    const counter: number[] = new Array<number>(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. احسب المجموع البادئ لـcounter، وحوّل «عدد مرات الظهور» إلى «فهرس الذيل»
    // counter[num]-1 هو آخر فهرس يظهر فيه num في res
    for (let i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. اجتز nums بترتيب عكسي، وضع كل عنصر في المصفوفة الناتجة res
    // هيّئ المصفوفة res لتسجيل النتائج
    const n = nums.length;
    const res: number[] = new Array<number>(n);
    for (let i = n - 1; i >= 0; i--) {
        const num = nums[i];
        res[counter[num] - 1] = num; // ضع num عند الفهرس المقابل
        counter[num]--; // قلّل المجموع البادئ بمقدار 1 للحصول على الفهرس التالي لوضع num
    }
    // استخدم المصفوفة الناتجة res لاستبدال المصفوفة الأصلية nums
    for (let i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}