Сортировка

@maks3 · Регистрация: 22.02.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте
подскажите пожалуйста как правильно называется эта сортировка ?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{
String buff;
 for (int i = 0; i < StringGrid1->RowCount-1; i++)
  for (int j = i; j < StringGrid1->RowCount; j++)
    {
     if (StringGrid1->Cells[0][i]>StringGrid1->Cells[0][j])
     {
     for(int k=0;k<7;k++)  // количество сортируемых столбцов
        {
          buff=StringGrid1->Cells[k][i];
          StringGrid1->Cells[k][i]= StringGrid1->Cells[k][j];
          StringGrid1->Cells[k][j]=buff;
        }
     }
    }
}

@kzru_hunter · 22.02.2011, 20:27

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

@maks3 · 22.02.2011, 21:11 **[ТС]**

А вот эта?
я так понимаю что такую сортировку можно применять для сортировки 0 столбца :ColN=0
а сортировка называется по миним. индексу?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 int i,j,minInd,ColN=0;
AnsiString minVal;
TStringList *sl = new TStringList;
 for(i=1; i<StringGrid1->RowCount; i++)
       {
        minInd = i;
        minVal = StringGrid1->Cells[ColN][i];
        for(j = i+1; j<StringGrid1->RowCount; j++)
            {
             if(minVal > StringGrid1->Cells[ColN][j])
                {
                 minInd = j;
                 minVal = StringGrid1->Cells[ColN][j];
                 //перенос кода внутрь if
                 sl->Text = StringGrid1->Rows[minInd]->Text;
                 StringGrid1->Rows[minInd]->Text = StringGrid1->Rows[i]->Text;
                 StringGrid1->Rows[i]->Text = sl->Text;
                }
            }
       }
delete sl;
}

cpp_developer · 23.02.2011, 02:51

для общего развития:

@kzru_hunter · 23.02.2011, 09:56

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

@Dr.Xank · 23.02.2011, 17:15

Сообщение от LK

для общего развития:

LK А вы не могли бы выложить сортировку на С++, а то в архиве у вас на Дельфи или паскаль.

cpp_developer · 23.02.2011, 17:45

гм...

Алгоритмы сортировки.

В общем случае сортировку следует понимать как процесс перегруппировки, заданного множества объектов в определенном порядке.

Сортировка применяется для облегчения поиска элементов в упорядоченном множестве. Задача сортировки одна из фундаментных в программировании. В большинстве случаев необходимо отсортировать многочлен, элементами которого являются целые числа. Различают два вида сортировки: внутреннюю и внешнюю.

Под внутренней сортировкой понимают сортировку массивов, так как массив можно поместить на хранение в оперативную (внутреннюю) память.

Под внешней сортировкой понимают сортировку файлов, т.к. файлы хранящиеся во внешней памяти, не всегда могут поместиться в оперативной памяти.

Мы будем рассматривать только внутреннюю сортировку.

Общая задача сортировки: пусть имеется множество элементов А={a1, a2,…, ap}. Под сортировкой будем понимать перестановку этих элементов в множество A’={ak1, ak2,…, akp}, где при некоторой упорядочивающей функции f:A ->A’ выполняется соотношение f(a1)f(a2)… f(ap), причем, aki=f(ai).

§2. Пузырьковая сортировка.

Будем рассматривать линейный массив как вектор столбец.
11
3
5
4
1

Сначала рассмотрим элементы от первого до последнего. Начиная с последнего элемента, будем рассматривать пары соседних элементов, если « верхний» элемент больше(тяжелее) «нижнего», то обменяем их местами. Указанный процесс обмена повторим для всех множеств от i до р. При последовательных обменах более «легкие» элементы ( с меньшими значениями) как бы всплывают наверх, а более «тяжелые» оседают вниз. За такую особенность указанный алгоритм получил название пузырьковой сортировки.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void b_sort(int *a,int n)
{
    int tmp,i,j;
 
        for(i = 0;i < n; i++)
         for(j=i+1; j < n; j++)
            if(a[i]>a[j])
            {
                tmp=a[j];
                a[j]=a[i];
                a[i]=tmp;
 
            };
 
}

