https://wiki.hsoub.com/index.php?title=Algorithms/shell_sort&feed=atom&action=history
Algorithms/shell sort - تاريخ المراجعة
2024-03-29T01:34:20Z
تاريخ التعديل لهذه الصفحة في الويكي
MediaWiki 1.35.0
https://wiki.hsoub.com/index.php?title=Algorithms/shell_sort&diff=29634&oldid=prev
جميل-بيلوني في 10:21، 3 مارس 2020
2020-03-03T10:21:39Z
<p></p>
<table class="diff diff-contentalign-right diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ar">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">→ مراجعة أقدم</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">مراجعة 10:21، 3 مارس 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >سطر 1:</td>
<td colspan="2" class="diff-lineno">سطر 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><noinclude>{{DISPLAYTITLE:خوارزمية شِل للترتيب}}</noinclude></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><noinclude>{{DISPLAYTITLE:خوارزمية شِل للترتيب}}</noinclude></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>خوارزمية شِل للترتيب Shell sort هي شكل آخر لخوارزمية [[Algorithms/insertion sort|الترتيب بالإدراج Insertion Sort]]. نحرّك العناصر موقعًا واحدًا إلى الأمام فقط في خوارزمية الترتيب بالإدراج، وإن لَزِم تحريك العنصر أبعد من ذلك يجب تحريك العنصر لخطوات متعددة. تهدف خوارزمية ترتيب شِل إلى السماح بإجراء عملية تبادل مع العناصر البعيدة.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>خوارزمية شِل للترتيب Shell sort هي شكل آخر لخوارزمية [[Algorithms/insertion sort|الترتيب بالإدراج Insertion Sort]]. نحرّك العناصر موقعًا واحدًا إلى الأمام فقط في خوارزمية الترتيب بالإدراج، وإن لَزِم تحريك العنصر أبعد من ذلك يجب تحريك العنصر لخطوات متعددة. تهدف خوارزمية ترتيب شِل إلى السماح بإجراء عملية تبادل مع العناصر البعيدة.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
جميل-بيلوني
https://wiki.hsoub.com/index.php?title=Algorithms/shell_sort&diff=29030&oldid=prev
Mohammed Taher: /* التعقيد الزمني */
2019-09-30T21:14:24Z
<p><span dir="auto"><span class="autocomment">التعقيد الزمني</span></span></p>
<table class="diff diff-contentalign-right diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ar">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">→ مراجعة أقدم</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">مراجعة 21:14، 30 سبتمبر 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l174" >سطر 174:</td>
<td colspan="2" class="diff-lineno">سطر 174:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== التعقيد الزمني ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== التعقيد الزمني ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>يبلغ التعقيد الزمني لطريقة التنفيذ الموضحة في الأمثلة أعلاه المقدار <code>O(<del class="diffchange diffchange-inline">n2</del>)</code>. تُقلّص الفجوة في الأمثلة إلى النصف في كل دورة من دورات الحلقة التكرارية، وهناك طرق أخرى لتقليص مقدار الفجوة تؤدي إلى الحصول على تعقيد زمني أفضل.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>يبلغ التعقيد الزمني لطريقة التنفيذ الموضحة في الأمثلة أعلاه المقدار <code>O(<ins class="diffchange diffchange-inline">n<sup>2</sup></ins>)</code>. تُقلّص الفجوة في الأمثلة إلى النصف في كل دورة من دورات الحلقة التكرارية، وهناك طرق أخرى لتقليص مقدار الفجوة تؤدي إلى الحصول على تعقيد زمني أفضل.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== مصادر ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== مصادر ==</div></td></tr>
</table>
Mohammed Taher
https://wiki.hsoub.com/index.php?title=Algorithms/shell_sort&diff=29029&oldid=prev
Mohammed Taher في 21:13، 30 سبتمبر 2019
2019-09-30T21:13:50Z
<p></p>
<table class="diff diff-contentalign-right diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ar">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">→ مراجعة أقدم</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">مراجعة 21:13، 30 سبتمبر 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >سطر 1:</td>
<td colspan="2" class="diff-lineno">سطر 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><noinclude>{{DISPLAYTITLE:خوارزمية شِل للترتيب}}</noinclude></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><noinclude>{{DISPLAYTITLE:خوارزمية شِل للترتيب}}</noinclude></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>خوارزمية شِل للترتيب Shell sort هي شكل آخر لخوارزمية الترتيب بالإدراج Insertion Sort. نحرّك العناصر موقعًا واحدًا إلى الأمام فقط في خوارزمية الترتيب بالإدراج، وإن لَزِم تحريك العنصر أبعد من ذلك يجب تحريك العنصر لخطوات متعددة. تهدف خوارزمية ترتيب شِل إلى السماح بإجراء عملية تبادل مع العناصر البعيدة.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>خوارزمية شِل للترتيب Shell sort هي شكل آخر لخوارزمية <ins class="diffchange diffchange-inline">[[Algorithms/insertion sort|</ins>الترتيب بالإدراج Insertion Sort<ins class="diffchange diffchange-inline">]]</ins>. نحرّك العناصر موقعًا واحدًا إلى الأمام فقط في خوارزمية الترتيب بالإدراج، وإن لَزِم تحريك العنصر أبعد من ذلك يجب تحريك العنصر لخطوات متعددة. تهدف خوارزمية ترتيب شِل إلى السماح بإجراء عملية تبادل مع العناصر البعيدة.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>ترتب خوارزمية شِل المصفوفة بالنسبة لقيمة كبيرة من <code>h</code> ، ثم تستمر في تقليص قيمة <code>h</code> إلى حين الوصول إلى <code>1</code>. تسمى المصفوفة <code>h-sorted</code> إذا كانت جميع المصفوفات الفرعية لكل <code>h</code> عنصر مرتّبة.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>ترتب خوارزمية شِل المصفوفة بالنسبة لقيمة كبيرة من <code>h</code> ، ثم تستمر في تقليص قيمة <code>h</code> إلى حين الوصول إلى <code>1</code>. تسمى المصفوفة <code>h-sorted</code> إذا كانت جميع المصفوفات الفرعية لكل <code>h</code> عنصر مرتّبة.</div></td></tr>
</table>
Mohammed Taher
https://wiki.hsoub.com/index.php?title=Algorithms/shell_sort&diff=29028&oldid=prev
Mohammed Taher: أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:خوارزمية شِل للترتيب}}</noinclude> خوارزمية شِل للترتيب Shell sort هي شكل آخر لخوارزمية...'
2019-09-30T21:13:18Z
<p>أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:خوارزمية شِل للترتيب}}</noinclude> خوارزمية شِل للترتيب Shell sort هي شكل آخر لخوارزمية...'</p>
<p><b>صفحة جديدة</b></p><div><noinclude>{{DISPLAYTITLE:خوارزمية شِل للترتيب}}</noinclude><br />
<br />
خوارزمية شِل للترتيب Shell sort هي شكل آخر لخوارزمية الترتيب بالإدراج Insertion Sort. نحرّك العناصر موقعًا واحدًا إلى الأمام فقط في خوارزمية الترتيب بالإدراج، وإن لَزِم تحريك العنصر أبعد من ذلك يجب تحريك العنصر لخطوات متعددة. تهدف خوارزمية ترتيب شِل إلى السماح بإجراء عملية تبادل مع العناصر البعيدة.<br />
<br />
ترتب خوارزمية شِل المصفوفة بالنسبة لقيمة كبيرة من <code>h</code> ، ثم تستمر في تقليص قيمة <code>h</code> إلى حين الوصول إلى <code>1</code>. تسمى المصفوفة <code>h-sorted</code> إذا كانت جميع المصفوفات الفرعية لكل <code>h</code> عنصر مرتّبة.<br />
<br />
== أمثلة ==<br />
<br />
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:<br />
<br />
* '''C++''':<br />
<br />
<source lang="c++">#include <iostream> <br />
using namespace std; <br />
<br />
int shellSort(int arr[], int n) <br />
{ <br />
// البدء بفجوة كبيرة ثم تقليص هذه الفجوة<br />
for (int gap = n/2; gap > 0; gap /= 2) <br />
{ <br />
// إجراء عملية الترتيب بالإدراج باستخدام مقدار الفجوة المعطى.<br />
// أولى العناصر في الفجوة <br />
// a[0..gap-1]<br />
// مرتّبة أصلًا<br />
// نستمر في إضافة عنصر إضافي إلى أن تصبح المصفوفة كلها مرتّبة<br />
for (int i = gap; i < n; i += 1) <br />
{ <br />
// نضيف هذا العنصر إلى العناصر التي جرى ترتيبها<br />
// نحفظ هذا العنصر في متغير مؤقت ثم نحدث ثغرة في موقعه<br />
int temp = arr[i]; <br />
<br />
// نزيح جميع العناصر المرتّبة مسبقًا إلى حين العثور<br />
// a[i] على الموقع الصحيح للعنصر <br />
int j; <br />
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) <br />
arr[j] = arr[j - gap]; <br />
<br />
// نضع العنصر المخزن في المتغير المؤقت في مكانه الصحيح<br />
arr[j] = temp; <br />
} <br />
} <br />
return 0; <br />
} <br />
<br />
void printArray(int arr[], int n) <br />
{ <br />
for (int i=0; i<n; i++) <br />
cout << arr[i] << " "; <br />
} <br />
<br />
int main() <br />
{ <br />
int arr[] = {12, 34, 54, 2, 3}, i; <br />
int n = sizeof(arr)/sizeof(arr[0]); <br />
<br />
cout << "Array before sorting: \n"; <br />
printArray(arr, n); <br />
<br />
shellSort(arr, n); <br />
<br />
cout << "\nArray after sorting: \n"; <br />
printArray(arr, n); <br />
<br />
return 0; <br />
} <br />
</source><br />
* '''بايثون''':<br />
<br />
<source lang="python"><br />
def shellSort(arr): <br />
<br />
# البدء بفجوة كبيرة ثم تقليص هذه الفجوة<br />
n = len(arr) <br />
gap = n//2<br />
<br />
<br />
<br />
# إجراء عملية الترتيب بالإدراج باستخدام مقدار الفجوة المعطى.<br />
# أولى العناصر في الفجوة <br />
# a[0..gap-1]<br />
# مرتّبة أصلًا<br />
# نستمر في إضافة عنصر إضافي إلى أن تصبح المصفوفة كلها مرتّبة <br />
while gap > 0: <br />
<br />
for i in range(gap,n): <br />
# نضيف هذا العنصر إلى العناصر التي جرى ترتيبها<br />
# نحفظ هذا العنصر في متغير مؤقت ثم نحدث ثغرة في موقعه<br />
temp = arr[i] <br />
# نزيح جميع العناصر المرتّبة مسبقًا إلى حين العثور<br />
# a[i] على الموقع الصحيح للعنصر <br />
j = i <br />
while j >= gap and arr[j-gap] >temp: <br />
arr[j] = arr[j-gap] <br />
j -= gap <br />
<br />
<br />
# نضع العنصر المخزن في المتغير المؤقت في مكانه الصحيح<br />
arr[j] = temp <br />
gap //= 2<br />
<br />
<br />
# اختبار الدوال السابقة<br />
arr = [ 12, 34, 54, 2, 3] <br />
<br />
n = len(arr) <br />
print ("Array before sorting:") <br />
for i in range(n): <br />
print(arr[i]), <br />
<br />
shellSort(arr) <br />
<br />
print ("\nArray after sorting:") <br />
for i in range(n): <br />
print(arr[i]), </source><br />
* '''جافا''':<br />
<br />
<source lang="java">class ShellSort <br />
{ <br />
/* دالة مساعدة لطباعة محتويات المصفوفة */<br />
static void printArray(int arr[]) <br />
{ <br />
int n = arr.length; <br />
for (int i=0; i<n; ++i) <br />
System.out.print(arr[i] + " "); <br />
System.out.println(); <br />
} <br />
<br />
int sort(int arr[]) <br />
{ <br />
int n = arr.length; <br />
<br />
// البدء بفجوة كبيرة ثم تقليص هذه الفجوة <br />
for (int gap = n/2; gap > 0; gap /= 2) <br />
{ <br />
// إجراء عملية الترتيب بالإدراج باستخدام مقدار الفجوة المعطى.<br />
// أولى العناصر في الفجوة <br />
// a[0..gap-1]<br />
// مرتّبة أصلًا<br />
// نستمر في إضافة عنصر إضافي إلى أن تصبح المصفوفة كلها مرتّبة <br />
for (int i = gap; i < n; i += 1) <br />
{ <br />
// نضيف هذا العنصر إلى العناصر التي جرى ترتيبها<br />
// نحفظ هذا العنصر في متغير مؤقت ثم نحدث ثغرة في موقعه<br />
int temp = arr[i]; <br />
<br />
// نزيح جميع العناصر المرتّبة مسبقًا إلى حين العثور<br />
// a[i] على الموقع الصحيح للعنصر <br />
int j; <br />
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) <br />
arr[j] = arr[j - gap]; <br />
<br />
// نضع العنصر المخزن في المتغير المؤقت في مكانه الصحيح<br />
arr[j] = temp; <br />
} <br />
} <br />
return 0; <br />
} <br />
<br />
// اختبار الدوال السابقة<br />
public static void main(String args[]) <br />
{ <br />
int arr[] = {12, 34, 54, 2, 3}; <br />
System.out.println("Array before sorting"); <br />
printArray(arr); <br />
<br />
ShellSort ob = new ShellSort(); <br />
ob.sort(arr); <br />
<br />
System.out.println("Array after sorting"); <br />
printArray(arr); <br />
} <br />
} <br />
</source><br />
== التعقيد الزمني ==<br />
<br />
يبلغ التعقيد الزمني لطريقة التنفيذ الموضحة في الأمثلة أعلاه المقدار <code>O(n2)</code>. تُقلّص الفجوة في الأمثلة إلى النصف في كل دورة من دورات الحلقة التكرارية، وهناك طرق أخرى لتقليص مقدار الفجوة تؤدي إلى الحصول على تعقيد زمني أفضل.<br />
<br />
== مصادر ==<br />
<br />
* صفحة [https://www.geeksforgeeks.org/shellsort/ ShellSort] في توثيق الخوارزميات في موقع GeeksforGeeks.<br />
<br />
[[تصنيف: الخوارزميات]]</div>
Mohammed Taher