Форум программистов CodeGuru
17 Январь 2018, 22:11:43 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.

Войти
Новости:
 
   Начало   Помощь Войти Регистрация  
Страниц: [1]   Вниз
  Печать  
Автор Тема: Различие между stable_sort() и sort() в STL  (Прочитано 2701 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Everest
Интересующийся
**
Офлайн Офлайн

Сообщений: 28


Просмотр профиля
« : 20 Март 2010, 20:27:05 »

Здравствуйте, хочу задать следующий вопрос:
Итак, отличие stable_sort() от sort() в STL заключается в том, что stable_sort() сохраняет относительный порядок следования равных элементов.
Теперь следующее:
1) http://www2.sscc.ru/Links/Litera/docs/online/stdlibcr/sta_5767.htm
Здесь утверждается, что следующая программа очень хорошо показывает эту разницу:
Код:
//
// sort.cpp
//
 #include <vector>
 #include <algorithm>
 #include <functional>
 #include <iostream.h>
 struct associate
 {
   int num;
   char chr;
   associate(int n, char c) : num(n), chr(c){};
   associate() : num(0), chr('\0'){};
 };
 bool operator<(const associate &x, const associate &y)
 {
   return x.num < y.num;
 }
 ostream& operator<<(ostream &s, const associate &x)
 {
   return s << "<" << x.num << ";" << x.chr << ">";
 }
 int main ()
 {
   vector<associate>::iterator i, j, k;
   associate arr[20] =
        {associate(-4, ' '), associate(16, ' '),
         associate(17, ' '), associate(-3, 's'),
         associate(14, ' '), associate(-6, ' '),
         associate(-1, ' '), associate(-3, 't'),
         associate(23, ' '), associate(-3, 'a'),
         associate(-2, ' '), associate(-7, ' '),
         associate(-3, 'b'), associate(-8, ' '),
         associate(11, ' '), associate(-3, 'l'),
         associate(15, ' '), associate(-5, ' '),
         associate(-3, 'e'), associate(15, ' ')};
   // Set up vectors
   vector<associate> v(arr, arr+20), v1((size_t)20),
                 v2((size_t)20);
   // Copy original vector to vectors #1 and #2
   copy(v.begin(), v.end(), v1.begin());
   copy(v.begin(), v.end(), v2.begin());
   // Sort vector #1
   sort(v1.begin(), v1.end());
   // Stable sort vector #2
   stable_sort(v2.begin(), v2.end());
   // Display the results
   cout << "Original    sort      stable_sort" << endl;
   for(i = v.begin(), j = v1.begin(), k = v2.begin();
       i != v.end(); i++, j++, k++)
   cout << *i << "     " << *j << "     " << *k << endl;
   return 0;
 }
Output :
Original    sort      stable_sort
<-4; >     <-8; >     <-8; >
<16; >     <-7; >     <-7; >
<17; >     <-6; >     <-6; >
<-3;s>     <-5; >     <-5; >
<14; >     <-4; >     <-4; >
<-6; >     <-3;e>     <-3;s>
<-1; >     <-3;s>     <-3;t>
<-3;t>     <-3;l>     <-3;a>
<23; >     <-3;t>     <-3;b>
<-3;a>     <-3;b>     <-3;l>
<-2; >     <-3;a>     <-3;e>
<-7; >     <-2; >     <-2; >
<-3;b>     <-1; >     <-1; >
<-8; >     <11; >     <11; >
<11; >     <14; >     <14; >
<-3;l>     <15; >     <15; >
<15; >     <15; >     <15; >
<-5; >     <16; >     <16; >
<-3;e>     <17; >     <17; >
<15; >     <23; >     <23; >
Но я запускаю данную программу на своем Visual C++ 9.0 Express Edition, а выдает он одно и тоже при stable_sort() и sort().

2) http://www.cgui.ru/stl129.htm
Здесь тоже приводится такая программа:
Код:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct rectype

{ string s; int num;

bool operator<(const rectype &b)const

{ return s < b.s;

} };

int mainO

{ const int N = 20; string t[20] =

{"Judy", "John", "John", "Judy", "John", "Judy", "Paul", "Judy", "Paul", "Mary", "Mary", "John", "Judy", "Paul", "John", "Paul", "Judy", "John", "Judy", "Judy"}; int k;

rectype a[N]; for (k=0; k<N; k++) { a[k].s = t[k]; a[k].num = 10 + k; }

sort(a, a+N); for (k=0; k<N; k++) { cout<<a[k].s<<" "<<a[k].num<<(k % 5 == 4 ? "\n" : "  "); }

return 0; }

Утверждается, что программа создает следующий вывод:

John 11     John 12     John 14        John 27    John   24

John 21     Judy 29     Judy 28        Judy 26    Judy   22

Judy 17     Judy 15     Judy 13        Judy 10    Mary  20

Mary  19   Paul  18     Paul  23        Paul 25    Paul   16

Заменим вызов алгоритма sort на stable_sort(a, a+N) ;
После этой модификации программа напечатает:

John  11      John 12      John 14      John 21    John 24

John 27       Judy 10      Judy 13      Judy 15    Judy  17

Judy  22      Judy 26     Judy 28     Judy 29    Mary  19

Mary  20      Paul 16      Paul 18      Paul 23    Paul  25

Но ничего подобного, опять все одинаково.


Поэтомы вопрос: Как все-таки наглядно можно показать разницу между двумя данными алгоритмами сортировки? Очень прошу помогите мне Улыбка
Записан
holdmann
Пользователь
***
Офлайн Офлайн

Сообщений: 262



Просмотр профиля
« Ответ #1 : 21 Март 2010, 02:30:39 »

Ну насколько я помню, различие между алгоритмами сортировок выявляются на больших громадных массивах данных. И вообще-то заключается во времени, необходимом на обработку (сортировку) самого массива.
Записан

Елси вы хотите купить, продать, отремонтировать автомобиль в Ижевске: Вам сюда =)
(c)holdmann
Everest
Интересующийся
**
Офлайн Офлайн

Сообщений: 28


Просмотр профиля
« Ответ #2 : 21 Март 2010, 07:13:06 »

holdmann, понимаете в том то и дело - задание показать различие, написав какую-нибдь программу Улыбка
И оно должно заключаться в том, что stable_sort() сохраняет относительный порядок следования равных элементов, а sort() - нет. А вот как это показать у меня не получается Грустный
Записан
Everest
Интересующийся
**
Офлайн Офлайн

Сообщений: 28


Просмотр профиля
« Ответ #3 : 21 Март 2010, 08:14:33 »

Вопрос снят - я его решил Улыбка
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!