Почему неправильно работает такая реализация алгоритма быстрой сортировки?

Question

[ReD]

Пробую разобраться с одной из множества реализации qsort, но она сортирует как-то странно:

#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;
void swap(int* a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void part(int *arr_ptr, int size_arr, int m){
    if (m != 0){
        swap (arr_ptr[0],arr_ptr[m]);
    }
    int x = arr_ptr[0];
    int i=0;
    int j=size_arr;
    while(j-i>1){
        bool change = false;
        if(arr_ptr[i+1] <=x){
            ++i;
            change = true;
        }
        if(j-1>i && arr_ptr[j-1] >= x){
            --j;
            change = true;
        }
        if(!change){
            ++i;
            --j;
            swap(arr_ptr[i], arr_ptr[j]);
        }
    }
    if(i > 0){
            swap(arr_ptr[0], arr_ptr[i]);    
    }
    m = i;
}
void quicksort(int *arr_ptr, int size_arr){
    if(size_arr <= 1){
        return;
    } else if (size_arr == 2){
        if (arr_ptr[0] > arr_ptr[1]){
            swap(arr_ptr[0],arr_ptr[1]);
        }
    return;    
    }
    int beg=0;
    int k = size_arr;
    while(k>1){
        int m = k/2; //mediana
        part(arr_ptr + beg, k, m);
            int left = m;
            int right = k-1-left;
            if(left <= right){
                quicksort(arr_ptr+beg, left);
                beg +=  left+1; 
                k   -=  left+1; 
            } else {
                quicksort(arr_ptr+beg+m+1, right);
                k -= right+1;
            }
        
    } 
} 
int main()
{
    int size_arr = 10;
    srand(static_cast<unsigned int>(time(NULL)));
    int *sort_arr = new int [size_arr];
    
    int line=0;
    for (int i = 0; i < size_arr; ++i)
    {
        line++;
        sort_arr[i] = rand()%100;
        cout << setw(3) << sort_arr[i] << " ";
        if(line%5 == 0){
            cout << "\n";
        }
    }
    cout << "\n";
    quicksort(sort_arr, size_arr);
    for (int i = 0; i < size_arr; ++i)
    {
        line++;
        cout << setw(3) << sort_arr[i] << " ";
        if(line%5 == 0){
            cout << "\n";
        }
    }
    cout << "\n";
    delete [] sort_arr;
}

Вывод:

33 23 61 14 11
14 65 23 69 60

14 23 11 14 61
33 23 60 65 69

Как исправить?

Answer 1

[Wataru]

тут много проблем.

1) не надо в конце part менять местами 0-ой и i-ый элементы. Это бессмысленно. Вы поддерживаете вариант, что элементы с 0 по i-ый <=x, c j-ого и дальше >=x

2) У вас у part() параметр m передается по значению. Изменение его в конце функции не видно из места вызова. Вы каждый раз, независимо от того, как разбиение произошло, рекурсивно запускаетесь половин массива разделенных ровно по середине.

3) Что у вас с рекурсивными вызовами твориться? Вы хвостовую рекурсию руками схлопнули что ли? А зачем выбирать, с какой стороны рекурсивно вызваться, а с какую дальше в цикле обрабатывать? Там у вас что-то с вычислениями напутанно, всякие +-1 неверно распиханы. Вы там делаете k -= left+1 и k -= right+1. По логике в одной половине left элементов, в другой - right. Тогда почему вы -1 еще делаете и там и там?

Comments

[ReD]

Попробовал перепись так:

#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;

void swap(int* a, int *b){
	int temp = *a;
	*a = *b;
	*b = temp;
}

void part(int *arr_ptr, int size_arr, int *m){
	if (*m != 0){
		swap (arr_ptr[0],arr_ptr[*m]);
	}

	int x = arr_ptr[0];

	int i=0;
	int j=size_arr;

	while(j-i>1){
		bool change = false;

		if(arr_ptr[i+2] <=x){
			++i;
			change = true;
		}
		if(j-1>i && arr_ptr[j-1] >= x){
			--j;
			change = true;
		}
		if(!change){
			++i;
			--j;
			swap(arr_ptr[i], arr_ptr[j]);
		}
	}
	if(i > 0){
			swap(arr_ptr[0], arr_ptr[i]);	
	}
	*m = i;
}

