Вторник, 19.03.2024, 06:27
Приветствую Вас, Гость |
Меню сайта
Наш опрос
Нужен ли форум на этом сайте?
Всего ответов: 1296
Статистика

Онлайн всего: 2
Гостей: 2
Пользователей: 0

Алгоритм «Быстрой сортировки» (QuickSort). Реализация на Паскале

    Описание алгоритма быстрой сортировки:

Идея – более эффективно переставлять элементы, расположенные дальше друг от друга.
1
шаг:
выбрать некоторый элемент массива X   
2 шаг: переставить элементы так:
A[i] <= X           A[i] >= X
при сортировке элементы не покидают « свою область»!  
3 шаг:    так же отсортировать две получившиеся области

78
6
82
67
55
44
34
Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).
Разделение: 
выбрать средний элемент массива (X=67)
             
1)
78
6
82
67
55
44
34
Разделение:
1)
выбрать средний элемент массива (X=67)            
2)установить L:=1, R:=N
3)увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
4)уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
5)если L<=R, поменять местами A[L] и A[R] и перейти
к п. 3
Код:        


Реализация сортировки Quick Sort на паскале:


   procedure QSort ( first, last: integer);
   var L, R, c, X: integer;
   begin
      if first < last then
      begin
         X:= A[(first + last) div 2];
         L:= first;
         R:= last;
            while L <= R do
            begin
               while A[L] < X do
                  L:= L + 1;
               while A[R] > X do
                  R:= R - 1;
               if L <= R then
               begin
                  c:= A[L];
                  A[L]:= A[R];
                  A[R]:= c;
                  L:= L + 1;
                  R:= R - 1;
               end;
           end;
        QSort(first, R); 
        QSort(L, last);
     end;
  end.


   program qq;
   const N = 10;
   var A: array[1..N] of integer;
   begin
      { заполнить массив }
      { вывести исходный массив на экран }
      Qsort ( 1, N ); { сортировка }
      { вывести результат }
   end.



Сравнение быстрой сортировки QuickSort и сортировки пузырьком. Количество перестановок(случайные данные):

N
QuickSort
«пузырек»
10
11
24
100
184
2263
200
426
9055
500
1346
63529
1000
3074
248547





Форма входа
Поиск
Мы в сети
Реклама
Для того чтобы не видеть рекламу в правом верхнем углу сайта пройдите простую процедуру регистрации
ФОРУМ
У нас наконецто появился форум! Добро пожаловать! Будьте первыми, задайте направление форуму! =)
--- Не стесняемся - заходим на форум! ---