Buble sort:
Time before: 3 24
>> 4 17 46 15 73 57 9 51 91 44<<
>> 4 15 46 17 73 57 9 51 91 44<<
>> 4 9 46 17 73 57 15 51 91 44<<
>> 4 9 17 46 73 57 15 51 91 44<<
>> 4 9 15 46 73 57 17 51 91 44<<
>> 4 9 15 17 73 57 46 51 91 44<<
>> 4 9 15 17 57 73 46 51 91 44<<
>> 4 9 15 17 46 73 57 51 91 44<<
>> 4 9 15 17 44 73 57 51 91 46<<
>> 4 9 15 17 44 57 73 51 91 46<<
>> 4 9 15 17 44 51 73 57 91 46<<
>> 4 9 15 17 44 46 73 57 91 51<<
>> 4 9 15 17 44 46 57 73 91 51<<
>> 4 9 15 17 44 46 51 73 91 57<<
>> 4 9 15 17 44 46 51 57 91 73<<
>> 4 9 15 17 44 46 51 57 73 91<<
Time after: 3 24

§ 3. Сортировка выбором.

Пусть имеется множество A={a 1 ,…, a p } выберем среди элементов a1 ,…, ap наименьший и обменяем его местами с первым. Выберем среди элементов a2 ,…, ap наименьший и обменяем его местами со вторым и т.д. На i-ом шаге выберем среди элементов a i,…,a p наименьший и обменяем его местами с i-ым, продолжать будем до тех пор, пока не достигнем последнего элемента.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void se_sort(int *a,int n)
 
{
 
    int tmp,i,j,xx;
 
for(i = 0; i < n; i++)
 
          {
 
        xx=i;
 
        for( j=i+1; j < n; j++)
 
            if(a[j] < a[xx] ) xx=j;
 
        tmp=a[i];
 
        a[i]=a[xx];
 
        a[xx]=tmp;
 
 
      };
}

Selection sort:
Time before: 3 24
>> 4 44 17 15 73 57 9 51 91 46<<
>> 4 9 17 15 73 57 44 51 91 46<<
>> 4 9 15 17 73 57 44 51 91 46<<
>> 4 9 15 17 46 57 44 51 91 73<<
>> 4 9 15 17 44 57 46 51 91 73<<
>> 4 9 15 17 44 51 46 57 91 73<<
>> 4 9 15 17 44 46 51 57 91 73<<
>> 4 9 15 17 44 46 51 57 73 91<<
Time after: 3 24

§4. Быстрая сортировка.

Данный алгоритм был предложен Ч. Хоаром.
Описание алгоритма.
Рассмотрим произвольный массив. Выберем произвольный элемент массива х. Далее перестроим массив таким образом, чтобы в части от первого элемента до х располагались не превосходящие х, а в части от х до последнего элемента не меньшие х.
Для этого находим пары элементов не удовлетворяющих условию и меняем их местами. Далее такой алгоритм применим к левой и правой частям массива.

Пример:

11, 5, 13, 10, 8, 14, 6
6, 5, 13, 10, 8, 14, 11
6, 5, 8, 10, 13, 14, 11
6, 5, 8, 10 10, 13, 14, 11
5, 6, 8, 10 10, 11, 14, 13
5, 6 6, 8, 10 10,11 11, 14, 13
11, 13, 14
5,6,8,10,11,13,14

Алгоритм Хоара связан с выбором элемента х как границы между частями массива, чем «лучше» пограничный элемент х, тем «быстрее» происходит сортировка.

