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

13.05.2013, 16:43. **Показов** 1034. **Ответов** 15

Author24 — интернет-сервис помощи студентам

Мне нужно сравнить как минимум три сортировки массива. Т.к. плохо знаю С++ нашла шаблоны.
И вот все на что я способна:

C++

#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;
    
   }
}

Сортировка методом пузырька и посредством выбора работают, но при вызове быстрой сортировке возникает ошибка:

Что делать?='(

@metaluga145 · 13.05.2013, 16:59

Не по теме:

Сообщение от 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()

13.05.2013, 17:30

Спасибо большое, теперь никакой ошибки )

З.Ы. и вешаться передумала

просто спасли меня)

@faLek · 13.05.2013, 18:25

C++

1	быстрая сортировка некорректно сортирует..

@metaluga145 · 13.05.2013, 18:35

faLek, странно, потому что эта сортировка с Википедии

@faLek · 13.05.2013, 19:21

ну вы проверьте как она у вас сортирует...

@metaluga145 · 13.05.2013, 19:29

faLek, плохо сортирует

@faLek · 13.05.2013, 19:45

metaluga145, а если плохо,значит не сортирует

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

C++

#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 · 13.05.2013, 19:56

faLek, что за элемент arr[j] при j=col?

@faLek · 13.05.2013, 21:58

Вот здесь при вызове функции:

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 · 13.05.2013, 23:10

faLek, да я то читал. только вот в функцию в данном примере передается количество элементов массива, а обращение к элементу arr[n] не корректно.

@faLek · 13.05.2013, 23:22

metaluga145, в каком случае именно?

@metaluga145 · 13.05.2013, 23:42

faLek, да во всех! во всех местах, где вызывается функция быстрой сортировки она вызывается с параметрами массив и размер массива!

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

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

Не по теме:

Сообщение от faLek

metaluga145, объяснить вашу мысль насчёт col-1?
Она ошибочна...

Прежде,чем объяснять другим их мысли, прочитайте внимательно код

@faLek · 14.05.2013, 00:06

metaluga145, ну хорошо,так написано в википедии,а вы докажите на чём вы основываете своё утверждение...

@metaluga145 · 14.05.2013, 00:07

faLek, возьмите и скомпилируйте!

@faLek · 14.05.2013, 00:13

компилировал и всё в порядке компилируется

@metaluga145 244 / 245 / 38 Регистрация: 08.04.2013 Сообщений: 927
	13.05.2013, 23:10	11
	faLek, да я то читал. только вот в функцию в данном примере передается количество элементов массива, а обращение к элементу arr[n] не корректно. 0

@faLek 101 / 102 / 43 Регистрация: 06.03.2012 Сообщений: 478
	13.05.2013, 23:22	12
	metaluga145, в каком случае именно? 0

MisS_Rediska
	13.05.2013, 17:30	3
	Спасибо большое, теперь никакой ошибки ) З.Ы. и вешаться передумала просто спасли меня)

@metaluga145 244 / 245 / 38 Регистрация: 08.04.2013 Сообщений: 927
	13.05.2013, 18:35	5
	faLek, странно, потому что эта сортировка с Википедии 0

@faLek 101 / 102 / 43 Регистрация: 06.03.2012 Сообщений: 478
	13.05.2013, 19:21	6
	ну вы проверьте как она у вас сортирует... 0

@metaluga145 244 / 245 / 38 Регистрация: 08.04.2013 Сообщений: 927
	13.05.2013, 19:29	7
	faLek, плохо сортирует 0

@metaluga145 244 / 245 / 38 Регистрация: 08.04.2013 Сообщений: 927
	13.05.2013, 19:56	9
	faLek, что за элемент arr[j] при j=col? 0

@metaluga145 244 / 245 / 38 Регистрация: 08.04.2013 Сообщений: 927
	13.05.2013, 23:42	13
	faLek, да во всех! во всех местах, где вызывается функция быстрой сортировки она вызывается с параметрами массив и размер массива! Добавлено через 17 минут А ошибка была в том, что если сверятся с Википедией, то передавать в строке 65 надо не j, а j+1. Добавлено через 1 минуту Не по теме: Сообщение от faLek metaluga145, объяснить вашу мысль насчёт col-1? Она ошибочна... Прежде,чем объяснять другим их мысли, прочитайте внимательно код 0

@faLek 101 / 102 / 43 Регистрация: 06.03.2012 Сообщений: 478
	14.05.2013, 00:06	14
	metaluga145, ну хорошо,так написано в википедии,а вы докажите на чём вы основываете своё утверждение... 0

@metaluga145 244 / 245 / 38 Регистрация: 08.04.2013 Сообщений: 927
	14.05.2013, 00:07	15
	faLek, возьмите и скомпилируйте! 0

@faLek 101 / 102 / 43 Регистрация: 06.03.2012 Сообщений: 478
	14.05.2013, 00:13	16
	компилировал и всё в порядке компилируется 0