ادغام مرتب سازی در جاوا

هر برنامه نویسی در ابتدا باید به طرح/طرح/معماری کار آینده فکر کند، در غیر این صورت همه چیز به یک آشفتگی و با هرج و مرج کامل ختم می شود. مانند هر پست دیگری، در ابتدا به یک برنامه نیاز دارید، بیایید شروع کنیم.

• 1) بیایید موضوع Merge Sort را برای مبتدیان در نظر بگیریم.
• 2) ما یک معماری و یک طرح برای کارهای بعدی ایجاد خواهیم کرد.
• 3) ما تمام قسمت های طرح را بررسی کرده و شرح خواهیم داد.
• 4) بیایید عملکرد و کیفیت را بررسی کنیم.

• 2.1) مرتب سازی Merge چیست.
• 2.2) شرح امضاهای احتمالی.
• 2.3) مثال بزنید.
• 2.4) پیاده سازی در جاوا را با استفاده از یک مثال شرح دهید.
• 2.5) هر چیز اضافی.

Merge - ادغام مرتب سازی در جاوا

متضمن اصل "تفرقه بینداز و حکومت کن". ایده و مفهوم آن چیست؟

1. مرتب سازی.

   آرایه را به قسمت هایی تقسیم می کنیم تا برابر با 1 عنصر شود. هر 1 عنصر مرتب شده است.

2. ادغام.

   ادغام عناصر مرتب شده
   بر اساس اصل دو دسته کارت. ما 2 عرشه کارت را با ارزش آنها روی میز قرار می دهیم و کارتی که کمترین مقدار را دارد در سومین انبوه کارت ها قرار می گیرد. در نهایت، اگر کارت‌هایمان در یک دسته خاص تمام شود، آنها را یکی یکی به عرشه حاصل منتقل می‌کنیم. نتیجه ادغام دو آرایه مرتب شده، یک آرایه مرتب شده جدید خواهد بود.

زمان صرف شده O (n log2 n) است. مرتب سازی بسیار سریع در نظر گرفته می شود. به طور خلاصه در مورد پیچیدگی الگوریتمی، اگر کسی به آن نیاز دارد. اغلب می توانید توابعی مانند:

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

این در مورد همان چیزی است که فقط به نمایه ها مرتبط است. متغیرهای موجود در آنها عبارتند از:

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

اگر این متغیرها توضیح داده نشده باشند، آنگاه کسی که خودش می خواهد چنین تابعی را بسازد نمی داند چه می خواهد. و باید گوگل را جستجو کنید تا بفهمید چیست، احتمالاً آن را پیدا خواهید کرد. بیایید یک مثال از مرتب سازی خود ارائه دهیم. یک آرایه وجود دارد {6, 1, 3, 5, 2, 4, 7, 8}که اگر طول آن بزرگتر از 1 باشد، آن را به 2 قسمت تقسیم می کنیم و قسمت چپ {6, 1, 3, 5}و قسمت راست را بدست می آوریم {2, 4, 7, 8}. عمل تقسیم به 2 قسمت را ادامه می دهیم تا طول آن از 1 بیشتر شود. در نتیجه یک دسته آرایه به طول 1 عنصر به دست می آوریم، یعنی: {6} {1} {3} {5} {2} {4} {7} {8}. پیاده سازی در جاوا چیزی شبیه به این است:

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+ افزایش دهید و هنگام بررسی، آن را به طور مشابه برای آرایه اول از شماره چرخه کم کنید. آیا واضح است که چرا باید این کار را انجام داد؟ یا اصلا چیزی مشخص نیست؟ :-) به عنوان مثال، 2 آرایه وجود دارد: {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 قسمت تقسیم می کند و دوباره تابع را با عناصر 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] + " ");
        }
    }

برای من، این مرتب سازی یک شکست کامل بود، میلیون ها سوال وجود داشت، اما هیچ پاسخی وجود نداشت، کل اینترنت را جستجو کردم، دوباره خواندم، مجموعه ای از فیلم ها را تماشا کردم، اما مثل همیشه، فقط پاسخ ها را خودم پیدا کردم. و فقط زمانی که شروع کردم به نوشتن راه حلی کاملاً متفاوت از آنچه که در همه جا چشمک می زند) اما در نهایت شبیه به بقیه بود))) مرتب سازی در واقع ساده ترین است ، نکته اصلی ارائه آن به صورت تعاملی در عمل است و همه چیز سر جای خود قرار می گیرد اگر به آن دست پیدا کنید، من یک ویدیو می سازم)))) تا اینجا، این تمام چیزی است که برای آن کافی بوده است: مرتب سازی ادغام ادغام-مرتب مهم ترین چیز این است که همیشه از آن برنامه ریزی کنید. آغاز. بهتر است قبل از شروع هر کاری کمی صبر کنید و فکر کنید. ممکن است زمان بیشتری طول بکشد، اما به جای اینکه مجبور شوید آن را چند بار بازنویسی کنید و به عصا دست بزنید، یک درک و یک راه حل ظاهر می شود. با تشکر از همه شما برای وقت خود، موفق باشید و روحیه خوب. ) پ.ن: انتقاد، خوب و بد، و همچنین سوال بسیار استقبال می شود. )))