Форум программистов, компьютерный форум CyberForum.ru

Сортировка. Счетчики - C++

Восстановить пароль Регистрация
 
boycott
0 / 0 / 0
Регистрация: 14.11.2012
Сообщений: 5
01.04.2013, 18:15     Сортировка. Счетчики #1
Всем привет, достаточно долго сижу на этом сайте, вот в первые решил попросить помощи, надеюсь на вас!
Вообщем задание было следующее: Отсортировать каждый столбик двумерной матрицы по возрастанию различными способами и вывести на экран количество сравнений и перестановок в каждой сортировке. Собственно программу то я написал, а вот со счетчиками уже около месяца разобраться до конца не могу.
Пузырек

Здесь вроде бы все правильно, но я не уверен
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void bubble_sort()
{
    int bss=0, bsp=0, p, pokaz;         // bss - Bubble Sort Sravneniya bsp - Bubble Sort Perestanovki
    int xx=x, yy=y;
    for (int b = 0; b < xx; b++)
    {
        pokaz=-1;
        do
        {
            p=0;
            for (int a = 0; a < yy-1 ; a++)
            {
                bss++;
                if (mas1[a+1][b] < mas1[a][b])
                {
                    tmp = mas1[a][b];
                    mas1[a][b]=mas1[a+1][b];
                    mas1[a+1][b]=tmp;
                    bsp++;
                    p++;
                }
            }
            pokaz++;
        } while (p!=0);
        if (pokaz!=0)
        {bss--;}
    }

Сортировка выбором
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void selection_sort()
{
    int sss=0, ssp=0;       // sss - Selection Sort Sravneniya ssp - Selection Sort Perestanovki
    for (int j = 0; j < x; j++)
    { 
        for (int i=0; i <= y-1; i++)
        {
            
            int pos = i; 
            int tmp = mas1[i][j];
            for (int m=i+1; m < y; m++)
            { 
                sss++;
                if (mas1[m][j] < mas1[pos][j]) 
                {
                    pos = m;
                    ssp++;
                }
            }
            mas1[i][j] = mas1[pos][j]; 
            mas1[pos][j] = tmp;
            //ssp++;
        }
    }

Сортировка вставками
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void insert_sort()
{
    int iss=0, isp=0;           // iss - Insert Sort Sravneniya isp - Insert Sort Perestanovki
    int n;
    for (int j = 0; j < x; j++)
    { 
        for (int i = 1; i < y; i++)
        {
            iss++;
            int tmp = mas1[i][j]; 
            for (n = i-1; n >= 0 && mas1[n][j] > tmp; n--) 
            {
                mas1[n + 1][j] = mas1[n][j];
                iss++;
            }
            
            mas1[n + 1][j] = tmp;  
            isp++;
 
        }
    }

Сортировка Шелла
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void shell_sort() 
{
    long inc, i, j, seq[40];
    int s;
    int shss=0, shsp=0;     // shss - SHell Sort Sravneniya, shsp - SHell Sort Perestanovki
 
    s = increment(seq, y); // вычисление последовательности приращений
    while (s >= 0)  // сортировка вставками с инкрементами inc[] 
    {
         inc = seq[s--];
         for (j = 0; j < x; j++)
         {
            shss++;
            for (i = inc; i < y; i++) 
            {
                int tmp = mas1[i][j];
                shss++;
                for (int k = i-inc; (k >= 0) && (mas1[k][j] > tmp); k -= inc)
                {
                    mas1[k + inc][j] = mas1[k][j];
                    mas1[k][j] = tmp;
                    shsp++;
                }
            }
         }
    }

Быстрая сортировка
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int QSORT(int first, int last, int i) 
{
    int f=first, l=last;
    int qss=0, qsp=0;                         // qss - Quick Sort Sravneniya qsp - Quick Sort Perestanovki
        
        do
        {   
            int mid = mas1[(first+last)/2][i];
            while (mas1[f][i] < mid)
            f++;
            while (mas1[l][i] > mid)
            l--;
            qss++;
            if (f <= l)
            {
                qsp++;
                int tmp = mas1[f][i];
                mas1[f][i] = mas1[l][i];
                mas1[l][i] = tmp;
                f++;
                l--;
            }
 
            if (first < l)
            {QSORT(first,l,i);}
            if (f < last)
            {QSORT(f,last,i);}
        } while (f <= l);
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2013, 18:15     Сортировка. Счетчики
Посмотрите здесь:

Сортировка C++
Не знаю как настроить счетчики for... C++
Счетчики C++
C++ Сортировка
C++ Сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
01.04.2013, 18:22     Сортировка. Счетчики #2
А какая проблема с счетчиками? Это ж элементарно.
Сейчас сижу пишу аналогичную контрольную, вот мой пузырек с счетчиками
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename T>
sort_result Vector<T>::bubbleSort ()
{
    long cmp_counter = 0, swap_counter = 0;
 
    for (int i = 0; i <= _size - 2; i++) {
        for (int j = _size - 1; j >= i + 1; j--) {
            ++cmp_counter;
            if (_array[j - 1] > _array[j]) {
                ++swap_counter;
                std::swap (_array[j - 1], _array[j]);
            }
        }
    }
 
    return sort_result (cmp_counter, swap_counter);
}
где sort_result это
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class sort_result
{
public:
    sort_result (long cmp, long swp) : result (std::make_pair(cmp, swp)) {}
 
    long comparisons ()
    {
        return result.first;
    }
 
    long swaps ()
    {
        return result.second;
    }
 
private:
    std::pair<long, long> result;
};
в остальные сортировки по аналогии добавишь.
boycott
0 / 0 / 0
Регистрация: 14.11.2012
Сообщений: 5
01.04.2013, 18:25  [ТС]     Сортировка. Счетчики #3
В том то и дело, что по аналогии не получается, где-то да выходит криво, и понять почему не в моих силах.
Может алгоритм не до конца правильно работает, или я вручную считаю не правильно
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
01.04.2013, 18:42     Сортировка. Счетчики #4
Цитата Сообщение от boycott Посмотреть сообщение
В том то и дело, что по аналогии не получается
Всмысле не получается? Я так понял имеются ввиду счетчики сравнений и обменов. Там где происходит сравнение - увиличиваешь счетчик сравнений, там где обмен элементов - счетчик обменов.
boycott
0 / 0 / 0
Регистрация: 14.11.2012
Сообщений: 5
01.04.2013, 18:53  [ТС]     Сортировка. Счетчики #5
Ну так и сделано было. Считают неправильно, где-то больше чем надо, где-то меньше. С одной стороны нелогично, ибо это же машина, и она не ошибается, с другой стороны возможно, что есть изъяны в коде.
Yandex
Объявления
01.04.2013, 18:53     Сортировка. Счетчики
Ответ Создать тему
Опции темы

Текущее время: 15:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru