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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Шаблон дерева. Оператор ввода http://www.cyberforum.ru/cpp-beginners/thread294770.html
Здравствуйте. Не могу перегрузить оператор ввода в шаблонном классе дерева. Идей что-то совсем нет ни один кода, что я пытался написать не компилировался. Помогите, пожалуйста. Вот сам класс. #pragma once #include <iostream> using namespace std; template <class T> struct Elem { T info; Elem *left, *right;
C++ Определить, является ли она магическим квадратом, т.е. такой, в которой суммы элементов во всех строках и столбцах одинаковы. Дана целая квадратная матрица n-го порядка. Определить, является ли она магическим квадратом, т.е. такой, в которой суммы элементов во всех строках и столбцах одинаковы. http://www.cyberforum.ru/cpp-beginners/thread294768.html
Записать на место отрицательных элементов матрицы нули, а на место положительных – единицы. C++
Дана квадратная матрица A. Записать на место отрицательных элементов матрицы нули, а на место положительных – единицы.
C++ ЕГЭ Информатика
На вход программы подаются прописные латинские буквы, ввод этих символов заканчивается точкой. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять, можно ли переставить эти буквы так, чтобы получился палиндром (палиндром читается одинаково слева направо и справа...
C++ ошибка в коде.положение 2ух точек относительно прямой http://www.cyberforum.ru/cpp-beginners/thread294732.html
попытался написать код, но выдает 3 ошибки((((((( вот код: #include "stdafx.h" #include <iostream> #include <stdio.h> #include <cmath> #include <list> #include <vector> #include <algorithm>
C++ структуры Найти три различные точки из заданного множества пространства точек, образующих треугольник наибольшего периметра. Прошу решить задачу через обычные библиотеки iostream и cmath так как других не знаю. подробнее

Показать сообщение отдельно
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
13.05.2011, 17:29     Быстрая сортировка с разделением
Код
Псевдокод.

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 );    // пока есть запросы в стеке
}
 
Текущее время: 12:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru