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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 207, средняя оценка - 5.00
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
15.09.2009, 21:13     Быстрая сортировка #1
Дошёл до темы быстрой сортировки, набрал код, начал компилировать. Что-то странно, всё написано правильно, уже проверял, 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);
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
15.09.2009, 21:23     Быстрая сортировка #2
Syltan, у тебя сортировка обрывается. Перепиши в соответствии с Алгоритмы сортировок
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);
}
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;
}
Акелла
Сонный металюга
 Аватар для Акелла
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);
}
Syltan
181 / 7 / 0
Регистрация: 27.08.2009
Сообщений: 868
17.09.2009, 23:06  [ТС]     Быстрая сортировка #6
Ответьте пожалуйста на 4-ый пост. Благодарю.

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

а - это же массив,и как это к массиву прибавляется число?или что?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2010, 19:16     Быстрая сортировка
Еще ссылки по теме:

Быстрая сортировка (сортировка Хоара) для связных списков C++
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
Акелла
Сонный металюга
 Аватар для Акелла
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
23.03.2010, 19:16     Быстрая сортировка #12
эх вы=))) это же основа еще великого Си=)))
имя массива - указатель на его первый елемент=) a+i - сдвиг по маиву на i элементов
Yandex
Объявления
23.03.2010, 19:16     Быстрая сортировка
Ответ Создать тему
Опции темы

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