Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 207, средняя оценка - 5.00
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
#1

Быстрая сортировка - C++

15.09.2009, 21:13. Просмотров 25318. Ответов 11
Метки нет (Все метки)

Дошёл до темы быстрой сортировки, набрал код, начал компилировать. Что-то странно, всё написано правильно, уже проверял, 8 раз, программа компилируется, но результат отсортированного массива не выдаёт, выдаёт только исходный результат.

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
#include <iostream>
using namespace std;
 
void quicksort(char *items, int len);
void qs(char *items, int left, int right);
 
int main()
{
    setlocale(0,"");
    char str[] = "вгдба";
    cout<<"Масив в исходном порядке: "<<str<<endl;
    quicksort(str,strlen(str));
    cout<<"Отсортированный масив: "<<str<<endl;
cin.get();
}
 
 
void quicksort(char *items, int len)
{
    qs(items,0, len - 1);
}
 
void qs(char *items, int left, int right)
{
    int i,j;
    char x,y;
    i = left;   j = right;
    x = items[(left+right)/2];
    do {
        while((items[i] < x) && (i < right)); i++;
        while((x < items[j]) && (j > left)); j--;
    if(i<=j)
        {
            y = items[i];
            items[i] = items[j];
            items[j] = y;
            i++; j--;
        }
    } while(i <= j);
 
if(left < j) qs(items,left,j);
if(i < right) qs(items,i,right);
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.09.2009, 21:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрая сортировка (C++):

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий...

Быстрая сортировка (сортировка методом Хоара) - C++
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке убывания. Вывести массивы до и после...

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

Сортировка расчёской и быстрая сортировка - C++
В файле in.txt записана последовательность целых чисел. Заданными методами отсортировать числа и записать в файлы out1.txt и out2.txt....

11
M128K145
Эксперт С++
8297 / 3517 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
15.09.2009, 21:23 #2
Syltan, у тебя сортировка обрывается. Перепиши в соответствии с Алгоритмы сортировок
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
15.09.2009, 23:49  [ТС] #3
Что-то попробывал реализовать быструю сортировку,но не выходит. Вот что за бред получился.
Как мне например отсортировать 200 чисел случайных, которые выходят случайным образом и ещё ей же отсортировать буквы(200 штук). Буду благодарен, за ответ.

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
#include <iostream>
using namespace std;
template<class T>
void quickSortR(T* a, long N);
 
int main()
{
setlocale(0,"");
cout<<quickSortR(......);
cin.get();
}
 
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);
}
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
17.09.2009, 21:03  [ТС] #4
Вот решение задачи выше,которую я попросил помочь. Если кто может,дополните коментарием вот этот,код,желательно как можно больше:
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
#include <iostream>
 
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); //Вот это тоже не ясно что делается
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    char str[] = "бвгда";
    quickSortR(str, strlen(str));
    std::cout << str << std::endl;
    int a[] = { 2, 5, 1, 20, 8, 0, 9 };
    quickSortR(a, 6);
 
    for(int i = 0; i < 7; i++)
        std::cout << a[i] << " ";
 
    std::cout << std::endl;
 
    return 0;
}
0
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
17.09.2009, 22:38 #5
быстрая сортировка или сортировка Хоара. это нужно было?

на вход передаешь ссылку на массив и количество элементов массива.
тут 2 функции - одна подготавливает сортировку, вторая непосредственно сортирует
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
void quick(char *items, int count)
{
  qs(items, 0, count-1);
}
 
void qs(char *items, int left, int right)
{
  register int i, j;
  char x, y;
 
  i = left; j = right;
  x = items[(left+right)/2];
 
  do {
    while((items[i] < x) && (i < right)) i++;
    while((x < items[j]) && (j > left)) j--;
 
    if(i <= j) {
      y = items[i];
      items[i] = items[j];
      items[j] = y;
      i++; j--;
    }
  } while(i <= j);
 
  if(left < j) qs(items, left, j);
  if(i < right) qs(items, i, right);
}
1
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
17.09.2009, 23:06  [ТС] #6
Ответьте пожалуйста на 4-ый пост. Благодарю.

Очень нужно разобраться с сортировкой. Допишите пожалуйста комментарий, кому не сложно в строках там где я указал,что мне не ясно.
0
kravam
быдлокодер
1702 / 889 / 45
Регистрация: 04.06.2008
Сообщений: 5,498
18.09.2009, 18:31 #7
Если тебе нужно разобраться с синтаксисом- то сам знаешь, что делать.
Если тебе нужно разобраться с алгоритмом- ищи код (алгоритм быстрой сортировки), синтаксис которого тебе понятен, выкладывай сюда и пиши, что тебе непонятно в алгоритме. Обрати внимание на код Акеллы.
0
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
18.09.2009, 18:43  [ТС] #8
Алгоритм в 6 посте описан, просто прокомментируйте строки в коде где я указал и всё.
0
Fuse
2 / 2 / 0
Регистрация: 14.11.2009
Сообщений: 44
23.03.2010, 18:51 #9
объясните пожалуйста этот кусок кода
C++
1
2
3
...
if ( N > i ) quickSortR(a+i, N-i);
...
0
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
23.03.2010, 18:55 #10
рекурсивно вызов процедуры самой собой, с передачей параметров в зависимости от того какой результат даст логическое выражение
0
Fuse
2 / 2 / 0
Регистрация: 14.11.2009
Сообщений: 44
23.03.2010, 19:13 #11
это понятно...
я имею ввиду первый параметры (a+i, N-i);

а - это же массив,и как это к массиву прибавляется число?или что?
0
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
23.03.2010, 19:16 #12
эх вы=))) это же основа еще великого Си=)))
имя массива - указатель на его первый елемент=) a+i - сдвиг по маиву на i элементов
1
23.03.2010, 19:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2010, 19:16
Привет! Вот еще темы с ответами:

Быстрая сортировка - C++
Читал о быстрой сортировки смысл понятен но не могу понять некоторые моменты. Каким образом работают два последних условия? Они работают...

Быстрая сортировка - C++
Помогите пожалуйста, при использовании алгоритма быстрой сортировки, конечный массив получается не отсортированным, хотя все операции...

Быстрая сортировка - C++
Задача: пользователь задает количество элементов массива (макс. - 500 000), вводит их, затем задает количество запросов (макс. - 10000) и...

Быстрая сортировка - C++
Друзья, здравствуйте! Как работает быстрая сортировка - у меня практически вопросов нет: #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru