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

Аватар пользователя 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]);
		}
	}
 
В общем так как-то. Желаю удачи!