Алгоритм моей быстрой сортировки


Я сделаю его более удобным для читателя после того, как я вам алгоритм завершен. Что-нибудь с быстрая сортировка алгоритм выделиться, а почему это не работает на 100%? Это не домашнее задание, я просто практикуюсь проблем из книг, и я поймал на этом.

Намеки, больше, чем ответов, было бы более высокую оценку. Пожалуйста, не публикуйте ваш собственный алгоритм быстрой сортировки, как копирование кого-то кода-то не помогает мне учиться. Я просто ищу, что последний бит, чтобы помочь мне сделать прыжок через; я не хочу, чтобы вы построить еще один мост где-то еще и сказать: "Возьми мой"; это не поможет. Если мой алгоритм-это гиблое дело так и скажи, и я буду вернуться к чертежной доске.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <ctime>
#include <assert.h>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::ostream_iterator;
using std::istream_iterator;

void print_part( vector<float>::iterator l,
                 vector<float>::iterator r ) {
    copy( l,r+1,ostream_iterator<float>( cout," " ) );
    cout << endl;
}

void print( std::vector<float> &data ) {
    copy( data.begin( ), data.end( ), 
          ostream_iterator<float>( cout," " ) );
    cout << endl;
}

void swap( vector<float>::iterator left,
           vector<float>::iterator right ) {
    cout << "Swaping " << (*left) << " with " << (*right) << endl;
    float tmp = (*right);
    (*right) = (*left);
    (*left) = tmp;
}

int get_pivot_index( vector<float> &data,
                     vector<float>::iterator left,
                     vector<float>::iterator right ) {
    int pivot_index = ((right-left)/2);
    int base = std::distance( data.begin( ),left );
    return ( pivot_index+=base );

}

void my_qsort( vector<float> &data, 
               vector<float>::iterator left,
               vector<float>::iterator right,
               int side
             ) {
     ((side==0) ? cout<<"":(side==1) ? cout<<"Left: " : cout<<"Right: " );
     print_part( left,right );
     if( (right-left)>0) {
         vector<float>::iterator lit=left;
         vector<float>::iterator rit=right;
         int pivot_index = get_pivot_index( data,left,right );
         int pivot=data[pivot_index];
         cout << "pivot = " << pivot << endl;
         while( lit <= right && rit > left && lit <= rit ) { 
             while( lit <= right && (*lit) < pivot ) {
                 if( lit > rit ) { break; }
                 else { lit++; }
             }
             while( rit > left && (*rit) >= pivot ) { 
                 if( lit > rit ) { break; }
                 else { rit--; }
            }
            if( lit < rit ) { swap( lit,rit ); }
        }
        my_qsort( data,left,rit,1 );
        my_qsort( data,lit+1,right,2 );
    }
    char c;
    cin >> c;
}

int main( int argc, char *argv[ ] ) {
    vector<float> 
    data( 
          ( istream_iterator<float>( cin ) ),
          ( istream_iterator<float>( ) )
        );
    cout << "-----------------------------------------------" << endl;
    my_qsort( data,data.begin( ),data.end( )-1,0 );
    cout << "-----------------------------------------------" << endl;
    print( data );
    return ( 0 );
}


763
3
задан 2 августа 2011 в 09:08 Источник Поделиться
Комментарии
3 ответа


  1. Я спрашиваю себя - "что есть инварианты?" и использовать утверждения, чтобы убедиться, что инварианты хороший код. В данном случае, my_qsort должна возвращать отсортированный диапазон.

  2. Я постараюсь найти самый простой, не например, понять, что происходит.

5
ответ дан 2 августа 2011 в 08:08 Источник Поделиться

У меня есть пара предложений.


  1. Не ждите, пока вы закончите, чтобы сделать ваш код читателя дружелюбный. Это плохая привычка развиваться из-за таких ситуаций, как сейчас. Вы хотели бы кого-нибудь посмотреть на ваш код, но это не так легко читать, как это должно быть, так трудно получить помощь, в которой вы хотели бы. Кроме того, как только вы начинаете кодирования для гостиной будет давление, чтобы не "тратить время" убирать то, что уже работает.

  2. Вы не указали, как вы знаете, у вас есть проблема. Это работает на некоторые наборы данных, а не другие? Если да, то в чем различие между наборами данных? Если вы тестируете с большими наборами данных, вы можете иметь трудное время, видя основное различие. Начните тестирование с очень небольших наборов данных: 1, затем 2, затем 3 элементов (с использованием всех перестановок порядка старта). Для небольших наборов данных может быть прорисована вручную.

4
ответ дан 2 августа 2011 в 07:08 Источник Поделиться

Ошибка кроется в левую рода. Когда 1-я величина больше 2-ой ценим ваш сортировка не работает. Поэтому остановимся на этой части вашего кода. Как правило, такого рода проблемы очень малы и легко исправить, но трудно определить :-)

Также было бы интересно посмотреть, как вы сортируете 4 и 5 символов, которые тасуются так, как он хотел бы подчеркнуть левой стороны вопрос вроде :-)

Если вам нужна более конкретная помощь, то дайте мне знать

1
ответ дан 30 мая 2013 в 04:05 Источник Поделиться