Въпросче на начинаещ

Най-малкото искам да ви досаждам с тъпи аматьорски въпросчета, ама сега ми е наложително. Просто имам малък проблем в училище с Pascal. Дадоха ни при въведени три числа да бъдат подредени по големина - хубаво (и лесно), дадоха ни и с четири и с повече, ама като ми казаха девет и на мен вече ми омръзна, защото единствения начин да го направя със досегашните си знания е да сравнявам поотделно числата докато установя как да бъдат наредени и си викам, че не може да няма по-лесен начин. Попринцип го чаткам езика и то повечко отколкото ни учат, ама за това не знам дали има друг начин та затова прибегнах до този клуб.
Ако някой може да ме светне става ли по друг начин и как точно? Благодаря предварително!

Ето ти едно елементарно решение:

Направи си един масив с фиксирана големина примерно 500-600. Обяви си една променлива която е броят на числата които трябва да се въведат и сортират. Първо искай от потребителя да въведе броя на числата (за да инициализираш променливата), после да въведе самите числа. Така програмата ти става универсална. След това сортираш по един от стандартните методи - мехурчето е най-лесно.

После можеш да дадеш на даскалката си да тества с 600 числа примерно.

Мечтата е мисъл, мисълта е идея, всяка идея се реализира. Аз не мечтая, а реализирам идеите си.

значи щом сравнява на ръка, значи за мехурче не е чувал.
и така, идеята не мехурчето е да се сравняват последователно всички съседни елементи в масива, и ако не са наредени вярно да се сменят. аз ползвам лека модификация при която се сравняват не съседни елементи, а текущия с първия ненареден. така при първия пас намираш най-малкия(големия) и той отива в началото, на втория пас намираш следващия най-голям и той отива на втора позиция и т.н.т.

for i:=1 to n-1
for j:=i+1 to n
if a>a[j] then
begin
h=a;
a=a[j];
a[j]=h;
end

be az paskal ne znam ama niama li niakoia funkciika deto da ti narezda masiva po niakoi ot zelanite ot teb na4ini ?
az li4no ne bih polzval metoda na mehur4etata (sega) a bih izsipal 4islata v edna baza danni ako niamam array_sort i 6te si gi drapna posle order by value asc :-)

E tuk ni6to niama :[линк]

А може ли малко по подробно да го кажете така като за дебил като мене. Схванах основната идея, ама не съм много сигурен, че знам как точно да го направя. Също не ми стана много ясно как става това (не се смейте моля) първо да бъде въведен броя на числата и после самите числа.
Пак Ви благодаря много за бързия отговор!

A moje i predi tova da hacknesh amerikanskata stancija deto ja pratiha v oribita na Mars - tam sigurno sha ima njakoja baza danni, deto shta ti gi sortira

Mi to signala stiga dotam za ima-njama 20 minuti ... i obratno oshte tolkoz - za okolo 1 chas shte si sortiral 3 chisla ... :)))

bubble sort e naj-prost i e naj-efektiven za masivi do 500 elementa ...
veche pri po-golemi e razumno da se izpolzva tejkata artilerija (quick sort, heap sort i t.n.)

[линк]
Search: "sorting algorithms"

След това четеш и си избираш най-подходящото решение. За начало ти препоръчвам да обърнеш внимание на простите алгоритми - bubble sort (метод на мехурчето), selection sort (метод на пряката селекция), insertion sort (метод на вмъкването).

bubble sort e naj-prost i e naj-efektiven za masivi do 500 elementa ...
veche pri po-golemi e razumno da se izpolzva tejkata artilerija (quick sort, heap sort i t.n.)


aha, ne biah chuwal che 500^2 e po-dobre ot 500*log(500)

Ето ти едно решение. Не е идеално,
но ще видиш идеята.

program Sort;
var
masiv:array[1..100] of integer;
Broj,i,razmeni:integer;
FlagImaLiSort:boolean;

begin
Write('Broj:');Readln(Broj);

for i:=1 to Broj do
begin
Write('Input ',i,' number ');Readln(masiv[ i ]);
end;

FlagImaLiSort:=true;
while FlagImaLiSort do
begin
FlagImaLiSort:=false;
for i:=1 to Broj-1 do
if masiv [ i ] > masiv [ i+1 ] then
begin
razmeni:=masiv[ i ];
masiv[ i ]:=masiv[ i+1 ];
masiv[ i+1 ]:=razmeni;
FlagImaLiSort:=true;
end;
end;

for i:=1 to Broj do Writeln(masiv [ i ] );

end.

Първо една забележка: като постваш код го слагай в таг 'пре', щото иначе става боза. Освен това за всеки случай не ползвай i, щото тоя таг не работи добре нещо. На времето работеше.
Второ това дето си го написал не е 'мехурче', а 'пряка селекция' - най-лесният и естествен алгоритъм за сортиране. Мехурчето просто има много атрактивно име, затова е популярно.

