Макала
Баштоо
Үйрөнүүнү баштаңыз
JavaRush /Java блогу /Random-KY /Java'да бириктирүү-сорттоо
vinsler
Деңгээл

Java'да бириктирүү-сорттоо

Группада жарыяланган
Ар бир программист алгач келечектеги иштин схемасын/планын/архитектурасын ойлонушу керек, антпесе анын баары баш аламандыкка, толук анархияга алып келет. Ар кандай посттордогудай эле, алгач план керек, баштайлы.
  • 1) Жаңы баштагандар үчүн бириктирүү сорту темасын алалы.
  • 2) Архитектураны жана мындан аркы иштердин планын түзөбүз.
  • 3) Биз пландын бардык бөлүктөрүн иштеп чыгып, сүрөттөп беребиз.
  • 4) Келгиле, аткарууну жана сапатын текшерип көрөлү.
  • 2.1) Бириктирүү сорттоо деген эмне.
  • 2.2) Мүмкүн болгон колдордун сыпаттамасы.
  • 2.3) Мисал келтириңиз.
  • 2.4) Мисал аркылуу Java тorнде ишке ашырууну сүрөттөп бериңиз.
  • 2.5) Кошумча нерсе.
Бириктирүү сорту Бириктирүү-сорттоо - 1

Бириктирүү - Java'да сортту бириктирүү

«Бөл жана жең» деген принципти билдирет. Идея жана анын мааниси эмнеде?

  1. Сорттоо.

    Массивди 1 элементке барабар болгуча бөлүктөргө бөлөбүз. Ар бир 1 элемент иргелет.

  2. Биригүү.

    Сорттолгон элементтерди бириктирүү.
    Карточкалардын эки палубасынын принцибине негизделген. Биз үстөлгө 2 палуба карталарды алардын баалуулуктары жогору коюп, эң төмөн болгон карта үчүнчү үйүлгөн карталарга жайгаштырылат. Акыр-аягы, белгилүү бир палубада карталар түгөнүп калса, аларды бирден палубага жылдырабыз. Натыйжа эки иреттелген массивдин, бир жаңы, сорттолгон массивдин бириктирorши болот.

Сарпталган убакыт - O(n log2 n). Сорттоо абдан тез деп эсептелет. Алгоритмдик татаалдык жөнүндө кыскача, эгер кимдир бирөө керек болсо. Сиз төмөнкүдөй функцияларды көп көрө аласыз: 
Sort(A, p, q);
Merge(A, p, q, r);
Бул бир эле нерсе, индекстер менен гана байланышкан. Алардагы өзгөрмөлөр: 
A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива
Эгерде бул өзгөрмөлөр сүрөттөлбөсө, анда мындай функцияны жасоону суранган адам эмне каалап жатканын билбейт. Ал эмне экенин билүү үчүн Google'ду карап чыгышыңыз керек болот, балким, таба аласыз. Сорттообузду мисалга келтирели. Массив бар , эгерде анын узундугу 1ден чоң болсо, анда аны 2 бөлүккө бөлүп, сол жана оң бөлүгүн {6, 1, 3, 5, 2, 4, 7, 8}алабыз . Анын узундугу 1ден чоң болмоюнча 2 бөлүккө бөлүү аракетин улантабыз. Натыйжада узундугу 1 элемент болгон массивдердин бир тобун алабыз, тактап айтканда: . Javaда ишке ашыруу төмөнкүдөй: {6, 1, 3, 5}{2, 4, 7, 8}{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 элементти салыштырыңыз ? Кичинекейи алынган массивге жайгаштырылат. Бул жерде маанилүү нерсе, эгерде биз биринчи массивден элемент алган болсок, анда цикл өткөндө, ал биринчи массивдин 2-элементине жана экинчи массивдин 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] + " ");
        }
    }
Мен үчүн бул сорттоо толук ийгorксиз болду, миллиондогон суроолор бар болчу, бирок жооптор жок, мен бүт Интернетти карап чыктым, кайра окудум, бир топ видеолорду көрдүм, бирок ар дайымкыдай эле жоопторду өзүм таптым. Ошондо гана мен бардык жерде жаркырап тургандан такыр башкача чечим жаза баштаганда гана) Бирок акырында ал башкаларга окшош болуп чыкты))) Сорттоо - бул эң жөнөкөй, эң негизгиси аны интерактивдүү түрдө иш жүзүндө көрсөтүү жана баары өз ордуна келет, эгер көнүп алсаң, мен видео тартам)))) Азырынча менде болгону ушул нерсе жетиштүү: Бириктирүү сорттоо Бириктирүү-сорт Эң негизгиси ар дайым башталышы. Кандайдыр бир ишти баштоодон мурун бир аз күтүп, ойлонуп көргөнүңүз оң. Бул көбүрөөк убакытты талап кылышы мүмкүн, бирок аны бир-эки жолу кайра жазып, балдак менен келүүнүн ордуна түшүнүү жана чечим чыгат. Убактыңызды бөлгөнүңүз үчүн рахмат, ийгorк жана жакшы маанай. ) PS: Сын, жакшы жана жаман, ошондой эле суроолор абдан жакшы болот. )))
Комментарийлер
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION