Kasawa dabaru a shirye-shirye: kasawa "kumfa"

kumfa raba ba kawai dauke su ya fi sauri hanyar, haka ma, shi rufe da jerin slowest hanyoyin da za a shirya. Duk da haka, shi yana da abũbuwan amfãni. Saboda haka, hanyar da kasawa da kumfa - mafi cewa ba shi ne mai halitta da kuma ma'ana warware matsalar, idan kana so ka gabatar da abubuwa a cikin wani takamaiman tsari. An talakawa mutum da hannu, misali, shi zai yi amfani da su - kawai ta diraya.

Inda ya yi irin wannan sabon abu da sunan?

Hanyar sunan zo up, ta amfani da misalin iska kumfa a cikin ruwa. Yana da wani misãli. Kamar yadda kadan iska kumfa tashi zuwa gaba - saboda su yawa ne mafi girma daga wani ruwa (a cikin wannan harka - da ruwa), da kuma kowane tsararru kashi, karami shi ne darajar, da mafi sauka a hankali hanya zuwa saman jerin lambobi.

Description na algorithm

kumfa warware aka yi kamar haka:

• farko izinin: da abubuwa na tsararru lambobin da aka dauka da nau'i-nau'i biyu, kuma ma idan aka kwatanta. Idan wasu abubuwa na biyu-mutum tawagar farko darajar ne mafi girma daga biyu, da shirin da ke sa su canza wuraren.
• saboda haka, mafi girma da yawan kuskure ƙarshen tsararru. Duk da yake duk sauran abubuwa kasance kamar yadda suke su ne, a cikin wani m hanya, da kuma bukatar karin kasawa.
• sabili da haka ya bukatar wani biyu izinin: shi ne sanya ta misalin da baya (riga aka bayyana a), kuma yana da yawan kwatancen - debe daya.
• a nassi yawan uku misãlai, daya kasa da na biyu, da kuma biyu, fiye da na farko. Kuma haka a kan;
• takaita da cewa kowane nassi yana da (duk dabi'u a cikin tsararru, musamman yawan) debe (nassi yawan) misãlai.

Ko guntu algorithm na wani shirin za a iya rubuta kamar:

• wani tsararru na lambobin da aka bari dai wani biyu lambobin an samu, na biyu daga cikinsu an daure su kasance mafi girma daga farko.
• kuskure positioned a dangane da juna abubuwa da tsararru software swaps.

Pseudocode dangane da algorithm bayyana

A mafi sauki aiwatar ne da za'ayi kamar haka:

Sortirovka_Puzirkom hanya.

farko

zagayowar for j daga nachalnii_index zuwa konechii_index.

zagayowar ga i daga nachalnii_index zuwa konechii_index-1.

idan massiv [i]> massiv [i + 1] (na farko kashi mafi girma daga wani, na biyu), sa'an nan:

(Canji sanya dabi'u).

karshen

Hakika, wannan sauki kawai aggravates halin da ake ciki: da sauki da algorithm, da more shi bayyana duk flaws. Zuba Jari rabo daga lokaci ne ma mai girma ko da na kananan tsararru (a nan ya zo a dangantakar: The adadin lokaci domin layman iya ze kananan, amma a gaskiya a shirye-shiryen kowane biyu ko daƙiƙa kirga).

Sai da na ɗauki cikin mafi aiwatar. Alal misali, shan la'akari da musayar dabi'u a cikin tsararru wurare:

Sortirovka_Puzirkom hanya.

farko

sortirovka = gaskiya.

zagayowar har sortirovka = gaskiya.

sortirovka = ƙarya.

zagayowar ga i daga nachalnii_index zuwa konechii_index-1.

idan massiv [i]> massiv [i + 1] (na farko kashi mafi girma daga wani, na biyu), sa'an nan:

(Canza abubuwa wuraren).

sortirovka = gaskiya. (Gano cewa musayar an sanya).

Ƙare.

gazawa

Babban hasara - ta tsawon lokaci da tsari. Nawa lokaci aka yi kasawa algorithm kumfa?

Gubar lokaci da aka lasafta daga yawan square lambobi a cikin tsararru - karshen sakamakon shi ne na gwargwado.

Idan mafi munin yanayin da tsararru ne haƙĩƙa, sun shige sau da yawa yadda yana da abubuwa debe daya darajar. Wannan ya faru saboda a karshen akwai daya da rabi, wanda da kome kwatanta, kuma na karshe izinin tafiya a cikin tsararru zama m mataki.

Bugu da kari, inganci Hanyar kasawa mai sauki musayar, kamar yadda shi ne ake kira, kawai don iri-iri na kananan size. Manyan yawa na data da taimakon tsari zai yi aiki ba: sakamakon zai kasance ko dai wani kuskure ko gazawar da shirin.

girma

kumfa raba ne mai sauqi ka fahimta. A amfani da tsarin na fasaha jami'o'i a nazari na ordering abubuwa na ta tsararru wuce a cikin ta farko wuri. A hanya ne sauki don aiwatar da biyu da Delphi shirye-shirye da harshen (L (Delphi), da kuma C / C ++ (C / C da da), wani mai wuce yarda sauki dabi'u na wuri algorithm a dama domin kuma a Pascal (Pascal). Bubble raba shi ne manufa ga sabon shiga.

Saboda da raunin da algorithm ba a yi amfani da extracurricular dalilai.

Kayayyakin kasawa manufa

A farko view of tsararru 8 22 4 74 44 37 1 7

Mataki 1 8 22 4 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

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Mataki 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

Mataki na 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

Mataki na 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

Mataki 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

Mataki 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Mataki 7 1 4 7 8 22 37 44 74

kumfa irin misali a cikin Pascal

misali:

const kol_mas = 10;

var massiv: tsararru [1..kol_mas] na lamba;

a, b, k: lamba;

fara

writeln ( 'shigar', kol_mas, 'abubuwa na tsararru').

ga wani: = 1 zuwa kol_mas yi readln (massiv [a ]).

ga wani: = 1 zuwa kol_mas-1 yi a fara

ga b: = wani + 1 ga kol_mas kada a fara

idan massiv [a]> massiv [ b] sa'an nan za a fara

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

ƙare.

ƙare.

ƙare.

writeln ( 'bayan irin').

ga wani: = 1 zuwa kol_mas yi writeln (massiv [a ]).

karshen.

MISALI kumfa kasawa a cikin C harshe (C)

misali:

#include

#include

int babban (int argc, char * argv [])

{

int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, JJu.

domin (;;) {

JJu = 0.

domin (i = 7; i> 0; i -) {

idan (massiv [i] [i- 1]) {

canza (massiv [i], massiv [i- 1]).

JJu ++.

}

}

idan (JJu == 0) karya.

}

getch (). // nuni da bata lokaci ba

koma 0.

}.