for ii:=1 to n-1 

  for j:=i+1 to n 

    if a[ii]>a[j] then 

    begin 

      h=a[ii]; 

      a[ii]=a[j]; 

      a[j]=h; 

    end

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Мерси (за тага) ще знам за в бъдеще.
А метода за сортиране, който и да е той почти
няма значение в случая. Просто на човека
му трябва нещо работещо каквото и да е.
Тъй като не знае, по-важното е да получи представа.
В този момент едва ли му трябват "учени" теории
за това колко метода за сортиране има.

Всъщност това което му трябва е да си седне на задника и да си потърси сам!

Не, 500 са твърде много. В крайна сметка, всеки алгоритъм си има приложение, в зависимост от случая. Методът на мехурчето е подходящ, когато масивите са почти сортирани, и само някои елементи не са си на мястото. Тогава е и особено подходящо да се използва модификацията, в която веднъж се върви към края на масива, после към началото, после пак към края и т.н. Това е известно още като "сортиране с клатене".

За по-голям брой вече идват на помощ бързото сортиране на Хоор (още известно като QuickSort) и MergeSort, макар че последния има недостатъкът, че за сливането изисква малко повече памет (евентуално и процесорно време).

Ако пък обхватът на числата, които сортираш, е ограничен (например, имаш да сортираш 500000 числа, но всяко от тях има стойност от 1 до 50), най-подходящо е сортирането чрез броене - на един пас преброяваш всяко от тези числа колко пъти се среща, след което тръгваш по масива, в който помнищ бройките на числата, и записваш в оригиналния масив всяко число толкова пъти, колкото се среща. Както може лесно да се види, този алгоритъм има линейна сложност, но не е приложим винаги.

И въобще, алгоритмите за сортировка трябва да се познават, и да се избира най-подходящия за случая. Може да се ползва и комбинация от тях - например QuickSort, който обаче, когато останат под 10 елемента, започва с пряка селекция. Аз лично съм свидетел как Петър Митров, първенец по ученическите олимпиади по информатика преди години, за едно състезание си беше направил performance тестове - пряка селекция е по-бърза под еди колко си елемента, от толкова до толкова - този алгоритъм, от толкова до толкова - онзи алгоритъм, и използваше най-подходящия метод, в зависимост от броя на елементите, които му се налага да сортира. Естествено, неговата програма беше най-бързата

използването на имена на променливи и низове на роден език е меко казано смехотворно.

английския все пак е lingua franca! така си ограничаваш кода до разчитаем само от българи и то не много българи

ein heller Schein am Firmament

da be ama ako te marzi da pi6e6 kod pravi6 tva deto ima nai malko pisane i raboti barzo i efektivno (gore dolu) :-)))

E tuk ni6to niama :[линк]

английския все пак е lingua franca! така си ограничаваш кода до разчитаем само от българи и то не много българи

ein heller Schein am Firmament

----

a kato si pishesh deviza na nemski go pravish razchitaem samo za nemci taka li?

За Meндeлeeв.

Напълно съм съгласен за имената на променливите.
Но в случая съзнателно са на "български". Все пак
това беше пример и то за ученик. (ами ако не
знае английски?).

Между другото той така и не каза дали
си е свършил работата.

и аз ползвам имена на български понякога:))))
и това че чужденци няма да могат да ми четат кода не ме вълнува, даже е добре.

>> И въобще, алгоритмите за сортировка трябва да се познават, и да се избира най-подходящия за случая.

Размерът на масива обаче не е едиствения фактор, който трябва да се отчете при избора на алгоритъм за сортиране. Мисля че важат и следните неща:

1. "Бързите" алгоритми са по-сложни за имплементация - отнемат повече време, а както е всеизвестно не всеки е като "истинския програмист" - правят се грешки (било заради неумение или заради препиване предишната вечер :))).

2. В общия случай "бързите" алгоритми гълтат повече памет (за мехурчето или пряка селекция ти трябват 2 брояча и един буфер за размените, за quick sort трябва стек - дали ще е програмния или твой - все тая). Знам че на състезанията по информатика се отчита скорост, а не консумирана памет, но в реалния свят положението е друго.

3. Един час програмистко време е МНОГО по-скъп от един час машинно време, т.е. понякога (и то доста често) си заслужава да изберем нещо просто и бавно, но бързо за имплементация, отколкото нещо сложно и бързо, но да загубим много време да го пишем и дебъгваме.

4. Трябва да се отчита колко често сортираме. Ако да кажем програмата ти веднъж на всеки 20 секудни трябва да сортира един масив от 500 елемента, то мехурчето си е точно на място (сортирането отнема 20 ms на PIII 733 - 0,1% от общото време и то теста го писах на Java :)).

Правилно. Никъде не съм казал, че изборът трябва да става само по скоростта на алгоритъма

Иначе за стека при бързото сортиране - смятам, че двоичен логаритъм от дължината на масива е твърде малко число... Ако трябва да се сортират байтовете на 4 гигабайтов масив, ти трябва стек с 32 елемента... Сигурно ще се съгласиш, че не са толкова много, а и QuickSort сам по себе си е достатъчно прост и лесен за имплементиране.