گو
آموزش الگوریتم در زبان گو - مرتب سازی درجی (insertion sort)

نویسنده

محمد جعفر ابراهیمی

17 مرداد 1400 / 1 دقیقه خواندن



الگوریتم مرتب سازی درجی (selection sort) از جمله الگوریتم های کلاسیک محسوب میشه که در اون میشه یه سری از مباحثی مثل جا به جایی (swap) دو فیلد از آرایه و حلقه نزولی رو تمرین کرد.

کارکرد الگوریتم به این صورته که هر کدوم از فیلد های آرایه رو پیمایش میکنه و آیتم فعلی آرایه رو با آیتم قبلی مقایسه میکنه و در صورتی که از کوچک تر بود جا به جا میکنه و این جا به جایی باید با تمام آیتم های قبلی انجام بشه این الگوریتم به دو صورت نوشته میشه که سعی میکنم هر دو رو پیاده سازی کنم.

پیمایش در آرایه

arr := [7]int16{32, 53, 21, 452, 22, 5, 222}

for i := 1; i < len(arr); i++ {
    // map array items
}

در اینجا ما از آرایه دوم شروع میکنیم چون هر آرایه ای که یک عضو داشته باشد مرتب است

arr := [7]int16{32, 53, 21, 452, 22, 5, 222}

for i := 1; i < len(arr); i++ {
    for j := i; j > 0; j-- {
        
    }
}

حالا برای پیمایش آرایه های قبل آرایه فعلی نیاز داریم به صورت نزولی اون ها رو پیمایش کنیم

arr := [7]int16{32, 53, 21, 452, 22, 5, 222}

for i := 1; i < len(arr); i++ {
    for j := i; j > 0; j-- {
        if arr[j] < arr[j-1] {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
}
fmt.Println(arr)

حالا در این پیمایش هر کدوم از اعضای آرایه رو با عضو قبلیش بررسی میکنیم وقتی کوچکتر بود اون هارو جا به جا میکنیم

arr := [7]int16{32, 53, 21, 452, 22, 5, 222}

for i := 1; i < len(arr); i++ {
	curr := arr[i]
	j := i
	for ; j > 0 && curr < arr[j-1]; j-- {
		arr[j] = arr[j-1]
	}
	arr[j] = curr
}

fmt.Println(arr)

روش دوم هم یکی از مرسوم ترین روش هاست که در اون ابتدا عضو فعلی آرایه رو نگه میداریم و بعد با پیمایش در اغضای قبلی درصورت بزرگتر بودن از عضو فعلی آرایه به سمت بالا جا به جا میکنیم

go
algorithm
الگوریتم
زبان گو
گولنگ
selection sort
مرتب سازی
مرتب سازی درجی
sort

نویسنده

محمد جعفر ابراهیمی

© استفاده از مطالب سایت تنها با درج لینک مستقیم به آن مطلب مجاز است.