Sắp xếp MẢNG, giải thuật sao cho đúng?

Steven_Luu · December 8, 2015, 1:22pm

THEO NHƯ THẢO LUẬN CỦA CÁC ANH, THUẬT TOÁN CỦA EM ĐÃ SAI, CÓ AI SỬA LẠI GIÚP EM ĐƯỢC KHÔNG Ạ? Chạy đúng với kiểu float luôn ạ
Dưới đây là một đoạn chương trình sắp xếp mảng kiểu integer, hãy chỉnh sửa lại kiểu dữ liệu sao cho sắp xếp được mảng kiểu thực
Nói trước, sửa int thành float, sửa %d thành %f là SAI liền nhé

`                #include <stdio.h>
                #include <stdlib.h>
                // nho nhat bi day ve truoc!!!
                void sortArray(int Array[], int sizeArray)
                {
                    // Giả sử có mảng n phần tử, vậy có TỐI ĐA (n - 1) lần hoán đổi.
                    int timeGlosby = -1;
                    do
                    {
                        timeGlosby = 0;
                        for (int i = 0; i < sizeArray; i++)
                        {
                            if (Array[i + 1] < Array[i])
                            {
                                // Ở đây chỉ hoán đổi không cần bận tâm :))
                                Array[i + 1] = Array[i + 1] + Array[i];
                                Array[i] = Array[i + 1] - Array[i];
                                Array[i + 1] = Array[i + 1] - Array[i];
                                timeGlosby++;
                            }
                        }
                    } while (timeGlosby != 0);
                }
                int main()
                {
                    unsigned char sizeArray = 5; // Luu y ngay day
                    int Array[] = {10,1,71,25,-1};
                    sortArray(Array, sizeArray);
                    for (int i = 0; i < sizeArray; i++) printf(" %d", Array[i]);
                    return 0;
                }

Itachi_Citus · December 8, 2015, 5:21am

Hình như bạn đang hỏi bài tập thì phải

#include <stdio.h>
#include <stdlib.h>
// nho nhat bi day ve truoc!!!
void sortArray(int Array[], int sizeArray)
{
    // Giả sử có mảng n phần tử, vậy có TỐI ĐA (n - 1) lần hoán đổi.
    int timeGlosby = -1;
    do
    {
        timeGlosby = 0;
        for (int i = 0; i < sizeArray; i++)
        {
            if (Array[i + 1] < Array[i])
            {
                // Ở đây chỉ hoán đổi không cần bận tâm :))
                Array[i + 1] = Array[i + 1] + Array[i];
                Array[i] = Array[i + 1] - Array[i];
                Array[i + 1] = Array[i + 1] - Array[i];
                timeGlosby++;
            }
        }
    } while (timeGlosby != 0);
}
int main()
{
    unsigned char sizeArray = 5; // Luu y ngay day
    int Array[] = {10,1,71,25,-1};
    sortArray(Array, sizeArray);
    for (int i = 0; i < sizeArray; i++) printf(" %d", Array[i]);
    return 0;
}

Cái này đâu ra vậy bạn .

Steven_Luu · December 8, 2015, 4:52am

Bạn có thể làm tốt một bài tập!

Nếu dãy BAN ĐẦU là một dãy giảm. Vậy bạn mất n - 1 lần hoán đổi. Bạn thử chưa?
Tuy nhiên code mình viết không liên quan gì đến // Giả sử có mảng n phần tử, vậy có TỐI ĐA (n - 1) lần hoán đổi.

qtd · December 8, 2015, 6:15am

Bạn sửa lại nội dung kèm markdown nhé
http://daynhauhoc.com/t/cach-post-code-dung-markdown-trong-category-programming/112

nguyenchiemminhvu · December 8, 2015, 10:30am

Nhìn thuật toán là thấy sai rồi chứ cần gì int hay float ở đây.

Chỉ cần xét cặp phần tử đầu tiên thỏa mãn điều kiện array[i + 1] < array[i] thì lập tức thoát luôn khỏi vòng do … while. Làm sao xét tiếp những phần tử ở sau được.

Itachi_Citus · December 8, 2015, 12:09pm

Nhầm nhé bạn , n-1 vòng lặp. Thuật toán bạn là bubble sort nên số lần hoán đổi tối đa là (n - 1)(n - 2)/2 (Gần gần cỡ đó, lười tính chính xác ra quá).

Thuật toán đúng với int bạn, sai với float là do nguyên nhân khác, khi đọc code đừng đọc mấy cái comment là thấy

//À nhầm int cũng sai, nhưng ko phải sai logic ở chỗ đó

qtd · December 8, 2015, 12:00pm

Mình chưa thử nhưng mình biết bạn sai =))

Steven_Luu · December 8, 2015, 1:13pm

[quote=“Itachi_Citus, post:6, topic:17714”]
Nếu dãy BAN ĐẦU là một dãy giảm. Vậy bạn mất n - 1 lần hoán đổi. Bạn thử chưa?
[/quote] Điều bạn nói là đúng nhưng:
Mình đã cho ban đầu là một dãy giảm mà bạn Dãy giảm tức là 54321 vậy bạn có 4 lần hoán đổi, đúng không nhỉ? Cái đó mình comment cho riêng mình hiểu Mình còn biết rằng có trường hợp khác không phải là n -1 lần hoán đổi.

Steven_Luu · December 8, 2015, 1:14pm

Vậy bạn cho mình một đoạn code đúng nhé! Mình rất mong muốn được học tập từ bạn

Steven_Luu · December 8, 2015, 1:19pm

Đó là lý do tại sao em dùng biến timeGlosby. Nếu số sau, không bé hơn số trước thì không có timeGlosby++ vậy thì do while của em sẽ đảm bảo dừng Nếu em sai thật, anh chỉ cặn kẽ giúp em nhé Em mong muốn học tập từ anh

Itachi_Citus · December 8, 2015, 2:54pm

Vẫn sai . Nó sẽ có 4 + 3 + 2 + 1 lần hoán đổi.

Code đó sai ở hai chỗ, thứ nhất là duyệt mảng quá số lượng phần tử, thứ hai sai ở đoạn code hoán đổi do độ chính xác của float.

Steven_Luu · December 9, 2015, 5:06am

Haha… Em hiểu rồi Cảm ơn anh nhiều lắm Anh có thể chỉ cho em viết lại code không anh? Trường hợp chạy float được luôn ấy

Steven_Luu · December 11, 2015, 12:48pm

Xin chào, em đã quay trở lại :)). Em cảm ơn các anh đã nhiệt tình chỉ bảo nhằm giúp em cải tiến code Tập số nguyên là con của tập số thực mà nhỉ :)) nên em có sử dụng %g (nếu bạn nào có thắc mắc thì “google” để rõ hơn về nó). Em xin đưa ra ý tưởng của bài này như sau:

#include <stdio.h>
#include <stdlib.h>
void insertArray(int Array[], int sizeArray)
{
	for (int i = 0; i < sizeArray; i++)
	{
	printf("\nArray[%d]: ", i); scanf(" %d",&Array[i]);
	}
}
void sortArray(int Array[], int sizeArray)
{
    for (int j = 1; j < sizeArray; j++)
    {
		// Source Sort
		for (int i = 1; i < sizeArray; i++)
		{
			if (Array[i] < Array[i - 1]) // KHONG TAP TRUNG
			{
                int cache = 0;
                cache = Array[i];
                Array[i] = Array[i - 1];
                Array[i - 1] = cache;
                //a = a + b //
				//b = a - b => a + b - b = a
				//a = a - b => a + b - a

			}
		}
    }
}
int main()
{
	int Array[100] = {0}, sizeArray = 0, valueMax = 27;
	printf("Insert size of array: "); scanf(" %d", &sizeArray);
	// Insert Array
	insertArray(Array, sizeArray);
	for (int i = 0; i < sizeArray; i++)
	{
	printf("\nArray[%d]: %d", i, Array[i]);
	}
	// Sorting...
	sortArray(Array, sizeArray);
	 for (int i = 0; i < sizeArray; i++)
	{
	printf("\nArray[%d]: %d", i, Array[i]);
	}
	return 0;
}

qtd · December 11, 2015, 1:39pm

=))))))) Cái cậu “Bạn đã thử chưa” đây à?
Lần sau hỏi thì nói là hỏi. Cứ đánh đố các anh tìm lỗi sai.
Sort float hay sort int thì nó cũng như nhau cả thôi.

qtd · December 11, 2015, 1:39pm