Java'да көбүктүү сортту ишке ашыруу

Сорттоо алгоритмдеринин кыйла көп саны бар, алардын көбү өтө спецификалык жана тар чөйрөдөгү маселелерди чечүү жана маалыматтардын белгилүү бир түрлөрү менен иштөө үчүн иштелип чыккан. Бирок бул ар түрдүүлүктүн арасында эң жөнөкөй алгоритм каалаган программалоо тorнде ишке ашырыла турган көбүктүү сорт болуп саналат. Жөнөкөйлүгүнө карабастан, ал көптөгөн татаал алгоритмдердин негизинде жатат. Дагы бир маанилүү артыкчылыгы - анын жөнөкөйлүгү, ошондуктан, ал сиздин алдыңызда эч кандай кошумча адабият болбостон, дароо эстеп, ишке ашырылышы мүмкүн.

Киришүү

Бүтүндөй заманбап Интернет маалымат базаларында чогултулган маалымат структураларынын ар кандай түрлөрүнөн турат. Алар колдонуучулардын жеке маалыматтарынан баштап жогорку интеллектуалдык автоматташтырылган системалардын семантикалык өзөгүнө чейин бардык маалыматтарды сакташат. Айта кетчү нерсе, маалыматтарды сорттоо структураланган маалыматтын бул чоң көлөмүндө өтө маанилүү ролду ойнойт. Сорттоо маалымат базасынан кандайдыр бир маалыматты издөөнүн алдында милдеттүү кадам болушу мүмкүн жана программалоодо сорттоо алгоритмдерин билүү абдан маанилүү ролду ойнойт.

Машинанын көзү жана адамдын көзү менен сорттоо

Келгиле, ар кандай бийиктиктеги 5 мамычаны өсүү тартибинде иреттөө керек деп элестетип көрөлү. Бул тилкелер ар кандай маалыматты билдире алат (акциялардын баалары, байланыш каналынын өткөрүү жөндөмдүүлүгү ж.б.); аны ачык-айкын кылуу үчүн бул тапшырманын айрым versionларын көрсөтсөңүз болот. Мисалы, биз Өч алуучуларды бийиктиги боюнча иреттейбиз: Компьютердик программадан айырмаланып, сорттоо сиз үчүн кыйын болбойт, анткени сиз бүт сүрөттү көрө аласыз жана бийиктиги боюнча сорттоо ийгorктүү бүтүшү үчүн кайсы баатырды кайда жылдыруу керектигин дароо аныктай аласыз. Сиз бул маалымат түзүмүн өсүү тартибинде иреттөө үчүн Халк менен Темир Адамдын ордун алмаштыруу жетиштүү деп ойлогон чыгарсыз:

Бүттү!

Жана бул сорттоо ийгorктүү аяктайт. Бирок, компьютер, сизден айырмаланып, бир аз акылсыз жана бүт маалымат структурасын бир бүтүн катары көрбөйт. Анын башкаруу программасы бир эле учурда эки маанини салыштыра алат. Бул маселени чечүү үчүн ал эс тутумуна эки санды жайгаштырып, аларга салыштыруу операциясын жасашы керек, андан кийин бардык маалыматтар талданганга чейин башка жуп санга өтүшү керек. Демек, ар кандай сорттоо алгоритмин үч кадам түрүндө абдан жөнөкөйлөштүрсө болот:

• эки элементти салыштыруу;
• Алардын бирин алмаштырыңыз же көчүрүңүз;
• Кийинки элементке өтүү;

Ар кандай алгоритмдер бул операцияларды ар кандай жолдор менен аткарышы мүмкүн, бирок биз көбүктүү сорттоо кантип иштээрин карап чыгабыз.

Bubble сорттоо алгоритми

Көбүктү сорттоо эң жөнөкөй болуп эсептелет, бирок бул алгоритмди сүрөттөөдөн мурун, эгер сиз машина сыяктуу бир убакыттын ичинде эки гана баатырды бири-бири менен салыштыра алсаңыз, Өч алуучуларды бийиктиги боюнча кантип сорттоор элеңизди элестетип көрөлү. Кыязы, сиз төмөнкүлөрдү кылмаксыз (эң оптималдуу):

• Сиз массивибиздин нөл элементине жыласыз (Black Widow);
• Нөл элементти (Black Widow) биринчиси (Халк) менен салыштырыңыз;
• Эгерде нөлдүн позициясындагы элемент жогорураак болсо, сиз аларды алмаштырасыз;
• Болбосо, нөл позициясындагы элемент кичирээк болсо, аларды өз ордунда калтырасыз;
• Оң тарапка жылып, салыштырууну кайталаңыз (Халкты капитан менен салыштырыңыз)

