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

Сортировка выбором - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ обясните каждую строку, пожалуйста http://www.cyberforum.ru/cpp-beginners/thread679188.html
Задача про автомобили, в общем все ясно, когда запустите...помогите объяснить (возможно написать комментарии около функции и т.д. надо сдать задачку, срооооочно. Препод требует обяснять каждую строку ((( ! ) #include <iostream.h> #include <conio.h> class Auto {protected: char *c; int a,b;
C++ связанный список Создать связанный список целых чисел. из него организовать два списка, по такому правилу: Первый содержит отрицательное значение данного списка, второй из положительных. http://www.cyberforum.ru/cpp-beginners/thread679186.html
C++ Посчитать количество букв "а" в англоязычный строчке
Есть такой код #include<iostream> #include<conio.h> #include<stdlib.h> #include<locale.h> using namespace std; void inp(); void out(); int n; char* arr; int main() {
операции над матрицами: сложение, вычитание, умножение, и транспонирование матрицы C++
Описать класс, реализующий тип данных "вещественная матрица" и работу с ними. Класс должен реализовывать следующие операции над матрицами: сложение, вычитание, умножение, и транспонирование матрицы.
C++ В одномерном массиве, состоящем из 5 элементов, вычислить среднее арифметическое всех элементов http://www.cyberforum.ru/cpp-beginners/thread679131.html
Написать прототип, определение функции и пример вызова функции для решения указанной далее задачи. исходные данные и результаты работы функции передавать через список параметров, единственный ответ лучше получать как возвращаемое значение. обработку массива вести с использованием указателей. спланировать тестирование функции. для ввода исходных данных, передаваемых в функцию, и печати результатов...
C++ В чем смысл создания шаблона с заранее известным передаваемым типом Видел шаблоны типа: template<int N> struct fact{ static const int v = fact<n-1>::v * n; }; Объясните мне, в чем смысл создавать шаблон с заранее известным передаваемым типом? Мне казалось, что шаблоны существуют для того, что бы сделать передаваемый тип любым. подробнее

Показать сообщение отдельно
Harutyunyan
1 / 1 / 0
Регистрация: 28.09.2012
Сообщений: 91
24.10.2012, 10:47     Сортировка выбором
Добрый день, я заметил, что при сортировке массива из N элементов по алгоритму сортировки "Выбором", количество смены местами элементов массива всегда равна N-1.

Тоесть если количество элементов в массиве N = 1000, то количестве перестановок местами элементов будет равна 999.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SSort(int *mas, int c)
{
    for(int i = 0 ; i < N -1; i++)
    {
        int mn = i;
        for(int j = i; j < N; j++)
            if(mas[mn] > mas[j]) mn = j;
        
        int tp = mas[i];
        mas[i] = mas[mn];
        mas[mn] = tp;
        cnt++; // Счетчик на колтчество перестановок
    }
}
В алгоритме видно, что ксегда будет выполняться замена элементов местами, в не зависимости от того, что будет выполнено это условие if(mas[mn] > mas[j]) mn = j; или нет.

Я решил исправить этот момент:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SSort(int *mas, int c)
{
    for(int i = 0 ; i < N -1; i++)
    {
        bool q = false;
        int mn = i;
        for(int j = i; j < N; j++)
            if(mas[mn] > mas[j]) {mn = j; q = true;}
        if(q)
        {
            int tp = mas[i];
            mas[i] = mas[mn];
            mas[mn] = tp;
            cnt++; // Счетчик на колтчество перестановок
        }
    }
}
Теперь количество замен сократиться, в зависимости от выполненного условия.
Через этот вариант если: если N = 1000, то количество замен будет приблизительно 750.

Я бы хотел узнать, какой вариант будет работать быстрее?
Просто в первом случаее нет некаких дополнительных переменных и условий, но количество замен элементов местами N-1, а во втором случае количество зависет от выполненного условия, но там дополнительное условие стоит.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 14:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru