Форум программистов, компьютерный форум CyberForum.ru

Быстрая сортировка с разделением - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
katena88
 Аватар для katena88
5 / 1 / 1
Регистрация: 25.10.2010
Сообщений: 86
13.05.2011, 16:16     Быстрая сортировка с разделением #1
Помогите создать функцию быстрой сортировки с разделением.
Мы не изучали ее алгоритм в делфи.
Пока она выглядит так:
Код
/ ф-ция быстрой сортировки с разделением
int BSortirovka(int a, char* c)
{
    int i,j,p;
	int x;



   return 0;
}
Не получается даже готовый пример подогнать под мои данные
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2011, 16:16     Быстрая сортировка с разделением
Посмотрите здесь:

быстрая сортировка C++
Сортировка разделением C++
C++ Быстрая сортировка
Быстрая сортировка C++
C++ Быстрая сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
13.05.2011, 17:29     Быстрая сортировка с разделением #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Код
Псевдокод.

quickSort ( массив a, верхняя граница N ) {
    Выбрать опорный элемент p - середину массива
    Разделить массив по этому элементу
    Если подмассив слева от p содержит более одного элемента, 
        вызвать quickSort для него. 
    Если подмассив справа от p содержит более одного элемента,
         вызвать quickSort для него. 
}

Реализация на Си.
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
template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N;        // поставить указатели на исходные места
  T temp, p;
 
  p = a[ N>>1 ];        // центральный элемент
 
  // процедура разделения
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );
 
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}
Добавлено через 1 минуту
есть еще и мдификация со стеком:
Псевдокод.
Код
Итеративная QuickSort (массив a, размер size) {
Положить в стек запрос на сортировку массива от 0 до size-1.
	
	do {
        Взять границы lb и ub текущего массива из стека.
		do {
            1. Произвести операцию разделения над текущим массивом a[lb..ub].
            2. Отправить границы большей из получившихся частей в стек.
            3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
		} пока меньшая часть состоит из двух или более элементов
	} пока в стеке есть запросы
}
Реализация на Си.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#define MAXSTACK 2048       // максимальный размер стека
 
template<class T>
void qSortI(T a[], long size) {
 
  long i, j;            // указатели, участвующие в разделении
  
  long lb, ub;          // границы сортируемого в цикле фрагмента
 
  long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
                        // каждый запрос задается парой значений,
                        // а именно: левой(lbstack) и правой(ubstack) 
                        // границами промежутка
 
  long stackpos = 1;    // текущая позиция стека
  long ppos;            // середина массива
  T pivot;              // опорный элемент
  T temp; 
 
  lbstack[1] = 0;
  ubstack[1] = size-1;
 
  do {
 
    // Взять границы lb и ub текущего массива из стека.
 
    lb = lbstack[ stackpos ];
    ub = ubstack[ stackpos ];
    stackpos--;
 
    do {
      // Шаг 1. Разделение по элементу pivot
 
      ppos = ( lb + ub ) >> 1;
      i = lb; j = ub; pivot = a[ppos];
 
      do {
        while ( a[i] < pivot ) i++;
        while ( pivot < a[j] ) j--;
 
        if ( i <= j ) {
          temp = a[i]; a[i] = a[j]; a[j] = temp;
          i++; j--;
        }
      } while ( i <= j );
 
      // Сейчас указатель i указывает на начало правого подмассива,
      // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
      // Возможен случай, когда указатель i или j выходит за границу массива
 
      // Шаги 2, 3. Отправляем большую часть в стек  и двигаем lb,ub
 
      if ( i < ppos ) {     // правая часть больше
 
        if ( i < ub ) {     //  если в ней больше 1 элемента - нужно 
          stackpos++;       //  сортировать, запрос в стек
          lbstack[ stackpos ] = i;
          ubstack[ stackpos ] = ub;
        }
        ub = j;             //  следующая итерация разделения
                            //  будет работать с левой частью
 
      } else {              // левая часть больше
 
        if ( j > lb ) { 
          stackpos++;
          lbstack[ stackpos ] = lb;
          ubstack[ stackpos ] = j;
        }
        lb = i;
      }
 
    } while ( lb < ub );        // пока в меньшей части более 1 элемента
 
  } while ( stackpos != 0 );    // пока есть запросы в стеке
}
katena88
 Аватар для katena88
5 / 1 / 1
Регистрация: 25.10.2010
Сообщений: 86
13.05.2011, 18:23  [ТС]     Быстрая сортировка с разделением #3
у меня не получается
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
13.05.2011, 18:42     Быстрая сортировка с разделением #4
Цитата Сообщение от katena88 Посмотреть сообщение
у меня не получается
что именно? какие ошибки?
katena88
 Аватар для katena88
5 / 1 / 1
Регистрация: 25.10.2010
Сообщений: 86
13.05.2011, 20:05  [ТС]     Быстрая сортировка с разделением #5
Цитата Сообщение от blackbanny Посмотреть сообщение
что именно? какие ошибки?
я не понимаю по какому принципу это работает и соответственно не получается добавить функцию

Добавлено через 3 минуты
я сделала вот так
Код
// ф-ция быстрой сортировки с разделением
int BSortirovka(int N, char* a)
{
template<class T>
long i = 0, j = N;            // поставить указатели на исходные места
  T temp, p;

  p = a[ N>>1 ];                // центральный элемент

  // процедура разделения
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;

    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );


  // рекурсивные вызовы, если есть, что сортировать
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}

   return 0;
}
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
13.05.2011, 20:42     Быстрая сортировка с разделением #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
вот рабочий код, используй итеративный алгоритм:
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstdlib>
#include <iostream>
#define MAXSTACK 2048
using namespace std;
 
 
using namespace std;
int *a = new int[10]; //выделяем память под массив из 10 элементов
 
void qSortI(int size) {
 
  int i, j;             // указатели, участвующие в разделении
  
  int lb, ub;       // границы сортируемого в цикле фрагмента
 
  int lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
                        // каждый запрос задается парой значений,
                        // а именно: левой(lbstack) и правой(ubstack) 
                        // границами промежутка
 
  int stackpos = 1;     // текущая позиция стека
  int ppos;            // середина массива
  int pivot;              // опорный элемент
  int temp; 
 
  lbstack[1] = 0;
  ubstack[1] = size-1;
 
  do {
 
    // Взять границы lb и ub текущего массива из стека.
 
    lb = lbstack[ stackpos ];
    ub = ubstack[ stackpos ];
    stackpos--;
 
    do {
      // Шаг 1. Разделение по элементу pivot
 
      ppos = ( lb + ub ) >> 1;
      i = lb; j = ub; pivot = a[ppos];
 
      do {
        while ( a[i] < pivot ) i++;
        while ( pivot < a[j] ) j--;
 
        if ( i <= j ) {
          temp = a[i]; a[i] = a[j]; a[j] = temp;
          i++; j--;
        }
      } while ( i <= j );
 
      // Сейчас указатель i указывает на начало правого подмассива,
      // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
      // Возможен случай, когда указатель i или j выходит за границу массива
 
      // Шаги 2, 3. Отправляем большую часть в стек  и двигаем lb,ub
 
      if ( i < ppos ) {     // правая часть больше
 
        if ( i < ub ) {     //  если в ней больше 1 элемента - нужно 
          stackpos++;       //  сортировать, запрос в стек
          lbstack[ stackpos ] = i;
          ubstack[ stackpos ] = ub;
        }
        ub = j;             //  следующая итерация разделения
                            //  будет работать с левой частью
 
      } else {              // левая часть больше
 
        if ( j > lb ) { 
          stackpos++;
          lbstack[ stackpos ] = lb;
          ubstack[ stackpos ] = j;
        }
        lb = i;
      }
 
    } while ( lb < ub );        // пока в меньшей части более 1 элемента
 
  } while ( stackpos != 0 );    // пока есть запросы в стеке
}
 
int main()
{
    
    for (int i = 0; i < 10; i++)
    {
        a[i] = rand()%100;  //заполняем массив случайными числами
    }
    qSortI(10); //сортируем
    
    for (int i = 0; i < 10; i++)
    {
        cout << a[i] << endl;  //выводим отсортированный массив
    }
   return 0;
}
Добавлено через 40 секунд
и почитай здесь
Yandex
Объявления
13.05.2011, 20:42     Быстрая сортировка с разделением
Ответ Создать тему
Опции темы

Текущее время: 18:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru