C++

Forum

 
Radix Sort Not working

Joshua Schweigert (48)
Hello,
I'm trying ultimately to do a radix sort. I'm going with the implementation using two tables. One will initially hold the unsorted values then hold the partially sorted values thereafter. The other will be an array of linked lists which will be where the radix sort is done. Here is my code thus far:

Main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <iostream>
#include <fstream>
#include "radix.h"
#include "radix.cpp"

using namespace std ;

int main ( int argc , char * argv [ ] ) {

    ifstream input ( argv [ 1 ] ) ;

    int temp_val = 0 ;
    int i = 0 , j = 0 ;

    radix * ro = new radix ( ) ;

// Populate the unsorted list from a file =====
    while ( input >> temp_val ) {

        ro->insert_into_unsorted ( temp_val ) ;
        temp_val ++ ;

    }
// =============================================

    ro->set_num_elements ( temp_val ) ;
    input.close ( ) ;

// Set the maximum possible place ===============================
    for ( i = 0 ; i < ro->get_unsorted_size ( ) ; i ++ ) {

        ro->set_max_place_value ( ro->get_unsorted_val ( i ) ) ;

    }
// ==============================================================

    temp_val = 0 ;

// What size to allocate the sorted array to ============================================
    for ( j = 0 ; j < ro->get_unsorted_size() ; j ++ ) {

        if ( ro->get_digit_place_value ( ( ro->get_unsorted_val(j) ) , 1 ) > temp_val ) {

            temp_val = ro->get_digit_place_value ( ( ro->get_unsorted_val(j) ) , 1 ) ;

        }

    }
// =======================================================================================

ro->create_new_sorted ( temp_val ) ;
ro->insert_into_sorted ( ro->get_unsorted_val ( 0 ) , 1 ) ;


}


radix source
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 
#include <iostream>
#include "radix.h"

using namespace std ;

radix::radix ( ) {

    unsorted_size  = 0 ;
    unsorted  = new int [ unsorted_size ] ;
    sorted_size = 0 ;
    sorted = new node * [ sorted_size ] ;
    max_place = 0 ;
}

void radix::print_unsorted_list ( ) {

    for ( int i = 0 ; i < unsorted_size ; i ++ ) {

        cout << unsorted [ i ] << " " ;

    }

}
void radix::print_sorted_list ( ) {

    for ( int i = 0 ; i < sorted_size ; i ++ ) {

        cout << sorted [ i ] << " " ;

    }

}

void radix::set_unsorted_size ( int new_val ) {

    unsorted_size = new_val ;

}

void radix::set_sorted_size ( int new_val ) {

    sorted_size = new_val ;

}

int radix::get_unsorted_size ( ) {

    return unsorted_size ;

}

int radix::get_sorted_size ( ) {

    return sorted_size ;

}

int radix::get_new_sorted_size ( int place ) {

    int temp = 0 ;

    for ( int i = 0 ; i < unsorted_size ; i ++ ) {

        if ( get_digit_place_value ( unsorted [ i ] , place ) > temp ) {

            temp = unsorted [ i ] ;

        }

    }

    return temp ;

}
int radix::get_digit_place_value ( int digit , int place ) {

    int mod = digit%10 ;

        for ( int i = 0 ; i < place ; i ++ ) {

            mod = digit % 10 ;
            digit /= 10 ;

        }
    return mod ;
}
void radix::set_max_place_value ( int digit ) {

    if ( get_place_value ( digit ) > max_place ) {

        max_place = get_place_value ( digit ) ;

    }

}
int radix::get_place_value ( int digit ) {

    int count = 0 ;

    while ( digit != 0 ) {

        digit /= 10 ;
        count ++ ;

    }

    return count ;

}

void radix::insert_into_unsorted ( int to_insert ) {

    if ( unsorted_size == 0 ) {

        ++ unsorted_size ;
        unsorted = new int [ unsorted_size ] ;
        unsorted [ unsorted_size - 1 ] = to_insert ;

    }

    else {

        int * holder = new int [ unsorted_size ] ;
        int i = 0 ;

        for ( i = 0 ; i < unsorted_size ; i ++ ) {

            holder [ i ] = unsorted [ i ] ;

        }

        unsorted = new int [ unsorted_size + 1 ] ;


        for ( i = 0 ; i < unsorted_size ; i ++ ) {

            unsorted [ i ] = holder [ i ] ;

        }

        ++ unsorted_size ;

        unsorted [ unsorted_size - 1 ] = to_insert ;

        delete [ ] holder ;
        holder = NULL ;

    }

}
void radix::insert_into_sorted ( int to_insert , int place ) {

    node * current = sorted [ get_digit_place_value ( to_insert , place ) , ] ;

    while ( current != NULL ) {

        current = current->next ;

    }

    current->num = to_insert ;

}

int radix::get_unsorted_val ( int index ) {

    return unsorted [ index ] ;

}

void radix::print_sorted_val ( int index ) {

    node * current = sorted [ index ] ;
    while ( current != NULL ) {

        cout << current->num << " " ;

    }

}

int radix::get_max_place ( ) {

    return max_place ;

}

void radix::set_num_elements ( int new_num ) {

    num_elements = new_num ;

}

int radix::get_num_elements ( ) {

    return num_elements ;

}

void radix::create_new_sorted ( int new_size ) {

    sorted_size = new_size ;
    sorted = new node * [ sorted_size ] ;
    zero_sorted_array() ;

}

void radix::back_in_unsorted ( ) {

    node * current ;

    int index = 0 ;

    for ( int i = 0 ; i < sorted_size ; i ++ ) {

        current = sorted [ i ] ;
        while ( current != NULL ) {

            unsorted [ index ] = current->num ;
            index ++ ;
            current = current->next;

        }

    }

}


radix header
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
#ifndef radix_h
#define radix_h

class radix {

private:

    struct node {

        int num ;
        node * next ;

    };

    int * unsorted ;
    int unsorted_size ;
    node ** sorted ;
    int sorted_size ;
    int max_place ;
    int num_elements;


public:

// Default constructor
    radix ( ) ;
// ===================

// Prints the unsorted list=======
    void print_unsorted_list ( ) ;
// ===============================

// Prints the sorted list ======
    void print_sorted_list ( ) ;
// =============================

// Sets the unsorted list size =============
    void set_unsorted_size ( int new_val ) ;
// =========================================

// Sets the sorted list size =============
    void set_sorted_size ( int new_val ) ;
// =======================================

// Gets the unsorted list size
    int get_unsorted_size ( ) ;
// ============================

// Gets the sorted list size
    int get_sorted_size ( ) ;
// ==========================

// Gets the new size of the array to store the values
    int get_new_sorted_size ( int place ) ;
// ==================================================

// Gets a value in the ones, tens... place of digit =======
    int get_digit_place_value ( int digit , int place ) ;
// ========================================================

// Gets the max place value
    int get_max_place ( ) ;
// ========================

// Sets the max place value ================
    void set_max_place_value ( int digit ) ;
// =========================================

// Gets the maximum place value of digit, such as ones, tens ...
    int get_place_value ( int digit ) ;
// =============================================================

// Inserts a number into the unsorted list ======
    void insert_into_unsorted ( int to_insert ) ;
// ==============================================

// Inserts a number into the sorted list ==================
    void insert_into_sorted ( int to_insert , int place ) ;
// ========================================================

// Gets the number at the index from the unsorted list
    int get_unsorted_val ( int index ) ;
// ===================================================

// Gets the node at the index from the sorted list
    void print_sorted_val ( int index ) ;
// ===============================================

// Sets the total number of elements from a file
    void set_num_elements ( int new_num ) ;
// =============================================

// Gets the total number of elements
    int get_num_elements ( ) ;
// =================================

// Creates a new sorted array ===============
    void create_new_sorted ( int new_size ) ;
// ==========================================

// Zeros out an array ==========
    void zero_sorted_array ( ) ;
// =============================

// Puts the contents of the sorted_array back into the unsorted array
    void back_in_unsorted ( ) ;
// ==================================================================

};

#endif // radix_h



It appears to be crashing during void insert_into_sorted ( int to_insert , int place ) ; and I'm not sure why.

Thanks for any help!
naraku9333 (2163)
1
2
3
4
5
6
7
8
9
10
11
12
13
 
void radix::insert_into_sorted ( int to_insert , int place ) {

    node * current = sorted [ get_digit_place_value ( to_insert , place ) , ] ;

    while ( current != NULL ) {

        current = current->next ;

    }

    current->num = to_insert ;//current is NULL

}
Joshua Schweigert (48)
naraku9333,

I changed that part to:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void radix::insert_into_sorted ( int to_insert , int place ) {

    node * current = sorted [ get_digit_place_value ( to_insert , place ) , ] ;

    while ( current != NULL ) {

        current = current->next ;

    }

    current = new node ;
     current->num = to_insert ;

}


I still cant get it to insert.
Topic archived. No new replies allowed.