دمج الفرز في جافا

يجب على كل مبرمج أن يفكر في البداية في مخطط/خطة/بنية العمل المستقبلي، وإلا سينتهي الأمر كله في حالة من الفوضى، مع فوضى كاملة. كما هو الحال مع أي مشاركة، تحتاج في البداية إلى خطة، فلنبدأ.

• 1) لنأخذ موضوع نوع الدمج للمبتدئين.
• 2) سنقوم بإنشاء بنية وخطة لمزيد من العمل.
• 3) سنعمل على شرح جميع أجزاء الخطة ووصفها.
• 4) دعونا نتحقق من الأداء والجودة.

• 2.1) ما هو دمج الفرز.
• 2.2) وصف التوقيعات المحتملة.
• 2.3) أعط مثالا.
• 2.4) وصف التنفيذ في Java باستخدام مثال.
• 2.5) أي شيء إضافي.

دمج - دمج الفرز في جافا

يتضمن مبدأ "فرق تسد". ما هي الفكرة ومعناها؟

1. فرز.

   نقوم بتقسيم المصفوفة إلى أجزاء حتى تساوي عنصرًا واحدًا. يتم فرز كل عنصر واحد.

2. الاندماج.

   دمج العناصر المصنفة.
   بناءً على مبدأ مجموعتين من البطاقات. نضع مجموعتين من البطاقات على الطاولة مع رفع قيمهما، ويتم وضع البطاقة الأدنى في الكومة الثالثة الناتجة من البطاقات. في النهاية، إذا نفدت أوراقنا في مجموعة معينة، فإننا ننقلها واحدة تلو الأخرى إلى المجموعة الناتجة. ستكون النتيجة دمج صفيفين مفروزين، ومصفوفة واحدة جديدة مفروزة.

الوقت المستغرق هو O(n log2 n). يعتبر الفرز سريعًا جدًا. باختصار حول التعقيد الخوارزمي، إذا احتاجه أي شخص، يمكنك غالبًا رؤية وظائف مثل:

Sort(A, p, q);
Merge(A, p, q, r);

هذا هو نفس الشيء تقريبًا، مرتبط فقط بالفهارس. والمتغيرات فيها هي:

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

وإذا لم يتم وصف هذه المتغيرات فإن الذي يطلب القيام بهذه الوظيفة بنفسه لا يعرف ماذا يريد. وسيتعين عليك البحث في Google لمعرفة ماهيته، ومن المحتمل أن تجده، ربما. دعونا نعطي مثالا على الفرز لدينا. توجد مصفوفة {6, 1, 3, 5, 2, 4, 7, 8}إذا كان طولها أكبر من 1 نقسمها إلى قسمين ونحصل على الجزء الأيسر {6, 1, 3, 5}والجزء الأيمن {2, 4, 7, 8}. نواصل عملية التقسيم إلى جزأين حتى يصبح طوله أكبر من 1. ونتيجة لذلك، نحصل على مجموعة من المصفوفات بطول عنصر واحد، وهي: {6} {1} {3} {5} {2} {4} {7} {8}. التنفيذ في Java يشبه هذا:

public int [] sortArray(int[] arrayA){ // sorting Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

بعد ذلك تحتاج إلى دمج هذه المصفوفات في 1. كيف يتم ذلك؟ لتجنب المرور عبر كل مصفوفة عدة مرات، دعنا ندخل مؤشرات الموضع لكل مصفوفة. ثم سنمر عبر حلقة مرة واحدة، تساوي طول مجموع هاتين المصفوفتين. خذ المصفوفة الأولى والمصفوفة الثانية، وخذ العنصر الأول، وقارن العنصر رقم 1 في المصفوفة الأولى والعنصر رقم 1 في المصفوفة الثانية ؟ يتم وضع الأصغر في المصفوفة الناتجة. من المهم هنا أنه إذا أخذنا عنصرًا من المصفوفة الأولى، فعندما تمر الحلقة، يجب أن يشير إلى العنصر الثاني من المصفوفة الأولى وإلى العنصر الأول من المصفوفة الثانية. للقيام بذلك، تحتاج إلى زيادة فهرس المصفوفة الثانية بمقدار +1، وعند التحقق، قم بطرحه من رقم الدورة، وبالمثل بالنسبة للمصفوفة الأولى. هل من الواضح لماذا تفعل هذا؟ أم أنه لا يوجد شيء واضح على الإطلاق؟ :-) على سبيل المثال، هناك مصفوفتان: {1}{4}{8}و {3}{6}{7} هناك حلقة:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

