Insert sort
Ostatnio zmodyfikowano 2013-06-23 16:22
kris Temat założony przez niniejszego użytkownika |
Insert sort » 2013-06-23 15:29:30 Witam.Ostatnio wypożyczyłem taką książkę jak Cormen i postanowiłem przerobić z niej wszystkie pseudokody.Przerobiłem już wszystkie sortowania, ale niestety przy sortowaniu insert sort napotkałem na problem którego nie jestem za bardzo wstanie wyjaśnić skąd się bierze.Oto kod który powinien najpierw sortować malejąco poprzez scalanie a następnie rosnąco poprzez wstawianie: #include <cmath> #include <iostream> #include <iomanip> #include <cstdlib> #include <time.h>
using namespace std;
const int N = 20;
int d[ N ], p[ N ];
void MergeSort( int i_p, int i_k ) { int i_s, i1, i2, i; i_s =( i_p + i_k + 1 ) / 2; if( i_s - i_p > 1 ) MergeSort( i_p, i_s - 1 ); if( i_k - i_s > 0 ) MergeSort( i_s, i_k ); i1 = i_p; i2 = i_s; for( i = i_p; i <= i_k; i++ ) p[ i ] =(( i1 == i_s ) ||(( i2 <= i_k ) &&( d[ i1 ] < d[ i2 ] ) ) ) ? d[ i2++ ] : d[ i1++ ]; for( i = i_p; i <= i_k; i++ ) d[ i ] = p[ i ]; } void insert() { cout << endl; cout << "insert sort rosnaco" << endl; int x; int n = N; for( int j = 2; j <= n; j++ ) { x = d[ j ]; int i = j - 1; while( i >= 0 && d[ i ] > x ) { d[ i + 1 ] = d[ i ]; i = i - 1; } d[ i + 1 ] = x; } for( int i = 0; i < N; i++ ) cout << setw( 4 ) << d[ i ]; cout << endl; }
int main() { int i; cout << " Sortowanie przez scalanie\n"; srand(( unsigned ) time( NULL ) ); for( i = 0; i < N; i++ ) d[ i ] = rand() % 100; for( i = 0; i < N; i++ ) cout << setw( 4 ) << d[ i ]; cout << endl; MergeSort( 0, N - 1 ); cout << "Po sortowaniu:\n\n"; for( i = 0; i < N; i++ ) cout << setw( 4 ) << d[ i ]; cout << endl; insert(); system( "pause" ); return 0; } Niestety, pierwszy kod działa bez zarzutu, jednak drugi ciągle gubi 2 lub 3 liczbę od końca i wstawia zamiast niej 0 na sam początek.Ktoś ma jakiś pomysł bo już próbowałem zmieniać numerowanie tablicy i dalej to samo.Za pomoc z góry dziękuje. |
|
DejaVu |
» 2013-06-23 16:22:00 Coremen wszystkie algorytmy omawia tak, jakby tablica była indeksowana od 1. To z kolei generuje problemy przy ich przepisywaniu na C++ wtedy, gdy pojawiają się operacje dzielenia/modulo, bowiem 1%2 to nie to samo co 0%2. |
|
« 1 » |