بسم الله الرحمن الرحيم
ما هو shell sort ؟
هو أمتداد لل insertion sort لترتيب العناصر بالتبديل
ملاحظة : لترتيب مصفوفة عددها زوجي نقسم علي 2 للحصول علي عدد بداية التحرك
الفردي نأخد العدد السابق له ونقسم علي 2 للحصول علي عدد ابداية التحرك
مثال :
قم بترتيب العناصر التالية تصاعدياً بأستخدام shell sort
{9,6,3,12}
عدد المصفوفة زوجي اربعة أعداد نقسم علي أثنان عدد بداية التحرك = 2
البداية العدد 9 نحرك بمقدرار اثنان نجد العدد 3 يقارن بالعدد 9 ويتم التبديل بينهما
تصبح المصفوفة
3,6,9,12
ثم نقارن العدد 6 مع العدد 12 ولا يتم التبديل
نتوقف هنا لانه لا يوجد عدد يقارن بالعدد 9
ونلاحظ ان المصفوفة أصبحت مرتبة أن لم تكن مرتبة بدأ بمقارنة العدد بالعدد التالي له في المرحلة التالية ويكون عدد التحرك = 1 لكن هنا أصبحت المصفوفة مرتبة
3,6,9,12
Time complexity = o(n^2)
كود الجافا
public char[] shellSort(char[] chars) {
int n = chars.length;
int increment = n / 2;
while(increment > 0) {
int last = increment;
while(last < n) {
int current = last - increment;
while(current >= 0) {
if(chars[current] > chars[current + increment]) {
//swap
char tmp = chars[current];
chars[current] = chars[current + increment];
chars[current + increment] = tmp;
current -= increment;
}
else { break; }
}
last++;
}
increment /= 2;
}
return chars;
}
لمتابعة الحلقة السابقة
لمتابعة الحلقة التالية
ليست هناك تعليقات:
إرسال تعليق