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

Сортировка массивов

Про сортировку массивов уже невероятно много материалов в интернете и в различных книгах. Однако из за такого наплыва информации, как не парадоксально, найти нужное становится сложнее. Так давайте попробуем разобраться в различных методах сортировок и сравним их на конкретных примерах. Из названия понятно, что реализовывать код мы будем на С++. Однако перенести алгоритм на любой другой язык программирования будет не сложно. И так приступим…

Так как это наша первая статья из данного цикла, давайте создадим шаблон для наших сортировок.

  • Заполнение массива
  • Вывод массива
  • Замер времени сортировки
  • Вывод результатов

[code]#include //Printf
#include //rand, srand
#include //clock, зерно

#define ARR_Size 10000 //Размер массива
#define RANGE 25 //Размах массива

int main(){
int tmp = 0;
clock_t t;
int arr[ARR_Size];
srand(time(NULL));
//###################—Заполнение массива—#################
for(int i = 0; i < ARR_Size; i++){
arr[i] = rand()%RANGE;
printf("%i element — %i\n",i,arr[i]);//Вывод массива
}
printf("\n\n\n");
//###################—Сортировка массива—#################
t = clock();//время

t = clock() — t;//время
//###################—Вывод сорт. массива—################
for(int i = 0; i %f",(float)t/CLOCKS_PER_SEC);//время
getchar();
return(0);
}
[/code]

Думаю, тут все понятно. Теперь приступим к разбору самого метода сортировки, под названием Selection sort.

Алгоритм состоит из 3 простых действий:

      Находим минимальное или максимальное значение в массиве
      Если элемент меньше или больше элемента первой неотсортированной позиции меняем их.
      Начинаем заново, откинув уже отсортированный список элементов

Реализация в С++ выглядит так:

[code] for(int k = 0; k < ARR_Size; k++){
for(int j = k; j < ARR_Size; j++){
if(arr[j] < arr[k]){
tmp = arr[j];
arr[j] = arr[k];
arr[k] = tmp;
}
}
}
[/code]

Теперь результаты замеров выполненных на ноутбуке.
ARR_Size = 1000 | Время: 0.002
ARR_Size = 10000 | Время: 0.193
ARR_Size = 100000 | Время: 19.221

Как видим, результат не радует. Использовать данный алгоритм не стоит при больших размерах массивов, так как время выполнения увеличивается пропорционально квадрату разницы размеров массивов.

1 Star2 Stars3 Stars4 Stars5 Stars (3 голосов, средний:5,00 из 5)
Вы можете пропустить чтение записи и оставить комментарий. Размещение ссылок запрещено.
Оставить комментарий