Программирование на C и C++

Онлайн справочник программиста на C и C++

сортировка выбором

Аватар пользователя merkul40
сб, 08/19/2017 - 12:05 -- merkul40

Доброго всем времени суток!
Я пытаюсь дальше разбираться в вопросах программирования на си.
Сортировка выбором заключается в поиске минимального (максимального) элемента массива и перестановке его на первую позицию в массиве (первый проход). Следующим проходом снова ищется минимальный (максимальный) элемент (без учета первого) и ставится на вторую позицию. И так далее до полного упорядочения массива.
В статьях в интернете пишется о неэффективности данного метода при большом массиве. На моем древнем компьютере весь код (заполнение массива случайными числами, сортировка массива из 1000 значений, вывод на экран) занимает около 1 сек. При увеличении членов массива до 10000 время выполнения кода 2 - 3 сек. При увеличении членов массива до 100 000 время выполнения кода 35 сек. Проблема метода заключается в большом количестве повторений переборов массива.

Код я наваял такой:

#include<stdio.h>
#include<stdlib.h>
#define N 100000                // Размер массива

int Mass[N];
int determination(void);
void printing(void);
int choise_sort(void);
void printing(void);

int main()
{
       
        determination();
        //printing();                                   //контрольный принт
        choise_sort();
        printing();
       
        return 0;        
        }
       
int determination(void)//функция присвоения значений массиву
{
        for (int i = 0; i <= (N - 1); i++)
        {
                Mass[i] = rand() % 5000;
                }
       
        }

int choise_sort(void)//функция упорядочения массива
{
        int min_number = 0, min_pos;
        for (int i = 0; i <= (N - 1);i++) // цикл циклов
        {
                min_pos = i;
                for (int j = i + 1; j <= (N - 1); j++) //цикл выбора минимального
                {                                                                               //значения за 1 проход
                if (Mass[min_pos] > Mass[j])
                {
                        min_pos = j;
                        }
                        }
                min_number = Mass[min_pos];//перестановка значений
                Mass[min_pos] = Mass[i];
                Mass[i] = min_number;
                }
        }
       
void printing(void)//функция вывода массива на экран
{
        for (int i = 0; i <= (N - 1); i++)
        {
                printf("%d\t%d\n", i + 1, Mass[i]);
                }
        }

В общем так как-то. Желаю удачи!