Модераторы: JackYF, bsa
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Реализация быстрой сортировки 
:(
    Опции темы
trinitr0
Дата 11.8.2020, 11:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 102
Регистрация: 25.6.2013

Репутация: нет
Всего: нет



Помогите пожалуйста с реализацией алгоритма быстрой сортировки.
Такая реялизация сортирует только первые несколько элементов, где ошибка?

Код

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

PM MAIL Jabber   Вверх
trinitr0
  Дата 13.8.2020, 22:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 102
Регистрация: 25.6.2013

Репутация: нет
Всего: нет



Немного поправил:

Код

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


не не помогло. Где же тут ошибки?
PM MAIL Jabber   Вверх
Oldshelf
Дата 14.8.2020, 14:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 44
Регистрация: 22.4.2018

Репутация: нет
Всего: 3



Не уверен насчёт достаточно "быстрой", но компактно и работает:

Код

#include <iostream>
#include <ctime>
#include <iomanip>
#include <windows.h>

using namespace std;
void swap(int* a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quicksort(int *arr_ptr, int size_arr){
    int i, i2, till=size_arr-1;

    for (i2=0; i2<till; i2++)
    {
        for (i=0; i<till; i++)
        {
            if (arr_ptr[i] > arr_ptr[i+1]){
                swap(arr_ptr[i],arr_ptr[i+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;

    system ("pause");
    return 0;
}


Это сообщение отредактировал(а) Oldshelf - 14.8.2020, 14:32
PM MAIL WWW   Вверх
trinitr0
Дата 14.8.2020, 15:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 102
Регистрация: 25.6.2013

Репутация: нет
Всего: нет



Спасибо за помощь! 
Но мне бы разобраться в варианте с опорным элеметом и двумя рекурсиями.
PM MAIL Jabber   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »


 




[ Время генерации скрипта: 0.1187 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.