Мындай алгоритм менен бир өтүү менен бүт тизмени карап чыккандан кийин, сорттоо толук бүтпөйт. Бирок, экинчи жагынан, тизмедеги эң чоң элемент эң оң жагына жылдырылат. Бул дайыма болот, анткени сиз эң чоң элементти тапканыңыз менен, сиз аны аягына чейин жылдырмайынча орундарды тынымсыз алмаштыра бересиз. Башкача айтканда, программа массивден Халкты "тапканда" аны тизменин эң аягына чейин жылдырат: Мына ушундан улам бул алгоритм көбүктүү сорттоо деп аталат, анткени анын иштешинин натыйжасында тизмедеги эң чоң элемент массивдин эң башында болот, ал эми бардык майда элементтер бир позиция солго жылдырылат: Сорттоону аяктоо үчүн массивдин башына кайтып келип, жогоруда сүрөттөлгөн беш кадамды кайталап, кайра солдон оңго жылдырып, керектүү элементтерди салыштырып, жылдыруу керек. Бирок бул жолу алгоритмди массивдин аягына бир элемент калганда токтотуу керек, анткени биз эң чоң элементтин (Hulk) эң оң абалда экенин билебиз: Ошентип, программада эки цикл болушу керек. Көбүрөөк түшүнүктүү болуу үчүн, программанын codeун карап чыгууга өтүүдөн мурун, бул шилтемени колдонуп, көбүкчө сорттоо кантип иштээрин көрүүгө болот: Көбүктү сорттоо кантип иштээрин визуализациялоо

Java тorнде көбүктүү сортту ишке ашыруу

Javaда сорттоо кантип иштээрин көрсөтүү үчүн бул жерде программанын codeу:

• 5 элементтен турган массивди түзөт;
• ага өч алуучулардын өсүшүн жүктөйт;
• массивдин мазмунун көрсөтөт;
• көбүктүү сортту ишке ашырат;
• сорттолгон массивди кайра көрсөтөт.

Сиз төмөндөгү codeду көрүп, жада калса аны сүйүктүү IntelliJ IDE-ге жүктөп алсаңыз болот. Ал төмөндө талдоого алынат:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

Коддогу деталдуу комментарийлерге карабастан, биз программада берилген кээ бир ыкмалардын сыпаттамасын беребиз. Программада негизги иштерди аткарган негизги методдор ArrayBubble классында жазылган. Класста конструктор жана бир нече ыкмалар бар:

• into– массивге элементтерди киргизүү ыкмасы;
• printer– сап боюнча массивдин мазмунун көрсөтөт;

• toSwap– зарыл болсо элементтерди кайра иретке келтирет. Бул үчүн убактылуу өзгөрмө колдонулат dummy, ага биринчи сандын мааниси жазылат, ал эми биринчи сандын ордуна экинчи сандын мааниси жазылат. Убактылуу өзгөрмөнүн мазмуну андан кийин экинчи санга жазылат. Бул эки элементти алмаштыруунун стандарттуу ыкмасы;

  жана акырында негизги ыкмасы:

• bubbleSorter– негизги ишти аткарган жана массивде сакталган маалыматтарды сорттогон, биз аны кайрадан өзүнчө көрсөтөбүз:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

Бул жерде сиз эки эсептегичке көңүл бурушуңуз керек: тышкы outжана ички in. Тышкы эсептегичout массивдин аягынан баштап маанилерди санай баштайт жана ар бир жаңы өтүү менен бара-бара бир азаят. outАр бир жаңы өтүү менен, массивдин оң жагына иргелген маанилерге таасир этпеши үчүн, өзгөрмө солго жылдырылат. Ички эсептегичin массивдин башынан баштап маанилерди санай баштайт жана ар бир жаңы өтүүдө бара-бара бир көбөйөт. Көбөйүү inал жеткенге чейин болот out(учурдагы өтүүдө акыркы талданган элемент). Ички цикл inэки чектеш уячаны inжана in+1. Эгерде inандан чоңураак сан сакталса , анда бул эки сандын ордун алмаштырган in+1ыкма деп аталат .toSwap

Корутунду

Көбүктү сорттоо алгоритми эң жай алгоритмдердин бири. Эгерде массив N элементтерден турса, анда биринчи өтүүдө N-1, экинчисинде N-2, андан кийин N-3 ж.б.у.с. Башкача айтканда, өтүүлөрдүн жалпы саны аткарылат: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Ошентип, сорттоодо, алгоритм болжол менен 0,5x(N ^2) салыштырууларды аткарат. N = 5 үчүн салыштыруулардын саны болжол менен 10 болот, N = 10 үчүн салыштыруулардын саны 45ке чейин көбөйөт. Ошентип, элементтердин саны көбөйгөн сайын, сорттоо татаалдыгы кыйла жогорулайт: Алгоритмдин ылдамдыгына өтүүлөрдүн саны гана эмес, ошондой эле жасалышы керек болгон алмаштыруулардын саны да таасир этет. Кокус берorштер үчүн алмаштыруулардын саны орточо (N^2)/4, бул өтүүлөрдүн санынын жарымына жакын. Бирок, эң начар учурда, алмаштыруулардын саны да N ^ 2 / 2 болушу мүмкүн - бул маалыматтар алгач тескери тартипте иреттелген болсо. Бул бир кыйла жай сорттоо алгоритми экендигине карабастан, анын кантип иштээрин билүү жана түшүнүү абдан маанилүү жана мурда айтылгандай, ал татаал алгоритмдер үчүн негиз болуп саналат. Jgd!