void quicksort(int *arr_ptr, int size_arr){
	if(size_arr == 1){
		return;
	} else if (size_arr == 2){
		if (arr_ptr[0] > arr_ptr[1]){
			swap(arr_ptr[0],arr_ptr[1]);
		}

	return;	
	}

	int beg=0;
	int k = size_arr;

	//while(k>1){
		int m = k/2; //mediana

		part(arr_ptr + beg, k, &m);

			int left = m;
			int right = k-1-left;

			if(left <= right){
				quicksort(arr_ptr+beg, left);
				beg++; //+=  left; 
				k--;   //-=  left; 
			} else {
				quicksort(arr_ptr+beg+m+1, right);
			 	k--; //-= right+1;
			}
		
	//} 
} 


int main()
{
	int size_arr = 10;
	srand(static_cast<unsigned int>(time(NULL)));

	int *sort_arr = new int [size_arr];
	
	
	int k=0;
	for (int i = 0; i < size_arr; ++i)
	{
		k++;
		sort_arr[i] = rand()%100;
		cout << setw(3) << sort_arr[i] << " ";

		if(k%5 == 0){
			cout << "\n";
		}
	}
	cout << "\n";

	quicksort(sort_arr, size_arr);

	for (int i = 0; i < size_arr; ++i)
	{
		k++;
		cout << setw(3) << sort_arr[i] << " ";

		if(k%5 == 0){
			cout << "\n";
		}
	}
	cout << "\n";

	delete [] sort_arr;

	return 0;
}

не помогло

[Wataru]

Потому что фигню сделали в quicksort(). Мало цикл закомментировать, надо всегда делать 2 рекурсивных вызова. А у вас один будет - в какой-то ветке if-else. Сравните с этим кодом.

[AnT]

wataru, Ни в коем случае!!!

При реализации быстрой сортировки на практике обязательно один из вызовов вручную заменяется на "циклический" вызов и только второй делается рекурсивным. Ни о каких "2 рекурсивных вызова" не может быть и речи.

• Если вы используете явную языковую рекурсию, то рекурсивный вызов делается первым, обязательно для более короткой половины массива, а затем выполняется "итеративный вызов" для обработки более длинной половины массива.
  
  
• Если вы используете "ручную рекурсию" (то есть явный стек), то наоборот, в стек заносится более длинная половина массива (для обработки "потом"), а "сейчас" выполняется циклический вызов алгоритма для обработки более короткой половины.
  

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

Это критически важное ключевое соображение, которое гарантирует вам, что глубина рекурсии во время сортировки всего массива не превысит log2(N) даже в самом худшем случае. Если вы проигнорируете эти соображения, то глубина рекурсии в худшем случае может достичь N, что совершенно не приемлемо на практике.

[Wataru]

AnT, Когда у вас глубина рекурсии достигает ~N в неоптимизированной реализации, то у вас сортировка, даже с вашей оптимизацией, будет работать за O(N^2). Если N такое большое, что O(N) памяти в стеке страшно завести, то вам в любом случае уже сильно поплохеет. Даже без оптимизации рекурсии.

А, раз человек не может разобраться с кодом, оптимизации можно для начала и исключить.

[AnT]

wataru, Это не относится к оптимизации (скорости сортировки) вообще. Это лишь вопрос грамотной реализации. Это на самом деле совсем не глубоко спрятанное соображение, которое позволит алгоритму завершиться на любых входных данных вместо того, чтобы упасть по переполнению стека рекурсии при неудачном выборе медианы.

Грамотно реализованный quicksort не выходит за пределы log2(N) стека, независимо от того, насколько хорошо сбалансировано разделение элементов массива (partitioning). То есть, например, можно гарантировать, что на 32-битной платформе всегда хватит стека глубины 32. Любая реальная практическая (не учебная студенческая) реализация quicksort всегда принимает во внимание это соображение.

[ReD]

Господа, ваш диспут читать интересно. Он прояснил некоторые мои догадки. Спасибо вам за содействие! Но я пока не обладаю достаточным опытом и знаниями чтобы найти все ошибки самостоятельно, поэтому буду рад помощи!