في المرور الأول للحلقة، اتضح أننا arrayC[1] = {1}أخذنا هذا العنصر من المصفوفة الأولى. بعد ذلك، عند المرور بالحلقة الثانية، يجب علينا بالفعل مقارنة العنصر {4}و {3}، ولكن للقيام بذلك، نحتاج إلى مراعاة مؤشرات الموضع وإزاحة كلا المصفوفتين، ولهذا ندخلهما.

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

ولكن هذا ليس كل شيء، عليك أن تأخذ في الاعتبار أن بعض المصفوفات قد تنتهي في وقت سابق. على سبيل المثال، هناك 3 صفائف: {1}{3}{5}وستنتهي {6}{7}{9} المصفوفة الأولى قبل وصول المصفوفة الثانية، ولهذا تحتاج إلى إدخال شيك، ومن حيث المبدأ، تكون وظيفة الدمج جاهزة.

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

أصعب شيء في هذا الفرز هو مبدأ انتقال العودية. أولئك. نرمي الجانب الأيسر في العودية حتى يصبح قابلاً للقسمة على 2، ثم نعيده مرة أخرى، بالكلمات، الأمر معقد ومربك للغاية، ولكن عندما تحاول التخيل، إذا لم يكن الأمر واضحًا بعد، فهي فوضى كاملة. لنأخذ المصفوفة : {2}{1}{4}{3}. ستؤدي عملية الفرز الأولى إلى تقسيمها إلى جزأين وتشغيل الوظيفة مرة أخرى مع العناصر 2-1 ، ثم مرة أخرى مع العنصرين 2 و 1 ، وإعادتهما بدورهما، بحيث يدخلان في وظيفة الدمج أولاً، وسيأتي 1-2 خارج ، ثم ستعود العودية مرة أخرى وترمي 4-3 في الدمج ، ثم 4 و 3 ، وبعد ذلك سيعود الدمج 3-4 ، وعندها فقط ستدور العودية مرة أخرى وستعود 1-2 و3-4 سيتم تضمينها في الدمج ، وسيتم إرجاع المصفوفة التي تم فرزها 1-2-3-4 . حسنًا، هذا كل شيء، الفرز يتكون من وظيفتين.

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

إذا قمت بكتابة نوع ما من الرئيسي، سوف تحصل على شيء مثل:

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

بالنسبة لي، كان هذا الفرز فاشلا تماما، كان هناك مليون سؤال، ولكن لا توجد إجابات، لقد بحثت في الإنترنت بالكامل، وأعدت القراءة، وشاهدت مجموعة من مقاطع الفيديو، ولكن كما هو الحال دائمًا، وجدت الإجابات بنفسي فقط. وفقط عندما بدأت في كتابة حل مختلف تمامًا عن الحل الذي يومض في كل مكان) ولكن في النهاية اتضح أنه مشابه لجميع الحلول الأخرى))) الفرز هو في الواقع أبسط شيء، والشيء الرئيسي هو تقديمه بشكل تفاعلي أثناء العمل، و كل شيء سيكون في مكانه إذا تمكنت من ذلك، سأصنع مقطع فيديو)))) حتى الآن، هذا كل ما اكتفيت منه: فرز الدمج فرز الدمج أهم شيء هو أن تضع دائمًا خطة من البداية. من الأفضل أن تنتظر قليلاً وتفكر قبل أن تبدأ بفعل أي شيء. قد يستغرق الأمر المزيد من الوقت، لكن الفهم والحل سيظهران بدلاً من الاضطرار إلى إعادة كتابته عدة مرات والتوصل إلى عكازين. شكرا لكم جميعا على وقتكم، ونتمنى لك التوفيق والمزاج الجيد. ) ملاحظة: النقد، الجيد والسيئ، وكذلك الأسئلة هي موضع ترحيب كبير. )))