30/09/2018, 18:31
Giúp đỡ về quicksort trong <vector>string
Mọi người ơi, em code như thế này mò mãi sao chả ra được lỗi, sau khi chạy quicksort mảng vẫn giữ nguyên như cũ, mọi người giúp em với
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void Hoanvi (string *a, string *b);
void quickSort(vector<string> a, int low, int high);
int partition (vector<string> a, int low, int high);
int compare( string s1, string s2);
// void quickSort( vector<string> &a, int low, int high)
void main()
{
//Khai bao bien
fstream f;
vector <string> danhsach;
// Xu ly file: string str(a) bien a thanh string
//Input
f.open("Input.txt",ios::in);
int count = 0;
f >> count;
danhsach.resize(count);
string tam;
getline(f,tam);
for (int i = 0; i < count; i++)
{
getline(f,danhsach[i]);a
}
f.close();
// Xu ly mang:
quickSort(danhsach,0,count-1);
//Output
fstream o;
o.open("Output.txt",ios::out);
for (int i = 0; i < count; i++)
o << danhsach[i] << endl;
o.close();
}
void quickSort(vector<string> a, int low, int high)
{
if (low < high)
{
int p = partition(a,low,high);
quickSort (a, low, p-1);
quickSort (a,p+1,high);
}
}
void Hoanvi (string *a, string *b)
{
string tam = *a;
*a = *b;
*b = tam;
}
int partition (vector<string> a, int low, int high)
{
string pivot = a[(low+high)/2]; // thay int = string
int i = low;
int j = high;
while (i < j )
{
//// s1 < s2 ==> <0
//// s1 > s2 ==> >0
//// s1 = s2 ==> 0
//while (compare(a[i],pivot) < 0 )
// i++;
//while (compare(a[j],pivot) > 0 )
// j-- ; // chinh sua
//if ( i < j )
//{
// Hoanvi(&(string)a[i],&(string)a[j]);
// //a[i].swap(a[j]);
// /*cout << "Truoc khi xep:
";
// cout << "
a[i]: " << a[i] << endl;
// cout << "
a[j]: " << a[j] << endl;
// swap((a[i]),(a[j]));
// cout << "Sau khi xep:
";
// cout << "
a[i]: " << a[i] << endl;
// cout << "
a[j]: " << a[j] << endl;*/
// i++;
// j--;
//}
while (compare(a[i],pivot) > 0 )
i++;
while (compare(a[j],pivot) < 0)
j--;
if ( i < j)
{
Hoanvi(&a[i],&a[j]);
//a[i].swap(a[j]);
i++;
j--;
}
}
return j;
}
int compare( string s1, string s2)
{
char *t1;
t1 = &s1[0];
t1 = strlwr(t1);
char *t2;
t2 = &s2[0];
t2 = strlwr(t2);
char* t1_lwr = strlwr(t1);
char* t2_lwr = strlwr(t2);
return strcmp(t1_lwr,t2_lwr);
// s1 < s2 ==> <0
// s1 > s2 ==> >0
// s1 = s2 ==> 0
}
// char* t1 = strdup (s1.c_str()); chuyen thanh chu thuong: strlwn(t1)
Bài liên quan
Qsort(vector< string> &a…)
partition(vector< string> & a…)