Техники во програмирање сортирање: сортирање "меур"

меур вид не се гледа само да биде најбрзо метод, згора на тоа, го затвора листата на најбавната начини да се организира. Сепак, тоа има свои предности. Така, начинот на сортирање меур - повеќето дека ниту е природно и логично решение за проблемот, ако сакате да се организираме на предмети во одредена цел. Обичен човек рачно, на пример, ќе ги користи - само со интуиција.

Од каде таква необична име?

Метод за името излезе, со користење на аналогија на воздушни меурчиња во водата. Тоа е метафора. Само малку, воздушни меури се зголеми нагорен - поради нивната густина е поголема од течност (во овој случај - вода), и секој елемент од низата, толку е помал, тоа е вредноста, толку повеќе постепено пат кон врвот на броеви на листата.

Опис на алгоритмот

меур вид се врши на следниов начин:

• Првиот помине: елементи на броеви во низата е донесена од страна на два пара, а исто така се споредуваат. Ако некои елементи на две-човек тим првата вредност е поголема од вториот, на програмата ги прави размена места;
• Како резултат на тоа, најголем број на промаши крајот на низата. Додека сите други елементи остануваат како што беа, во хаотичен начин, и бараат повеќе сортирање;
• и затоа бараат втор пат: тоа е направено по аналогија со претходната (веќе е опишано) и има голем број на споредби - минус еден;
• на премин број три споредби, еден помалку од секунда, и двете, од првата. И така натаму;
• резимираме дека секој премин има (сите вредности во низата, одреден број) минус (премин број) споредби.

Дури и пократко алгоритам на програмата може да се запише како:

• низа од броеви се проверува додека се најде било два броја, вториот од нив е обврзана да биде поголема од првата;
• неправилно поставени во однос на едни со други елементи на софтвер низа размена на.

Pseudocode врз основа на алгоритам е опишано

Наједноставна имплементација се врши на следниов начин:

Sortirovka_Puzirkom постапка;

почеток

циклус за J од nachalnii_index да konechii_index;

циклус за I од nachalnii_index да konechii_index-1;

ако massiv [i]> massiv [i + 1] (првиот елемент е поголема од една секунда), тогаш:

(Промена става вредности);

крајот

Се разбира, оваа едноставност само ја влошува ситуацијата: поедноставно алгоритам, повеќе се манифестира сите недостатоци. сооднос инвестиција на време е премногу голем, дури и за мала низа (тука доаѓа во релативноста: Износот на време за лаик може да изгледа мал, но всушност програмер секој втор или дури милисекунда точки).

Таа зеде подобро спроведување. На пример, водејќи сметка за размена на вредности во низата локации:

Sortirovka_Puzirkom постапка;

почеток

sortirovka = true;

циклус до sortirovka = true;

sortirovka = false;

циклус за I од nachalnii_index да konechii_index-1;

ако massiv [i]> massiv [i + 1] (првиот елемент е поголема од една секунда), тогаш:

(Промена елементи места);

sortirovka = true; (Се познава дека размената е направена).

Крај.

ограничувања

Главниот недостаток - времетраењето на процесот. Колку време се врши сортирање алгоритам меур?

Доведе време се пресметува бројот на квадратни броеви во низа - крајниот резултат на тоа е пропорционален.

Ако најлош случај во низата е донесен онолку пати колку што има елементи минус една вредност. Ова се случува затоа што на крајот таму е само еден елемент, кои немаат ништо да се спореди, а последниот помине низ низа станува бескорисна акција.

Покрај тоа, ефикасен метод на сортирање едноставна размена, како што се нарекува, само за низи на мала големина. Големи количини на податоци со помош на процесот нема да работи: резултатот ќе биде или грешка или неуспехот на програмата.

достоинство

меур вид е многу лесно да се разбере. Студиските програми на технички универзитети во студијата на нарачување елементи на својата низа помине во на прво место. Методот е лесно да се спроведе и во Делфи програмски јазик (L (Делфи) и C / C ++ (C / C плус плус), неверојатно едноставен вредности на локација алгоритам во вистинската цел и на Паскал (Pascal). Меур вид е идеален за почетници.

Поради недостатоците на алгоритам не се користи во воннаставните цели.

принципот визуелни сортирање

На почетна поглед на низата 8 22 4 74 44 37 1 7

Чекор 1 4 8 22 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

1 4 8 22 74 44 37 7

8 1 22 4 74 44 37 7

1 4 8 22 74 44 37 7

Чекор 2: 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Чекор 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Чекор 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Чекор 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Чекор 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Чекор 7 1 4 7 8 22 37 44 74

меур вид пример во Pascal

На пример:

const kol_mas = 10;

var massiv: низа [1..kol_mas] на цел број;

a, b, k: цел број;

започне

writeln ( "влез", kol_mas, "елементи на низата ');

по: = 1 до kol_mas се направи readln (massiv [a ]);

по: = 1 до kol_mas-1 се започне

за б: = a + 1 до kol_mas почнуваат

ако massiv [a]> massiv [ b] потоа почнуваат

k: = massiv [a]; massiv [a]: = massiv [ b]; massiv [b]: = k;

крај;

крај;

крај;

writeln ( "по вид ');

по: = 1 до kol_mas се направи writeln (massiv [a ]);

крај.

ПРИМЕР меур сортирање во јазик C (Ц)

На пример:

# Include

# Include

int главната (int argc, char * avg [])

{

INT massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

за (;;) {

ff = 0;

за (i = 7; i> 0; i -) {

ако (massiv [i] [i- 1]) {

swap (massiv [I], massiv [i- 1]);

ff ++;

}

}

ако (ff == 0) скрши;

}

getch (); // одложување дисплеј

врати 0;

}.