Изпечатай

[suxxx]

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

Така сортираме общото време но как да направя клиентите да се подреждат по азбучен ред   '>  '>
Може ли да ми дадете примерен алгоритъм за сортиране по азбучен ред.
БЛАГОДАРЯ ПРЕДВАРИТЕЛНО!!!!!!

[KeuH]

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

Идеята е следната: имаме масив m от n елемента.
Викаме qsort(m, (int)(n/2)), където (int)(n/2) е така наречения пивот.
qsort:
Ако pivot = 1, върни m,
иначе ако pivot = 2, сравни m[1] и m[2] и ги размени, ако трябва;
иначе извикай less = qsort(m[1..pivot], pivot/2),
greater = qsort(m[pivot+1..n], (pivot+1+n)/2);
обедини m = less със greater.

За конкретен код виж:

http://en.wikipedia.org/wiki/Quicksort#C.2B.2B

За да сравняваш стрингове от полза може да ти е функцията:

$man 3 strcmp

Тъй като не съм специалист по c++, може в c++ да има друга функция за сравнява на низове.  Тази е от c, но би трябвало да работи и в c++.  Специалистите по c++ да се изкажат!

може би `man sort` и неговия изходен код ще ти бъдат от полза

[suxxx]

Този т.н пивот функция на с++ ли е '>
Не може ли да се използват фунцийте за работа със низове и по точно strchr,но как да немерим коя е първа буква и коя втора.
Аз лично сортирам със т.н метод на мехурчето:
ето тук се помъчих на направя програма в която се въвеждат 5 имена и след това излизат по азбучен ред но нещо съм объркал:

Примерен код

#include <iostream> #include <string> using namespace std; struct sorts {  char name[60]; }; sorts b[5]; void sort(int m) int main () { for (int i=0;i<=5;i++) { cout << "enter five names" << endl; cin.getline(b[i].name,60); } sort(i); return (0) } void sort(int m) { for (int i=0;i<=m-2;i++) for (int k<=i+1;k<=m-1;k++) { if (strcmp(b[i].name,b[k].name) == 0) { string *beg = &b[i].name; string *end = &b[k].name; } } sort(beg,end);  for (int i=0;i<=5;i++) {  cout << b[i].name << endl; }

Нещо не мога да разбера за този пивот дето викаш,но ще продължавам да се мъча.БЛАГОДАРЯ ти все пак за усилието,аиде със здраве!!!!

[KeuH]

Ок, явно ще трябва да обясня по-подробно!

Първо.  Сортирането на n е елемента е математичестки, а не програмистки проблем и за него има разбработени томове и томове от литература.  За справка има една монография от Доналд Кнут - "Изкуството на програмирането", но не я препоръчвам на начинаещ като тебе.  Аз съм се учил по много книги, но една добра уводна книга е "Algorithms and Data Structures" от Michael Goodrich и Roberto Tamassia, но нямам представа, дали я има на българския пазар.  Със сигурност, обаче на българския пазар има книга, която ще те въведе в сортирането - питай някой студент по информатика и ще ти препоръча нещо.

Методът на мехурчето, който използваш е най-неподходящия от всички възможни методи, защото при всичи случаи ще направи около n^2 операции - в това число сравнения и премествания.  На математически жаргон се казва, че сложността му е O(n^2).  Погледни в някоя книга за дефиниця, какво значи функция f да принадлежа на клас от сложност O(P(n)), където P(n) е полином по n.  Методът, който аз ти предлагам - quicksort се счита за най-бързия метод, тъй като неговата средна сложност е O (n*log(n)).  Няма значения конкретния програмен език, на който се пише.  По принцип матетическта дефиниция, тази която съм ти дал по-горе е рекурсивна и буквалното й имплементиране би отнело много памет, но с малко въображение може да се напише итеративно и всичко да е тип-топ.  С други думи - забрави за метода на мехурчето по следната причина.  Ако имаш масив с да кажем 1 500 000 човека (телефонният указател на София), за сортирането му по метода на мехурчето ще ти трябват около 2250000000000 операции, ако всяка ти отнеме по една милисекунда (много груба оценка) 2250000000 секунди, което в часове е 62500.  Ако изполваш quicksort и телефонният указател не е разбъркан точно отзад напред, ще ти трябват около 21331463.49910866 операции, или около 5 часа.  Виждаш ли разликата, така че забрави за bubble sort и научи някой по-бърз алгоритъм, било то quick-sort, било то merge-sort, било то heap-sort и т.н.  За справка пак те отправям към въпросната книга.  Но сега да се върнем на quicksort и да ти обясня по-добробно.  Няма да влизам в анализ на сложността на алгоритъма, защото може да се покаже, че при нарочно избрани данни и този алгоритъм е бавен, но както ти казах и по-горе една свястна имплементация е бърза и заема малко памет и в средно-статистическият случай е най-доброто възможно.  И между другото, този алгоритъм го има като стандартна функция в c, така че няма нужда дори да го имплементираш.  За справкa:

