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

Ошибка в быстрой сортировке - C++

Восстановить пароль Регистрация
 
MisS_Rediska
Сообщений: n/a
13.05.2013, 16:43     Ошибка в быстрой сортировке #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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
const long int n=100;
using namespace std;
 
void BubbleSort(int array[], int col)
{                    
        int temp=0,i,j;                              
        for (i=1;  i<col  ;  i++) // i - номер текущего шага
        {            
                for (j=0;  j<col-i;  j++)
                {     
                        if (array [j]>array [j+1])          //сравнение элементов
                        {     
                                temp=array[j];              //обмен
                                array [j]=array [j+1];    
                                array [j+1]=temp;
                        }
                }
        }
}
void SelectSort(int arr[], int col) 
{
    int tmp, j, i,pos;
    for(i = 0; i < col; ++i) // i - номер текущего шага
    { 
        pos = i; 
        tmp = arr[i];
        for(j = i + 1; j < col; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] < tmp) 
           {
               pos = j; 
               tmp = arr[j]; 
           }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}
void QuickSort(int arr[], int col) 
{
  int i = 0, j = col;        // поставить указатели на исходные места
  int temp, p;
 
  p = arr[ col/2 ];        // центральный элемент
 
  // процедура разделения
  do 
   {
    while ( arr[i] < p ) i++;
    while ( arr[j] > p ) j--;
 
    if (i <= j) 
    {
      temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
      i++; j--;
    }
   } 
   while ( i<=j );
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) QuickSort(arr, j);
  if ( col > i ) QuickSort(arr+i, col-i);
}
void main()
{ int a[n],i; 
  unsigned int m;
setlocale(LC_ALL, "Russian");
  //Массивы случайных чисел для сортировки:
   srand(time(NULL));
   cout<<"Массив для сортировки:"<<" ";
   cout<<endl;
   for (i=0;i<n;i++)
   { a[i]=-100+rand()%301;
     cout<<a[i]<<" ";
   }
   cout<<endl;
   cout<<"Примечание: 1 - Cортировка пузырьком,\n";
    cout<<"            2 - Cортировка методом выбора,\n"; 
    cout<<"            3 - Быстрая сортировка.";
   cout<<endl;
   cout<<"Введите метод сортировки: ";
   cin >> m;
   switch(m)
   { case 1: BubbleSort(a, n); 
             cout << "Массив после сортировки <Пузырьком>: ";
              cout<<endl;
               for ( i = 0; i < n; i ++ )
               {
                cout << a[i] << " ";
                }; break;
     case 2: SelectSort( a, n );
           cout << "Массив после сортировки методом <Выбора>: ";
           cout<<endl;
             for ( i = 0; i < n; i ++ )
             {
                cout << a[i] << " ";
             }; break;
     case 3: QuickSort( a, n );
             cout << "Массив после <Быстрой сортировки>: ";
             cout<<endl;
               for ( i = 0; i < n; i ++ )
                {
                 cout << a[i] << " ";
                };break;
    
   }
}
Сортировка методом пузырька и посредством выбора работают, но при вызове быстрой сортировке возникает ошибка:
Ошибка в быстрой сортировке

Что делать?='(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2013, 16:43     Ошибка в быстрой сортировке
Посмотрите здесь:

C++ Визуализатор по быстрой сортировке Хоара на С++
C++ Ошибка в сортировке
Ошибка в сортировке C++
Ошибка в пирамидальной сортировке C++
Структыру.Ошибка в сортировке C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
13.05.2013, 16:59     Ошибка в быстрой сортировке #2

Не по теме:

Цитата Сообщение от MisS_Rediska Посмотреть сообщение
Что делать?='(
главное не вешаться



строку
C++
1
int i = 0, j = col;
заменить на
C++
1
int i = 0, j = col-1;
Добавлено через 1 минуту
и не пишите
C++
1
void main()
пишите
C++
1
int main()
MisS_Rediska
Сообщений: n/a
13.05.2013, 17:30     Ошибка в быстрой сортировке #3
Спасибо большое, теперь никакой ошибки )

З.Ы. и вешаться передумала
просто спасли меня)
faLek
99 / 100 / 7
Регистрация: 06.03.2012
Сообщений: 478
13.05.2013, 18:25     Ошибка в быстрой сортировке #4
C++
1
быстрая сортировка некорректно сортирует..
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
13.05.2013, 18:35     Ошибка в быстрой сортировке #5
faLek, странно, потому что эта сортировка с Википедии
faLek
99 / 100 / 7
Регистрация: 06.03.2012
Сообщений: 478
13.05.2013, 19:21     Ошибка в быстрой сортировке #6
ну вы проверьте как она у вас сортирует...
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
13.05.2013, 19:29     Ошибка в быстрой сортировке #7
faLek, плохо сортирует
faLek
99 / 100 / 7
Регистрация: 06.03.2012
Сообщений: 478
13.05.2013, 19:45     Ошибка в быстрой сортировке #8
metaluga145, а если плохо,значит не сортирует

Добавлено через 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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
const int n=100;
using namespace std;
 
 
void BubbleSort(int *array, int col)
{                    
        int temp=0,i,j;                              
        for (i=1;  i<col  ;  i++) // i - номер текущего шага
        {            
                for (j=0;  j<col-i;  j++)
                {     
                        if (array [j]>array [j+1])          //сравнение элементов
                        {     
                                temp=array[j];              //обмен
                                array [j]=array [j+1];    
                                array [j+1]=temp;
                        }
                }
        }
}
void SelectSort(int *arr, int col) 
{
    int tmp, j, i,pos;
    for(i = 0; i < col; ++i) // i - номер текущего шага
    { 
        pos = i; 
        tmp = arr[i];
        for(j = i + 1; j < col; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] < tmp) 
           {
               pos = j; 
               tmp = arr[j]; 
           }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}