В массиве существует элемент называемый медианой, т.е. количество меньших его равно количеству больших его. Наиболее удобным будет выбирать медианы в качестве х, но поиск медианы сопряжен с существенными вычислительными затратами. В большинстве случаев в качестве х-пограничного элемента в части массива от L до R выбирают элемент [(R+L)/2].

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void q_sort(int *a,int Lo,int Ma)
{
    int md,L=Lo,M=Ma,tmp;
    md=a[(L+M)/2];
    do
    {
        while(a[L]md)M--;
        if(L<=M)
        {
            tmp=a[L];
            a[L]=a[M];
            a[M]=tmp;
            L++;
            M--;
        };
    }
    while(L<=M);
    if (M > Lo) q_sort (a,Lo,M);
    if (L < Ma) q_sort (a,L,Ma);
}

Quick sort:
Time before: 3 24
>> 4 46 17 15 44 57 9 51 91 73<<
>> 4 9 17 15 44 57 46 51 91 73<<
>> 4 9 15 17 44 57 46 51 91 73<<
>> 4 9 15 17 44 57 46 51 91 73<<
>> 4 9 15 17 44 51 46 57 91 73<<
>> 4 9 15 17 44 51 46 57 91 73<<
>> 4 9 15 17 44 46 51 57 91 73<<
>> 4 9 15 17 44 46 51 57 73 91<<
Time after: 3 24

§ 5. Сортировка включением.

Описание алгоритма: пусть имеется множество А={a1, a2,…, ap}
1.Разделим множество А на две части.
A={a1,a2,…, ai}{ai+1,…, ap}, обозначим их AL и AR
Предполагается, что часть АL уже отсортирована.
2.Возьмем первый элемент части АR и поместим его в часть АL так, чтобы его порядок не нарушился.
3.Продолжаем, указанный процесс, до тех пор, пока не будет исчерпана часть АR.

На начальном этапе предполагается, что АL содержит только первый элемент множества А.

Для помещения элемента в отсортированную часть, используется процедура просеивания, которая состоит в следующем: пусть имеется элемент х, сравним его с последним элементом, отсортированной части.
Если порядок не нарушается, т. е. xai, то x станет последним элементом множества.
Если выполняется х < ai, то сдвинем на позицию вправо ai+1->ai+1 и будем сравнивать x с ai
Продолжаем процесс до тех пор,пока не найдем такой элемент aj, что хaj.

C++
1
2
3
4
5
6
7
8
9
void in_sort(int a[100], int n)
{int tmp,i,j;
for( i = 1; i < n; i++)
    {tmp=a[i];
    for ( j=i-1; j>=0 && tmp < a[j]; j--)
        a[j+1] = a[j];
    a[j+1] = tmp;
    }
}

Insertion sort:
Time before: 3 24
>> 4 46 17 15 73 57 9 51 91 44<<
>> 4 17 46 15 73 57 9 51 91 44<<
>> 4 15 17 46 73 57 9 51 91 44<<
>> 4 15 17 46 73 57 9 51 91 44<<
>> 4 15 17 46 57 73 9 51 91 44<<
>> 4 9 15 17 46 57 73 51 91 44<<
>> 4 9 15 17 46 51 57 73 91 44<<
>> 4 9 15 17 46 51 57 73 91 44<<
>> 4 9 15 17 44 46 51 57 73 91<<
Time after: 3 24

@maks3 · 24.02.2011, 23:38 **[ТС]**

спасибо, буду дальше изучать разбираться

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@kzru_hunter 1124 / 795 / 101 Регистрация: 01.02.2011 Сообщений: 1,887 Записей в блоге: 1
	22.02.2011, 20:27
	Сортировка выбором 1

@kzru_hunter 1124 / 795 / 101 Регистрация: 01.02.2011 Сообщений: 1,887 Записей в блоге: 1
	23.02.2011, 09:56
	Насчет сортировки выбором ошибся, хотя алгоритмы немного похожи. Я бы назвал эту сортировку простой. Алгоритм сортировки, используемый в 2-х постах, один и тот же. 0

@maks3 0 / 0 / 0 Регистрация: 22.02.2011 Сообщений: 5
	24.02.2011, 23:38 [ТС]
	спасибо, буду дальше изучать разбираться 0