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
|
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int WORD_COUNT = 172820;
char *lines[WORD_COUNT];
int left_num, right_num;
void sort();
void quick_sort(char *lines[], int, int);
void insert_sort();
int main()
{
int i = 0;
ifstream fin("enable3.txt");
char line[100];
while(!fin.eof())
{
fin.getline(line, 100);
if(fin.good())
{
lines[i] = new char[strlen(line)+1];
strcpy(lines[i], line);
i++;
}
}
fin.close();
sort();
i = 0;
while(i < WORD_COUNT)
{
cout << lines[i] << endl;
i++;
}
return 0;
}
void sort()
{
quick_sort(lines, left_num, right_num);
// insert_sort();
}
void quick_sort(char *lines[], int l, int r)
{
int i = l, j = r;
char temp[100];
int m = (l + r) /2;
int pivot;
if (strcmp(lines[m],lines[i]) > 0 && strcmp(lines[j],lines[m]) > 0 && strcmp(lines[j], lines[i]) > 0)
{
pivot = m;
}
else if (strcmp(lines[m],lines[i]) > 0 && strcmp(lines[j],lines[m]) > 0 && strcmp(lines[j], lines[i]) > 0 )
{
pivot = i;
}
else
{
pivot = j;
}
while (i <= j)
{
while (strcmp(lines[i],lines[pivot]) > 0)
i++;
while(strcmp(lines[j], lines[pivot]) < 0)
j--;
if (i <=j)
{
strcpy(temp, lines[i]); //set i to temp
strcpy(lines[i], lines[j]); //have old j be set to i
strcpy(lines[j], temp); //have temp set to the new j
i++;//increment i
j--;//decrement j
}
}
cout << lines[pivot];
//recursion
if (l < j)
quick_sort(lines, l, j);
if (r < i)
quick_sort(lines, r, i);
}
void insert_sort()
{
int j;
char *temp;
for(int i=0 ; i < WORD_COUNT; i++) // count through the array
{
cout << "Using insertion sort to sort word number " << i << endl;
j = i; // set i to j
while(j > 0 && strcmp(lines[j], lines[j-1]) > 0)
{
strcpy(temp, lines[j]); // have the array j be set to temp
strcpy(lines[j], lines[j-1]);
strcpy(lines[j-1] , temp);
j--; // decrement j
}
}
}
|