$ man 3 qsort

Сега отново към алгоритъма.  Ето една друга страница, където има страхотно обяснение и анимация, как работи quicksort:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html

След като проумееш матечески алгоритъма идва втората стъпка.   Как да го приложиш на практика.  Тука се набиват на очи три проблема.  Проблем едно: как да избегнеш рекурсията, проблем две, как да избегнеш допълният разход на памет и проблем три как да сравняваш елементите, които имаш да сравняваш.

Ще започна отзад напред.  За сравняване на символни низове в c++ можеш да използваш функцията strcmp.  Ето какво пише в документацията й.  Не мога да го обясня по-добре от това.

int strcmp(const char *s1, const char *s2);
  The  strcmp()  function compares the two strings s1 and s2.  It returns
       an integer less than, equal to, or greater than zero if  s1  is  found,
       respectively, to be less than, to match, or be greater than s2.

За използване на inplace стратегията, т.е. за да избегнеш разхода на допълнителна памет пусни два итератора по масива и им разменяй местата, сравнявайки ги с пивота.  За по-подробна информация:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort1a.html

А първият въпрос и той не е сложен, но за да го решим, направо да ти го напиша като програмен код.  За това виж wikipedia-та от първият ми постинг - там има страхотен код.  Ако все пак имаш проблеми обаче, пиши пак, ще видя, дали ще намеря малко време да драсна малко код '>

[suxxx]

Много съм ти задължен !!! Ще се опитам да науча този quicksort.Но хората са ми казвали че bubblesort е най-лесен и разбираем за начинаещ като мен.Пък аз съм канидат-студент и на 20-ти съм на изпит на който трябва да напиша някаква програмка и затова си мисля че няма значение колко бавно ще сортира важното алгоритъма да ми е верен но ще науча и това сортиране,защото дето викаш много по-бързо ще търси.
Чао за сега.Поздрави !!!!

[KeuH]

Виж сега порових още малко из едни стари книжки и намерих нещо и на български - автор е Преслав Наков, а книгата се нарича "Въведение в алгоритмните" или нещо такова.  За метода на мехурчето, наистина е най-лесен, но ако е до лесното има и други лесни методи - признавам си, бързото сортиране на Хоор (quicksort) е малко объркващо за начинаещ, но наистина те съветвам да научиш някой по-бърз алгоритъм - има ги доста в почти всеки справочник по програмиране, напр. merge-sort е направо елементарен, стига да знаеш, какво е рекурсия.

[suxxx]

Може ли да те помоля за една последна услуга ??
Намерих един алгоритъм за сортиране по азбучен ред но ми трябва да намира думите който потребителя е въвел.Ще може ли да ми го преобразуваш когато имаш време и ако ти се занимава.Благодаря!!!

Примерен код

#include <iostream> #include <string> using namespace std; int main() {         string a[5] = {"car","bar","cad","sad","add"};         string *beg = &a[0]; //points to beginning of sorting region         string *end = &a[5]; //points after end of sorting region         sort(beg,end);         for (int i = 0; i < 5; i++)                 cout << a[i] << endl;         //outputs alphabetically. }

аз се опитах да го направя това нещо но пак не успях   '> .Пак някаде бъркам  '>  '>

Примерен код

#include <iostream> #include <string> #define max 10 using namespace std; struct sortc {  char name[60]; }; sortc b[max]; int main () {  for (int i=0;i<=max;i++) {   cout << "Name ?" << endl;   cin.getline(b[i].name,60);   }  string *beg = &b[i].name[0];  string *end = &b[i].name[max];    sort(beg,end);  for (int i=0;i<max;i++) {  cout << b[i] << endl;  }    return (0); }

[halturata]

Ми що не кажеш направо какъв е проекта, та да ти го напишеме бе пич?  '>

KeuH, тази книга "Algorithms and Data Structures" има ли я в pdf формат и ако да откъде мога да я дръпна.И нещо подобно ,само че на Java, има ли?