trinitr0
@trinitr0
провинциальный админ

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

Пробую разобраться с одной из множества реализации 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


Как исправить?
  • Вопрос задан
  • 109 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@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 еще делаете и там и там?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
AGIMA Москва
от 150 000 до 250 000 ₽
СофтТелематика Москва
от 200 000 до 250 000 ₽
PitchMe Санкт-Петербург
от 250 000 ₽
18 сент. 2020, в 15:52
30000 руб./за проект
18 сент. 2020, в 15:47
60000 руб./за проект