Быстрая сортировка

[Syltan]

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

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

[netrino]

while((items[i] < x) && (i < right)); i++;
while((x < items[j]) && (j > left)); j--;

У вас тут вайлы не выполняют никаких операций из-за точки с запятой сразу после них) потому выходит бесконечный цикл.

while((items[i] < x) && (i < right)) i++;
while((x < items[j]) && (j > left)) j--;

стоит сделать так и всё правильно сортирует

[Syltan]

Спасибо за ответ netrino. Как мне например отсортировать 200 чисел случайных, которые выходят случайным образом и ещё ей же отсортировать буквы(200 штук случайных). Буду благодарен, за ответ. Прочитал,что ещё можно использовать какой-то template<class T>,не в курсе что это такое,какие-то вроде шаблоны,что-то они там делают. Вот код нашёл:

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

Не скажите,как реализовать задачу выше выделенную синим цветом?

[netrino]

Шаблоны созданы для обобщений алгоритма на разные типы данных, на этапе компиляции они раскрываются и создаются необходимые виды ф-ций, оперирующие темы или иными видами данных, которые указываются в качестве параметра при использовании. Пример:

template<class T>
T max(T left, T right)
{
    return (left > right)? left : right;
}
...
max<int>(10, 15); // Вместо T подставляется int
max<char>('a', 'd'); // Вместо T подставляется char

При компиляции будет создано два варианта ф-ции max, один, который принимает в качестве параметров int, второй - char. В случаях, где можно однозначно определить какую ф-цию из шаблона следует создать, исходя из типов параметров, можно опустить <>: max(10, 10); max('a', 'd');
Так что ф-ция, которую вы привели в последнем посте рабочая

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

[colored]

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

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

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

Из Шилдта пример? Я тоже его книгу читаю.

[Syltan]

Если кто может,дополните коментарием вот этот,код,желательно как можно больше:

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

[LaptevVV]

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

Если кто может,дополните коментарием вот этот,код,желательно как можно больше:

#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 ];                // не понятно
это сдвиг вправо на 1. Если N положительное и беззнаковое, то деление на 2 
 
  // процедура разделения
  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 );
 
  // рекурсивные вызовы, если есть, что сортировать 
[b] это рекурсивный вызов той же функции с левой и правой половиной исходного массива
  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;
}

Резюме. Читайте литературу!
По вопросам явно видно, что ни одной книжки по С++ вы не открывали.

[Syltan]

Если кто может, ответьте пожалуйста на 6 пост,очень нужно разобраться с сортировкой. Благодарю.