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

Метод пузырька (метод обменной сортировкой с выбором)

Сортировка одномерных массивов

Алгоритмы сортировки одномерных массивов

Лекция 9

Цели:

ü познакомиться с некоторыми алгоритмами сортировки массивов и разработки соответствующего проекта в среде Visual C++ 6.0.

Под сортировкой понимается упорядочение элементов некоторой последовательности в нужном порядке (убывания или возрастания). Существует достаточно много алгоритмов сортировок послед-овательностей. Но мы остановимся только на трёх, наиболее простых.

Идея метода отражена в его названии. Шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то они меняются местами. При этом самые «легкие» (наименьшие) элементы массива «всплывают» наверх, а самые «тяжелые» – «тонут». Алгоритмически это можно реализовать следующим образом. Весь массив просматривается снизу вверх, стоящие рядом элементы меняются в том случае, если «нижний» элемент меньше, чем «верхний». Таким образом, наверх «всплывет» самый «легкий» элемент всего массива. Так нужно повторять для оставшихся неотсортированными N-1 элементов (т.е. для тех, которые лежат «ниже» первого) и т.д. Алгоритм достаточно прост:

Алгоритм (в порядке возрастания)

Программа

объявление вещ: t[10], x, цел: i, j, k, flag для i=0 до 10-1 шаг 1 ввод t[i] все_для i для i=10-1 до 1 шаг -1 //обмена не было flag=0 для j=0 до i-1 шаг 1 если t[j]>t[j+1] //меняем местами два соседних //элемента x=t[j] t[j]=t[j+1] t[j+1]=x //обмен состоялся flag=1 все_если все_для j если flag==0 выход из цикла по i // не было // обмена все_если все_для i для i=0 до 10-1 шаг 1 вывод t[i] все_для i

#include "stdio.h" #include "math.h" #define N 10 int main () { float t[N], x; int i, j, k, flag; // ввод массива t с клавиатуры for (i=0; i<=N-1; i++) { printf ("x[%i]= ",i); scanf ("%f", &t[i]); } for (i=N-1; i>=1; i--) { //обмена не было flag=0; for (j=0; j<=i-1; j++) { if (t[j]>t[j+1]) { // элементы меняются // местами x=t[j]; t[j]=t[j+1]; t[j+1]=x; //обмен состоялся flag=1; } } if(flag= =0) //если обмена не было, то нужно //выйти из цикла break; } // вывод массива t на экран for (i=0; i<=N-1; i++) printf ("%.3f ", t[i]); printf ("\n"); return 1; }

При сортировке этим методом при просмотре массива ищется наименьший элемент, сравнивая его с первым. Если такой элемент найден, но меняется местами с первым. Затем эти действия повторяются, но не с первого элемента, а со второго. Так продолжается до тех пор, пока не будет отсортирован весь массив:

Алгоритм (в порядке возрастания)

Программа

объявление вещ: t[10], x, цел: i, j, k для i=0 до 10-1 шаг 1 ввод t[i] все_для i для i=0 до 10-1 шаг 1 k=i x=t[i] для j=i+1 до 10-1 шаг 1 если t[j]<x // меняем местами два // элемента x=t[j] k=j все_если t[k]=t[i] t[i]=x все_для j все_для i для i=0 до 10-1 шаг 1 вывод t[i] все_для i

#include “stdio.h” #include “math.h” #define N 10 int main() { float t[N], x; int i, j, k; //ввод массива с клавиатуры for(i=0;i<=N-1;i++) { printf("t[%i]=",i); scanf("%f",&t[i]); } // сортировка массива for(i=0;i<=N-1;i++) { k=i; x=t[i]; for(j=i+1;j<=N-1;j++) //находятся элементы, которые //нужно поменять местами if(t[j]<x) { k=j; x=t[j]; } //найденные элементы меняются //местами t[k]=t[i]; t[i] = x; } for(i=0; i <=N-1; i++) { printf("%.3f ",t[i]); } return 1; }