void QuickSort(int *arr, int col) 
{
  int i = 0, j = col;        // поставить указатели на исходные места
  int temp, p;
 
  p = arr[ col/2 ];        // центральный элемент
 
  // процедура разделения
  do 
   {
    while ( arr[i] < p ) i++;
    while ( arr[j] > p ) j--;
 
    if (i <= j) 
    {
      temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp;
      i++; j--;
    }
   } 
   while ( i<=j );
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) QuickSort(arr, j);
  if ( col > i ) QuickSort(arr+i, col-i);
}
 
 
void main()
{ 
    int a[n],i; 
    unsigned int m;
 
    setlocale(LC_ALL, "Russian");
  //Массивы случайных чисел для сортировки:
   srand(time(NULL));
   cout<<"Массив для сортировки:"<<" ";
        cout<<endl;
   
        for (i=0;i<n;i++)
   { 
       a[i]= -100 + rand() % 301;
        cout<<a[i]<<" ";
   }
   cout<<endl;
   cout<<"Примечание: 1 - Cортировка пузырьком,\n";
    cout<<"            2 - Cортировка методом выбора,\n"; 
    cout<<"            3 - Быстрая сортировка.";
   cout<<endl;
   cout<<"Введите метод сортировки: ";
   cin >> m;
   switch(m)
   { case 1: BubbleSort(a, n); 
             cout << "Массив после сортировки <Пузырьком>: ";
              cout<<endl;
               for ( i = 0; i < n; i ++ )
               {
                cout << a[i] << " ";
                }
               cout<<endl;
               break;
     case 2: SelectSort( a, n );
           cout << "Массив после сортировки методом <Выбора>: ";
           cout<<endl;
             for ( i = 0; i < n; i ++ )
             {
                cout << a[i] << " ";
             }
             cout<<endl;
             break;
     case 3: QuickSort( a, n );
             cout << "Массив после <Быстрой сортировки>: ";
             cout<<endl;
               for ( i = 0; i < n; i ++ )
                {
                 cout << a[i] << " ";
                }
               cout<<endl;
               break;
    
   }
   system ("pause");
}
Добавлено через 54 секунды
metaluga145, объяснить вашу мысль насчёт col-1?
Она ошибочна...
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
13.05.2013, 19:56     Ошибка в быстрой сортировке #9
faLek, что за элемент arr[j] при j=col?
faLek
99 / 100 / 7
Регистрация: 06.03.2012
Сообщений: 478
13.05.2013, 21:58     Ошибка в быстрой сортировке #10
Вот здесь при вызове функции:
C++
1
QuickSort( a, n );
передаётся аргумент переменной col
C++
1
void QuickSort(int *arr, int col)
а та в свою очередь передаёт своё значение переменной j...

Добавлено через 4 минуты
ну а arr[j],чтобы проходить с конца массива,вы прочтите про быструю сортировку :
http://algolist.manual.ru/sort/quick_sort.php - здесь и реализация и алгоритм;
http://cybern.ru/qsort.html - только алгоритм (подробный);
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
13.05.2013, 23:10     Ошибка в быстрой сортировке #11
faLek, да я то читал. только вот в функцию в данном примере передается количество элементов массива, а обращение к элементу arr[n] не корректно.
faLek
99 / 100 / 7
Регистрация: 06.03.2012
Сообщений: 478
13.05.2013, 23:22     Ошибка в быстрой сортировке #12
metaluga145, в каком случае именно?
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
13.05.2013, 23:42     Ошибка в быстрой сортировке #13
faLek, да во всех! во всех местах, где вызывается функция быстрой сортировки она вызывается с параметрами массив и размер массива!

Добавлено через 17 минут
А ошибка была в том, что если сверятся с Википедией, то передавать в строке 65 надо не j, а j+1.

Добавлено через 1 минуту

Не по теме:

Цитата Сообщение от faLek Посмотреть сообщение
metaluga145, объяснить вашу мысль насчёт col-1?
Она ошибочна...
Прежде,чем объяснять другим их мысли, прочитайте внимательно код

faLek
99 / 100 / 7
Регистрация: 06.03.2012
Сообщений: 478
14.05.2013, 00:06     Ошибка в быстрой сортировке #14
metaluga145, ну хорошо,так написано в википедии,а вы докажите на чём вы основываете своё утверждение...
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
14.05.2013, 00:07     Ошибка в быстрой сортировке #15
faLek, возьмите и скомпилируйте!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2013, 00:13     Ошибка в быстрой сортировке
Еще ссылки по теме:

Как подсчитать произведенное количество перестановок при быстрой сортировке? C++
Количество произведенных сравнений в Быстрой Сортировке C++
C++ Переставить в быстрой сортировке вывод результата так чтобы он выполнялся один раз

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

Или воспользуйтесь поиском по форуму:
faLek
99 / 100 / 7
Регистрация: 06.03.2012
Сообщений: 478
14.05.2013, 00:13     Ошибка в быстрой сортировке #16
компилировал и всё в порядке компилируется
Yandex
Объявления
14.05.2013, 00:13     Ошибка в быстрой сортировке
Ответ Создать тему
Опции темы

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