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

Проблемы с "Быстрой сортировкой" - C++

Восстановить пароль Регистрация
 
assasko
0 / 0 / 0
Регистрация: 20.05.2011
Сообщений: 18
03.04.2012, 12:57     Проблемы с "Быстрой сортировкой" #1
Ребята, всем привет, не могли бы вы мне помочь. Столкнулся с быстрой сортировкой, но что-то не выходит ее реализовать. Вот код:
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
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <windows.h>
 
using namespace std;
void myqsort(int * massive, int left, int right);
 
int main(int argc, char *argv[])
{
    cout << "Zadayte chislo elementov v massive N = ";
    int n;
    cin >> n;
    int *mas=new int[n];
    srand((unsigned)time(NULL));
    for (int i=0; i<n; i++)
    { mas[i]=(int)rand()/rand()+1;
    cout << mas[i] <<" ";}
    cout << endl;
    cout << "==========================================="<<endl;
    double t1=clock();
    myqsort(mas,0,n-1);
    double t2=clock();
    for (int i=0; i<n; i++)
    {cout << mas[i] <<" ";}
    cout << endl;
    cout <<"t1 = "<<t1<<endl;
    cout <<"t2 = "<<t2<<endl;
    cout << "\nVremya rascheta = " <<(t2-t1)/CLOCKS_PER_SEC << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}
 
void myqsort(int * mas, int lb, int rb){
int tmp;
if ((lb+1==rb)&(mas[lb]>mas[rb]))
   {
    tmp = mas[lb];
    mas[lb]=mas[rb];
    mas[rb]=tmp;
   }
if (lb+1<rb)
   {
    int key=mas[lb];
    int i_left=lb+1;
    int i_right=lb;
    while(i_left<=i_right)
      {
       while((mas[i_left]<key)&(i_left<rb))i_left++;
       while((key<=mas[i_right])&(lb<i_right))i_right--;
       if(i_left<i_right)
         {
          tmp=mas[i_left];
          mas[i_left]=mas[i_right];
          mas[i_right]=tmp;
         }
      }
      if(i_left>=i_right)
       {
        tmp=mas[i_right];
        mas[i_right]=mas[lb];
        mas[lb]=tmp;
       }
      myqsort(mas,lb,i_right-1);
      myqsort(mas,i_right+1,rb); 
   }   
}
Сортировка не работает, выполняется только перестановка предпоследнего и последнего элементов, если предпоследний больше последнего. Помогите найти проблемку в коде, пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
03.04.2012, 13:08     Проблемы с "Быстрой сортировкой" #2
Алгоритмы сортировок
panicwassano
590 / 558 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
03.04.2012, 13:15     Проблемы с "Быстрой сортировкой" #3
assasko непонятно зачем изобретать то, что изобрели 50 лет назад?
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
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);
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
03.04.2012, 13:39     Проблемы с "Быстрой сортировкой" #4
Ну, товарищи, если тупо копировать чужие программы, программировать не научишься. Хотя в этой ситуации стоит конечно брать пример с готового кода
Из его алгоритма я понял, что функция делит массив на две неравные части, в отличие от требований классического алгоритма. Но затем всё честно раскидывается. влево - элементы, меньшие ключа, вправо - большие. Это, конечно, забирает у алгоритма его ценную быстроту, не уверен на сколько это портит алгоритм, но работоспособности явно не лишает, конечно ключ лучше выбирать посередине.

Единственная проблема: сам ключ остаётся в левой части и стоит не на месте. В этом и причина, на мой взгляд

Добавлено через 18 минут
А не, не в этом. Чёрт побери!!!

а вот это
C++
1
(mas[i_left]<key)&(i_left<rb)
Запомните уже отличие между операторами & и &&
assasko
0 / 0 / 0
Регистрация: 20.05.2011
Сообщений: 18
03.04.2012, 22:43  [ТС]     Проблемы с "Быстрой сортировкой" #5
Цитата Сообщение от panicwassano Посмотреть сообщение
assasko непонятно зачем изобретать то, что изобрели 50 лет назад?
Я понимаю, что изобретать нет смысла, но просто стоит задача написать самому, а не брать уже готовое.

Добавлено через 1 минуту
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Ну, товарищи, если тупо копировать чужие программы, программировать не научишься. Хотя в этой ситуации стоит конечно брать пример с готового кода
Из его алгоритма я понял, что функция делит массив на две неравные части, в отличие от требований классического алгоритма. Но затем всё честно раскидывается. влево - элементы, меньшие ключа, вправо - большие. Это, конечно, забирает у алгоритма его ценную быстроту, не уверен на сколько это портит алгоритм, но работоспособности явно не лишает, конечно ключ лучше выбирать посередине.

Единственная проблема: сам ключ остаётся в левой части и стоит не на месте. В этом и причина, на мой взгляд

Добавлено через 18 минут
А не, не в этом. Чёрт побери!!!

а вот это
C++
1
(mas[i_left]<key)&(i_left<rb)
Запомните уже отличие между операторами & и &&
Проблема не в этом, все равно местами меняются только последний и предпоследний элементы, в том случае когда предпоследний больше последнего.
Yandex
Объявления
03.04.2012, 22:43     Проблемы с "Быстрой сортировкой"
Ответ Создать тему
Опции темы

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