Hỏi Về Thuật toán sắp xếp Insertion Sort trong mảng chuỗi

Chaylok_C_u · March 10, 2015, 1:58pm

làm sao để sắp sếp Tên bằng Insertion Sort trong mảng chuỗi.
không chỉ sắp xếp chữ cái đầu tiên mà còn sắp sếp các ký tự tiếp theo : “khai”,khac",“anh”,"tin"sau khi sắp xếp : “anh”,“khac”,“khai”,“tin”.

nguyenchiemminhvu · March 10, 2015, 9:10am

Bạn dùng hàm strcmp trong thư viện string.h để so sánh 2 từ theo thứ tự từ điển.

strcmp(): http://www.cplusplus.com/reference/cstring/strcmp/
Thứ tự từ điển được định nghĩa như thế nào? http://diendan.congdongcviet.com/archive/index.php/t-29806.html

Theo đó thì “a” < “an” < “anh” …
và “ab” < “ac” < “amnop” …

Sau khi có phép so sánh rồi thì bạn sắp xếp y như sắp xếp kiểu integer vậy.

Chaylok_C_u · March 10, 2015, 9:43am

sao mình làm như bạn nhưng nó báo lỗi ở khi sắp xếp chèn trực tiếp

nguyenchiemminhvu · March 10, 2015, 10:00am

Cho mọi người xem code của bạn đi

Chaylok_C_u · March 10, 2015, 1:58pm

Đây bạn coi giúp mình

Insertions Sort

void ShakerSort(char TiengAnh[10][50], int n);
void InputArray(char TiengAnh[10][50],int &n)
{
	printf("Nhap n: ");
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
	{
		fflush(stdin);
		printf("Cac Phan tu trong mang a[%d]=  ",i);
		gets(TiengAnh[i]);
	}
}
void OutputArray(char TiengAnh[10][50], int n)
{
	printf("Danh Sach Các Tu Tieng Anh: \n");
	for(int i = 0; i < n; i++)
		printf("%s\n",TiengAnh[i]);
}
void main()
{
	char TiengAnh[10][50];
	int n;
	InputArray(TiengAnh, n);
	OutputArray(TiengAnh, n);

	printf("\nInterchangeSort:  ");
	InterchangeSort(TiengAnh, n);
	OutputArray(TiengAnh, n);

	printf("SelectionSort: ");
	InterchangeSort(TiengAnh, n);
	OutputArray(TiengAnh, n);

	printf("BubbleSort: ");
	BubbleSort(TiengAnh, n);
	OutputArray(TiengAnh, n);

	printf("ShakerSort: ");
	ShakerSort(TiengAnh, n);
	OutputArray(TiengAnh, n);
	getch();
}
void Swap(char a[], char b[])
{
	char Temp[30];
	strcpy(Temp, a);
	strcpy(a, b);
	strcpy(b, Temp);

}
int KiemTraTuDien(char a[], char b[])
{
	if(strcmp(a, b) < 0)
		return 1;
	return 0;

}
void ShakerSort(char TiengAnh[10][50], int n)
{
	int j;
	int left, right, k;
	left = 0; right = n - 1; k = n - 1;
	while (left < right)
	{
		for (j = right; j > left; j --)
			if (KiemTraTuDien(TiengAnh[j], TiengAnh[j-1]))
			{
				Swap(TiengAnh[j], TiengAnh[j-1]);
				k =j;
			}
		left = k;
		for (j = left; j < right; j ++)
			if (TiengAnh[j]> TiengAnh[j+1])
			{
				Swap(TiengAnh[j], TiengAnh[j-1]);
				k = j; 
			}
		right = k;
	}
}
void InsertionSort(char TiengAnh[10][50], int n)
{
	int  pos;
	char x[30];
	for(int i = 1; i < n; i++)
	{
		x = TiengAnh[i];
		pos = i - 1;
		while(pos >= 0 && x < TiengAnh[pos])
		{
			TiengAnh[pos +1] = TiengAnh[pos--];
		}
		TiengAnh[pos + 1] = x;
	}
}