Отправляет email-рассылки с помощью сервиса Sendsay

Все обо всем

Подписаться Бесплатная новостная рассылка Подписчиков 20 RSS
  Апрель 2003   →
 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
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://enter2exit.narod.ru
Открыта: 30-03-2003

Автор
Константин

Статистика

20 подписчиков
0 за неделю
←   Все выпуски   →

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


Информационный Канал Subscribe.Ru

Все обо всем
№1 1.04.2003

Я решил начать расыслку с рассмотрения основных принцпов сортировки данных, а это является основной чертой многих современных программ, будь то СУБД, экспертная система или простая задача подсчета количества слов в словаре, состоящих из одинаковых букв. Везде необходимо использовать сортировку данных. И чем быстрее будет выполняться этот процесс, тем больше будет "поклонников" у Вашего программного средства. Ведь никому не хочется сидеть и ждать 30 минут, для сортировки ХХ миллионов записей в Вашей базе данных, особенно если эту же работу другая программа выполняет за 2-3 минуты, а может и быстрее.

Для начала посмотрим какие методы сейчас наиболее известны.

  1. Метод пузырька
  2. Метод выбора наименьшего элемента
  3. Метод Шелла
  4. Метод

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

Метод пузырька

Данный метод также имеет название сортировки простым обменом. Суть его в том, что самые "тяжелые" элементы тонут, а "легкие" - всплывают. То есть, проссматривая алгоритм сверху вниз и менять соседние элементы только в том случае, когда "нижний" элемент "легче" чем "верхний". Операция повторяется вначале для n элементов, потом для n-1, n-2 и до самого "верха" массива.

void puz()
{
  for(int a=0;a<MAX;a++)
    for(int b=0;b<MAX-1-a;b++)
      if(Ar[b]>Ar[b+1])
 {
 int r  = Ar[b];
 Ar[b]   = Ar[b+1];
 Ar[b+1] = r;
 Cnt++;   // подсчет количества обменов
 }
}

Метод выбора наименьшего элемента 

Для сортировки данных необходимо последовательно пройти весь массив, сравнивая i-ый элемент со всеми последующими, и найдя среди них наименьший, переставить его на i-ое место. После перебора всех элементов получится отсортированный массив.

void min()
{
  int c;
  for(int a=0;a<MAX-1;a++)
    for(int b=a+1;b<MAX;b++)
      if(Ar[a]>Ar[b])
 {
 int r = Ar[a];
 Ar[a] = Ar[b];
 Ar[b] = r;
        Cnt++;
 }
}

Метод Шелла

Метод Шелла - качественный переход от простой сортировки к более "умным" алгоритмам. В начале массив разбивается на 2 части и сравниваются элементы стоящие через одинаковое расстояние друг с другом, разделенные нашей границей. Так, если в массиве 10 элементов, то сравнение будет идти слеубщим образом: 1 с 6, 2 с 7, 3 с 8, 4 с 9, 5 с 10. При необходимости элементы меняются местами. Если за время одного полного прохода была хоть одна перестановка, то данный шаг повторяется еще раз. Если перестановок небыло, то массив делится уже не на 2, а на 4 (8, 16, ..) частей, и так до тех пор, пока не дайдем до сравнения элемента с его соседом

void shl()
{
  for(int dev=MAX/2; dev>0; dev = dev/2)
    {
    int rep = 1;
    while(rep)
 {
 rep = 0;
 for(int a=0; a<MAX-dev; a++)
   if(Ar[a]>Ar[a+dev])
     {
     rep = 1;
     Cnt++;
     int r = Ar[a];
     Ar[a] = Ar[a+dev];
     Ar[a+dev] = r;
     }
 }
    }
}

В заключении привожу пример программы, реализующей все эти алгоритмы. 

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX  10  //количество элементов массива
#define DISP 100  //разбег значений : от -(DISP/2) до (DISP/2)
int Ar[MAX];
int Cnt = 0;

void puz()
{
  for(int a=0;a<MAX;a++)
    for(int b=0;b<MAX-1-a;b++)
      if(Ar[b]>Ar[b+1])
 {
 int r  = Ar[b];
 Ar[b]   = Ar[b+1];
 Ar[b+1] = r;
 Cnt++;
 }
}

void min()
{
  int c;
  for(int a=0;a<MAX-1;a++)
    for(int b=a+1;b<MAX;b++)
      if(Ar[a]>Ar[b])
 {
 int r = Ar[a];
 Ar[a] = Ar[b];
 Ar[b] = r;
        Cnt++;
 }
}

void shl()
{
  for(int dev=MAX/2; dev>0; dev = dev/2)
    {
    int rep = 1;
    while(rep)
 {
 rep = 0;
 for(int a=0; a<MAX-dev; a++)
   if(Ar[a]>Ar[a+dev])
     {
     rep = 1;
     Cnt++;
     int r = Ar[a];
     Ar[a] = Ar[a+dev];
     Ar[a+dev] = r;
     }
 }
    }
}

void ins()
{
  for(int a=0; a<MAX-1; a++)
    {
    int max = 0;
    for(int b=0; b<MAX-a; b++)
      if(Ar[max]<Ar[b])
 max = b;

    int r = Ar[max];
    for(int c=max; c<MAX-a-1; c++)
      {
      Ar[c] = Ar[c+1];
      Cnt++;
      }
    Ar[MAX-a-1] = r;
    Cnt++;
    }
}

int main()
{
  clrscr();      //очищаем экран
  randomize();   //запускаем генератор случайных чисел
   //меню
  printf(" 1 - Метод пузырька\n 2 - Выбор наименьшего\n 3 - Метод Шелла\n 4 - Метод вставки\n--------------------\n 0 - Выход\n\nВаш выбор: ");
  int i;
  scanf("%d", &i);  //ожидаем ввод

  if (i==0)      //если 0
     return -1;  //выход

  printf("\n\nИсходный массив:\n");  //создаем исходный массив
  for(int j=0;j<MAX;j++)
    {
    Ar[j] = DISP/2-random(DISP);
    printf("%8d", Ar[j]);
    }

  if(i==1)                          //обработка пунктов меню
    puz();
  if(i==2)
    min();
  if(i==3)
    shl();
  if(i==4)
    ins();

  printf("\n\nРезультат:\n");      //вывод результата
  for(j=0;j<MAX;j++)
    printf("%8d", Ar[j]);
  printf("Количество перестановок: %d", Cnt);

  return 0;
}

В программе есть также алгоритм вставки, но его описание приводить не буду, в связи с малой эффективностью алгоритма

Так же программа дополнительно выводит количество перестановок, которое понадобилось для полной сортировки исходного массива. Можете сами проследить на сколько один алгоритм превосходит по возможностям другой.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное