thắc mắc Bài toán sắp xếp, làm thế nào cho hay?

rosario_1

Member
Cho 1 dãy số tự nhiên. Hãy sắp xếp theo thứ tự từ bé đến lớn theo số chữ số. Nếu số chữ số như nhau thì số đứng trước trong dãy ban đầu sẽ đứng trước.

Input: 1,2,9,134,12,1
Output: 1,2,9,1,12,134

Không khó nhưng làm thế nào để code cho hay đây?
 
Cho 1 dãy số tự nhiên. Hãy sắp xếp theo thứ tự từ bé đến lớn theo số chữ số. Nếu số chữ số như nhau thì số đứng trước trong dãy ban đầu sẽ đứng trước.

Input: 1,2,9,134,12,1
Output: 1,2,9,1,12,134

Không khó nhưng làm thế nào để code cho hay đây?
Thím xây dựng hàm Compare (so sánh) theo tiêu chí của đề bài.
Rồi căn cứ theo hàm so sánh ấy áp dụng Quick Sort, Merge Sort hay Heap Sort đều OK! :)
 

haylachoi

Member
Tạo 1 cái list 2 chiều. Dòng 0 chứa các số có 1 chữ số, dòng 1 chứa các số 2 chữ số... Dùng 1 vòng for là xong.
Demo = c#.
PHP:
        static void Main(string[] args)
        {
            int[] arr = { 1,2,9,134,12,1  };
            List<int>[] r = new List<int>[10];
            foreach (var n in arr)
            {            
               var index = Count(n);
                if (r[index] == null)
                {
                    r[index] = new List<int>();
                    r[index].Add(n);
                }
                else r[index].Add(n);
            }
            Display(r);
            ReadKey();
        }
        static int Count(int n)
        {
            int r = 0;
            while (n >= 10)
            {
                n /= 10;
                r++;
            }
            return r;
        }
        static void Display(List<int>[] r)
        {
            for (int i = 0; i < r.Length; i++)
                if (r[i] != null)
                    foreach (var n in r[i])
                        Console.WriteLine(n);
        }
   
[I][I][\PHP][/I][/I][/Quote]
 
Last edited:

MainOC

Junior Member
Bài này yêu cầu stable sort. Thường thì quicksort vs heapsort không có tính chất này.
 
Đề bài hơi khó hiểu nhỉ, theo mình hiểu thì ouput thế này mới đúng:
Output: 1,1,12,134,2,9
Rào trước: không bash, không chửi, không nói có gì mà khó hiểu, okay?
 

haylachoi

Member
Đề bài hơi khó hiểu nhỉ, theo mình hiểu thì ouput thế này mới đúng:
Output: 1,1,12,134,2,9
Rào trước: không bash, không chửi, không nói có gì mà khó hiểu, okay?
Đề này so sánh số chữ số thôi, số nào nhiều chữ số hơn thì đứng sau. Các số có cùng số chữ số thì xem số nào đứng trước trong đề bài thì sẽ xếp trước.
 

omyto

Junior Member
Cho 1 dãy số tự nhiên. Hãy sắp xếp theo thứ tự từ bé đến lớn theo số chữ số. Nếu số chữ số như nhau thì số đứng trước trong dãy ban đầu sẽ đứng trước.

Input: 1,2,9,134,12,1
Output: 1,2,9,1,12,134


Không khó nhưng làm thế nào để code cho hay đây?
Cái ví dụ sai hay sao vậy? Phải là thế này chứ:

Input: 1,2,9,134,12,-11
Output: 1,2,9,-11,12,134


Hay là số đã có trong dãy 1 thì sẽ nằm đầu dãy 2, chứ ko nằm trong dãy 1 nữa ??
 

rosario_1

Member
Thím xây dựng hàm Compare (so sánh) theo tiêu chí của đề bài.
Rồi căn cứ theo hàm so sánh ấy áp dụng Quick Sort, Merge Sort hay Heap Sort đều OK! :)
Đây là cách tớ làm trên thực tế. Chỉ có điều tớ chưa cảm thấy thỏa mãn với cái cách tớ làm, nó hơi thô chưa được "đẹp". Bạn cho xin code cụ thể, tớ muốn tham khảo cách b
 

rosario_1

Member
Counting sort/ radix sort nhé. Tham khảo rồi modify cho phù hợp. Bài tập về nhà à?
Ko bạn, tớ đi làm từ lâu lắm lắm rồi, đây chỉ đơn giản vừa là giải trí vừa là tự nâng cấp skill thuật toán. Tớ đọc Counting sort/ radix sort thì thấy không phải giải pháp, vì yêu cầu sắp xếp của mình có dựa vào cả thứ tự ban đầu nên không work, bạn thử cho code chạy thử xem thế nào.
 

vouu0102

Junior Member
Chuyển các số về số chữ số rồi sort trên dãy mới. 1,2,9,134,12,1 -> 1,1,1,3,2,1 -> sort -> output (chọn cái sort nào nó giữ nguyên thứ tự ấy.)
 

trungpham90

Đã tốn tiền
Ko bạn, tớ đi làm từ lâu lắm lắm rồi, đây chỉ đơn giản vừa là giải trí vừa là tự nâng cấp skill thuật toán. Tớ đọc Counting sort/ radix sort thì thấy không phải giải pháp, vì yêu cầu sắp xếp của mình có dựa vào cả thứ tự ban đầu nên không work, bạn thử cho code chạy thử xem thế nào.
Anh tự nghĩ đi, radix sort thì anh đổi sort từ least significant digit (LSD) -> (most significant digit) MSD sang sort từ MSD -> LSD là xong, có cái j khó, radix sort là stable sort, ko hiểu sao lại ko giữ đc thứ tự? Bài để anh làm cho giỏi lại bắt tôi code thì làm làm j?
 

lypbon

Member
func sapxep(array ar) {
for(i = 0 -> ar.length) {
for(j = i + 1 -> ar.length) {
if(ar [ i ] .length > ar [ j ] . length) {
tem = ar [ i ];
ar [ i ] = ar[ j ];
ar[j] = tem;
}
}
}
}
 

duyquang6

Junior Member
CPP version:
Code:
void stupidSort(vector<int>& nums) {
    vector<int> idx(nums.size());
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int k) {return floor(log10(nums.at(i))) < floor(log10(nums[k])) || (i < k);});
    vector<int> temp;
    temp.reserve(nums.size());
    for (auto i : idx) {
        temp.emplace_back(nums[i]);
    }
    std::copy(temp.begin(), temp.end(), nums.begin());
}
 
Last edited:

nautilux

Đã tốn tiền
C#:
static void Main(string[] args)
        {
            List<int> cin = new List<int>() { 1, 2,1234, -44,9, 134, 12, 1,-11, };
            int maxLength = cin.Max().ToString().Length;
            int length = 1;
            
            Console.WriteLine(string.Join(",", swap(cin, length, maxLength)));
            Console.ReadLine();
        }
        public static List<int> swap(List<int> cin, int length, int maxLength)
        {
            List<int> cout = new List<int>();
            for (int i = 0; i < cin.Count; i++)
            {
                if ((cin[i] < 0 && (cin[i] * -1).ToString().Length == length) || (cin[i] > 0 && cin[i].ToString().Length == length))
                {
                    cout.Add(cin[i]);
                }
            }
            if(length < maxLength)
            {
                cout.AddRange(swap(cin, length + 1, maxLength));
            }
            return cout;
        }
 

Super Namek

Member
Cho 1 dãy số tự nhiên. Hãy sắp xếp theo thứ tự từ bé đến lớn theo số chữ số. Nếu số chữ số như nhau thì số đứng trước trong dãy ban đầu sẽ đứng trước.

Input: 1,2,9,134,12,1
Output: 1,2,9,1,12,134

Không khó nhưng làm thế nào để code cho hay đây?
C:
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
#include <math.h>

int values[] = {  1,2,9,134,12,1 };

int stupid_compare (const void * a, const void * b)
{
  return ( log10(*(int*)a) - log10(*(int*)b ));
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), stupid_compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}
1591266056919.png

http://cpp.sh/9ngoh
 

duyquang6

Junior Member
C:
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
#include <math.h>

int values[] = {  1,2,9,134,12,1 };

int stupid_compare (const void * a, const void * b)
{
  return ( log10(*(int*)a) - log10(*(int*)b ));
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), stupid_compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}
View attachment 80182
http://cpp.sh/9ngoh
thử testcase này đi
[1,10,9,134,12,1]
 

Super Namek

Member
thử testcase này đi
[1,10,9,134,12,1]
Sửa lại

thử testcase này đi
[1,10,9,134,12,1]
Fixed : Quên chưa ép kiểu về int

C:
/* qsort example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
#include <math.h>

int values[] = { 1,10,9,134,12,1 };

int stupid_compare (const void * a, const void * b)
{
  return ( (int)log10(*(int*)a) - (int)log10(*(int*)b ));
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), stupid_compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}
 
Top