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

Ruby:
a =  [1,2,9,134,12,1]
puts a.sort_by.with_index{|x,i| [x.digits.size, i]}
không đảm bảo nhanh nhất nhưng đảm bảo ngắn nhất :>
 
php dùng usort kiểm tra độ dài length nếu a[ i ]>a[i+1] return xếp lại vị trí, nếu bằng nhau thì return a[ i ]-a[i+1].
 
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?
Bảo bạn show code để thấy ý tưởng của bạn bằng giấy trắng mực đen. Xin lỗi vì có thể tớ ngu, nhưng tớ chẳng nhận thấy sự liên hệ nào giữa sort số chữ số và việc sort LSD, MSD, hoặc có thể có nhưng chí ít nó không hiển nhiên, ít nhất là với cá nhân tớ.

Nếu dùng radix sort cái duy nhất tớ có thể nghĩ đến là tính số chữ số của từng số trong dãy, rồi dùng radix sort. Nhưng với cá nhân tớ mà nói đây là 1 cách tiếp cận tầm thường, bất kỳ thuật toán sắp xếp nào stable cũng đều làm được, thế thì Radix để làm gì?

Cuối cùng bạn đừng nói cái gì để tớ làm cho giỏi, cái gì bắt code. Tớ nói thật mục đích tớ lập những topic như thế này chỉ đơn giản kiểu như 1 trò chơi "đố vui"lúc trà dư tửu hậu, bạn tìm thấy giá trị đấy trong đó hãy vào mà show code là 1 phần của nó, không thì mời đừng tham gia.
 
Bảo bạn show code để thấy ý tưởng của bạn bằng giấy trắng mực đen. Xin lỗi vì có thể tớ ngu, nhưng tớ chẳng nhận thấy sự liên hệ nào giữa sort số chữ số và việc sort LSD, MSD, hoặc có thể có nhưng chí ít nó không hiển nhiên, ít nhất là với cá nhân tớ.

Nếu dùng radix sort cái duy nhất tớ có thể nghĩ đến là tính số chữ số của từng số trong dãy, rồi dùng radix sort. Nhưng với cá nhân tớ mà nói đây là 1 cách tiếp cận tầm thường, bất kỳ thuật toán sắp xếp nào stable cũng đều làm được, thế thì Radix để làm gì?

Cuối cùng bạn đừng nói cái gì để tớ làm cho giỏi, cái gì bắt code. Tớ nói thật mục đích tớ lập những topic như thế này chỉ đơn giản kiểu như 1 trò chơi "đố vui"lúc trà dư tửu hậu, bạn tìm thấy giá trị đấy trong đó hãy vào mà show code là 1 phần của nó, không thì mời đừng tham gia.
Tôi xin lỗi anh trước nếu cách nc của tôi khiến anh thấy ko thoải mái.

Tôi xin tự phân trần là do tôi trả lời trên Stackoverflow nhiều, gặp nhiều thằng lười nên có lẽ giọng điệu hơi gay gắt.

Còn về vấn đề code, tôi thấy Trình độ mỗi người mỗi khác, thời gian mỗi người bỏ vào cũng khác. Tôi ko thấy có lợi ích code những bài ntn, nên tôi chỉ nói đường hướng thôi.

Bản thân anh coi cách của tôi là tầm thường, tôi chê, vì đã là topic mở ra thảo luận, mà có định kiến, chỉ nên làm thế này, chỉ nên trả lời ntn, thì ko thể học hỏi đc.

PV ở FAANG, candidate cũng bàn về hướng giải quyết trước, rồi mới lao vào code, code chỉ là công đoạn cuối cùng, engineer phải đảm bảo hướng làm thoả mãn yêu cầu của bài toán mới code, anh ko nên để chuyện thảo luận về 1 vấn đề thành 1 cuộc công kích cá nhân.
 
Last edited:
Vẫn chưa đúng bạn. Input { 1,0,8,123,0,0 }.
Output của bạn { 1,123,0,8,0,0 }
Output đúng phải là {1,0,8,0,0,123}

Thím Super Namek quên chưa xét giá trị a, b đầu vào của hàm stupid_compare =0.
Bởi khi lấy log10 của 0, giá trị trả về sẽ là một số âm rất lớn (-2147483648 )

Mình đã sửa lại, và chạy OK rồi.

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

//int values[] = { 1,10,9,134,12,1 };
int values[] = {1,0,8,123,0,0};

int stupid_compare (const void * a, const void * b)
{
int temp1, temp2;

if (*(int*)a==0) temp1=0;
else temp1= (int)log10(*(int*)a);

if (*(int*)b==0) temp2=0;
else temp2= (int)log10(*(int*)b);

return temp1-temp2;
}

int main ()
{
int n;
qsort (values, 6, sizeof(int), stupid_compare);
for (n=0; n<6; n++)
printf ("%d ",values[n]);
return 0;
}
 
Last edited:
Tôi xin lỗi anh trước nếu cách nc của tôi khiến anh thấy ko thoải mái.

Tôi xin tự phân trần là do tôi trả lời trên Stackoverflow nhiều, gặp nhiều thằng lười nên có lẽ giọng điệu hơi gay gắt.

Còn về vấn đề code, tôi thấy Trình độ mỗi người mỗi khác, thời gian mỗi người bỏ vào cũng khác. Tôi ko thấy có lợi ích code những bài ntn, nên tôi chỉ nói đường hướng thôi.

Bản thân anh coi cách của tôi là tầm thường, tôi chê, vì đã là topic mở ra thảo luận, mà có định kiến, chỉ nên làm thế này, chỉ nên trả lời ntn, thì ko thể học hỏi đc.

PV ở FAANG, candidate cũng bàn về hướng giải quyết trước, rồi mới lao vào code, code chỉ là công đoạn cuối cùng, engineer phải đảm bảo hướng làm thoả mãn yêu cầu của bài toán mới code, anh ko nên để chuyện thảo luận về 1 vấn đề thành 1 cuộc công kích cá nhân.

mình thường ko quan tâm cách giải mà chỉ quan tâm đến challenge mà bài toán đưa ra cũng như hạn chế khi dùng cách giải bình thường. Bài này thím nghĩ 2 cái đó là gì? Stable sort và ???. Từ đó mới suy ra radix sort có lợi thế hơn chỗ nào.

* mình noob mới biết radix sort luôn. Đang coi thử nó chạy ra sao.
* ??? mình đoán là cost của việc compare là lớn nên phải hạn chế chỗ này. Trong khi stable sort thông dụng nhanh nhất là merge sort (imo) lại compare rất nhiều, đó có thể là bẫy của bài toán.
 
Thím Super Namek quên chưa xét giá trị a, b đầu vào của hàm stupid_compare =0.
Bởi khi lấy log10 của 0, giá trị trả về sẽ là một số âm rất lớn (-2147483648 )

Mình đã sửa lại, và chạy OK rồi.
Thanks bro. Tớ chưa tính case 0 thật
PYa3Yt3.png
 
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?
Quick sort thôi fen


Java:
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(1,23,9,11,4,7,123,0,23));
        Collections.sort(numbers, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.toString().length() -  o2.toString().length() ;
            }
        });
        for(int i: numbers){
            System.out.print(i + " ");
        }
        //1 9 4 7 0 23 11 23 123
    }
 
Last edited:
mình thường ko quan tâm cách giải mà chỉ quan tâm đến challenge mà bài toán đưa ra cũng như hạn chế khi dùng cách giải bình thường. Bài này thím nghĩ 2 cái đó là gì? Stable sort và ???. Từ đó mới suy ra radix sort có lợi thế hơn chỗ nào.

* mình noob mới biết radix sort luôn. Đang coi thử nó chạy ra sao.
* ??? mình đoán là cost của việc compare là lớn nên phải hạn chế chỗ này. Trong khi stable sort thông dụng nhanh nhất là merge sort (imo) lại compare rất nhiều, đó có thể là bẫy của bài toán.
Bài toán này có 2 constraints, thứ nhất là số lượng phần tử (n), thứ hai là số lượng chữ số trong mỗi phần tử (d).
- Nếu chỉ nghĩ theo constraints thứ nhất, thì merge sort là lựa chọn đương nhiên.
- Nếu giả sử mỗi phần tử đều nằm trong khoảng Signed Int (32 bit) thì số lượng chữ số sẽ là <= 10. Vậy dùng radix sort sẽ đc thuật toán có độ phức tạp là O(nd) ~ O(10n) ~ O(n).
- Việc dùng merge sort hoặc các thuật toán sort khác thông dụng hơn, là vì radix sort chỉ dùng đc trong trường hợp đặc thù này, nên nó ko quá phổ biến và ko nhiều tính ứng dụng.
 
Bài toán này có 2 constraints, thứ nhất là số lượng phần tử (n), thứ hai là số lượng chữ số trong mỗi phần tử (d).
- Nếu chỉ nghĩ theo constraints thứ nhất, thì merge sort là lựa chọn đương nhiên.
- Nếu giả sử mỗi phần tử đều nằm trong khoảng Signed Int (32 bit) thì số lượng chữ số sẽ là <= 10. Vậy dùng radix sort sẽ đc thuật toán có độ phức tạp là O(nd) ~ O(10n) ~ O(n).
- Việc dùng merge sort hoặc các thuật toán sort khác thông dụng hơn, là vì radix sort chỉ dùng đc trong trường hợp đặc thù này, nên nó ko quá phổ biến và ko nhiều tính ứng dụng.
Bạn này nói thì toàn đao to búa lớn, StackOverflow, FAANG các kiểu nhưng ngay cả những cái bình thường nhất nói thẳng mình thấy rất có vấn đề.

Thứ nhất, 2 constraints của bài toán này cái đầu tiên số lượng chữ số, cái thứ 2 là vị trí của nó trong dãy ban đầu nếu số chữ số là như nhau.

Thứ 2, mình nghĩ là khi bàn về phương hướng, cách tiếp cận thì đầu tiên người ta phải làm rõ vấn đề, từ đó đưa ra các cách tiếp cận phù hợp để giải được bài toán đấy và cuối cùng là đánh giá ưu nhược điểm rồi chọn lựa và code. Đằng này bạn vứt ra 1 cái tool không 1 lời giải thích, nói thẳng đến tận bây giờ mình vẫn ko hiểu cách tiếp cận của bạn và tại sao bạn dùng radix.

Thứ 3, kể cả là dùng radix. Dù tính lý thuyết đúng là, O(n) nhưng chưa chắc đã là nhanh trên thực tế. Với thuật toán này vì là so sánh chữ số nên với mỗi số bạn đều sẽ phải tính từng chỗ số một (%10, %100, %1000 ...) rồi sắp xếp nên số lượng phép toán rất nhiều, cái trước mắt có thể nhìn thấy là constant time rất lớn. Đến Heap Sort, dù trường hợp xấu nhất là nlogn so với n^2 của QuickSort, nhưng thực tế các thư viện Sort của các ngôn ngữ toàn là QuickSort, là bởi constant time của QuickSort nhỏ hơn, thực tế chạy nhanh hơn.

Cuối cùng, đây tớ nói chuyện với tư cách "việc công", ko liên quan đến chuyện "đả kích cá nhân" hay gì nhé. Đó là, nếu tớ phải làm việc với bạn, thì điều đầu tiên tớ làm là email cho xếp "Anh hoặc chuyển em, hoặc chuyển nó đi chỗ khác, chứ với cái kiểu như thế chắc chắn ko thể làm việc được với nhau. Chấm hết". Đến cái điều cơ bản là diễn đạt cho tớ hiểu ý tưởng của bạn, thấy được cái lý của bạn (chỉ là thấy được lý thôi chưa cần biết có đồng tình hay không) bạn còn làm chả ra hồn, tớ chả hiểu người khác làm việc với bạn kiểu quái gì không biết nữa.
 
Bạn này nói thì toàn đao to búa lớn, StackOverflow, FAANG các kiểu nhưng ngay cả những cái bình thường nhất nói thẳng mình thấy rất có vấn đề.

Thứ nhất, 2 constraints của bài toán này cái đầu tiên số lượng chữ số, cái thứ 2 là vị trí của nó trong dãy ban đầu nếu số chữ số là như nhau.

Thứ 2, mình nghĩ là khi bàn về phương hướng, cách tiếp cận thì đầu tiên người ta phải làm rõ vấn đề, từ đó đưa ra các cách tiếp cận phù hợp để giải được bài toán đấy và cuối cùng là đánh giá ưu nhược điểm rồi chọn lựa và code. Đằng này bạn vứt ra 1 cái tool không 1 lời giải thích, nói thẳng đến tận bây giờ mình vẫn ko hiểu cách tiếp cận của bạn và tại sao bạn dùng radix.

Thứ 3, kể cả là dùng radix. Dù tính lý thuyết đúng là, O(n) nhưng chưa chắc đã là nhanh trên thực tế. Với thuật toán này vì là so sánh chữ số nên với mỗi số bạn đều sẽ phải tính từng chỗ số một (%10, %100, %1000 ...) rồi sắp xếp nên số lượng phép toán rất nhiều, cái trước mắt có thể nhìn thấy là constant time rất lớn. Đến Heap Sort, dù trường hợp xấu nhất là nlogn so với n^2 của QuickSort, nhưng thực tế các thư viện Sort của các ngôn ngữ toàn là QuickSort, là bởi constant time của QuickSort nhỏ hơn, thực tế chạy nhanh hơn.

Cuối cùng, đây tớ nói chuyện với tư cách "việc công", ko liên quan đến chuyện "đả kích cá nhân" hay gì nhé. Đó là, nếu tớ phải làm việc với bạn, thì điều đầu tiên tớ làm là email cho xếp "Anh hoặc chuyển em, hoặc chuyển nó đi chỗ khác, chứ với cái kiểu như thế chắc chắn ko thể làm việc được với nhau. Chấm hết". Đến cái điều cơ bản là diễn đạt cho tớ hiểu ý tưởng của bạn, thấy được cái lý của bạn (chỉ là thấy được lý thôi chưa cần biết có đồng tình hay không) bạn còn làm chả ra hồn, tớ chả hiểu người khác làm việc với bạn kiểu quái gì không biết nữa.

Bàn bạc vấn đề nếu ông bạn thấy tôi giải thích chưa đủ cặn kẽ, ở chỗ nào thì tôi sẽ gt thêm thôi.

Ông bạn nóng quá. Calm down bro. Ko hiểu mình đao to búa lớn ở chỗ nào? Mình thuần tuý chia sẻ kn vs góc nhìn thôi, mọi người đều muốn học hỏi thêm, ko phải như vậy sao?

Còn giải mấy bài thuật toán thì tôi thấy 2 cái quan trọng nhất là time vs space complexity, nhưng có vẻ là cách nghĩ của ông bạn khác. Thế mới nói là mỗi người sẽ có quan điểm khác nhau nên cách tiếp cận sẽ khác nhau.
 
Last edited:
Bạn này nói thì toàn đao to búa lớn, StackOverflow, FAANG các kiểu nhưng ngay cả những cái bình thường nhất nói thẳng mình thấy rất có vấn đề.

Thứ nhất, 2 constraints của bài toán này cái đầu tiên số lượng chữ số, cái thứ 2 là vị trí của nó trong dãy ban đầu nếu số chữ số là như nhau.

Thứ 2, mình nghĩ là khi bàn về phương hướng, cách tiếp cận thì đầu tiên người ta phải làm rõ vấn đề, từ đó đưa ra các cách tiếp cận phù hợp để giải được bài toán đấy và cuối cùng là đánh giá ưu nhược điểm rồi chọn lựa và code. Đằng này bạn vứt ra 1 cái tool không 1 lời giải thích, nói thẳng đến tận bây giờ mình vẫn ko hiểu cách tiếp cận của bạn và tại sao bạn dùng radix.

Thứ 3, kể cả là dùng radix. Dù tính lý thuyết đúng là, O(n) nhưng chưa chắc đã là nhanh trên thực tế. Với thuật toán này vì là so sánh chữ số nên với mỗi số bạn đều sẽ phải tính từng chỗ số một (%10, %100, %1000 ...) rồi sắp xếp nên số lượng phép toán rất nhiều, cái trước mắt có thể nhìn thấy là constant time rất lớn. Đến Heap Sort, dù trường hợp xấu nhất là nlogn so với n^2 của QuickSort, nhưng thực tế các thư viện Sort của các ngôn ngữ toàn là QuickSort, là bởi constant time của QuickSort nhỏ hơn, thực tế chạy nhanh hơn.

Cuối cùng, đây tớ nói chuyện với tư cách "việc công", ko liên quan đến chuyện "đả kích cá nhân" hay gì nhé. Đó là, nếu tớ phải làm việc với bạn, thì điều đầu tiên tớ làm là email cho xếp "Anh hoặc chuyển em, hoặc chuyển nó đi chỗ khác, chứ với cái kiểu như thế chắc chắn ko thể làm việc được với nhau. Chấm hết". Đến cái điều cơ bản là diễn đạt cho tớ hiểu ý tưởng của bạn, thấy được cái lý của bạn (chỉ là thấy được lý thôi chưa cần biết có đồng tình hay không) bạn còn làm chả ra hồn, tớ chả hiểu người khác làm việc với bạn kiểu quái gì không biết nữa.


bác này nói có lý này,thật cái vụ bigO nó chỉ có ý nghĩa khi số lượng phần tử phải rất lớn ( tầm hơn 1tr) lúc này ta mới có thể xem các phép tính trong 1 vòng lặp là không đáng kể và gần như là bằng nhau. -> thường thuật toán này quan trọng khi xử lý big data.

Còn thường nếu không phải là big data, thì sự khác biệt việc giữa O(n) vs O(n^2) có thể không đáng kể mà dùng quicksort có sắn trong nhiều ngôn ngữ vs tường mình hơn hẳn
 
Java:
    static int MAX_DIGIT_INT = 10; // MAX_INT = (2^31 - 1)

    static int[] sort(int[]data){
        ArrayList<Integer>[]count = new ArrayList[MAX_DIGIT_INT];
        for(int i = 0; i < MAX_DIGIT_INT; i++){
            count[i] = new ArrayList<>();
        }
        for(int i : data){
            count[getNumDigit(i)].add(i);
        }
        int[]result = new int[data.length];
        int index = 0;
        for(ArrayList<Integer> list : count){
            for(int i : list){
                result[index++] = i;
            }
        }
        return result;
    }
   
    static int getNumDigit(int v){
        int result = 0;
        while(v != 0){
            result++;
            v /= 10;
        }
        return result;
    }

Code demo:
https://ideone.com/dA3zSb

Đây, mời các anh.

Constraints khác nhau thì lời giải khác nhau, < 1000 phần tử thì bubble sort cũng chả vấn đề j, đề bài ko rõ ràng, ko cần thiết phải biến thành (n + 1) cuộc tranh cãi thuật toán sort nào là tốt nhất.
 
Last edited:
chả cần làm gì cao siêu, sort này nọ, chỉ cần hash map là đc mà
https://play.golang.org/p/5dOvtnepj7x

Code:
package main

import (
    "fmt"
    "sort"
    "strconv"
)

func main() {
    fmt.Println("Hello, playground")
    arr := []int{1, 2, 9, 134, 12, 1}
    fmt.Println(sortLength(arr))
}

func sortLength(arr []int) []int {
    lengthMap := make(map[int][]int)
    keysMap := make(map[int]bool, 0)

    var result []int
    for _, v := range arr {
        lengthInt := len(strconv.Itoa(v))
        lengthMap[lengthInt] = append(lengthMap[lengthInt], v)
        keysMap[lengthInt] = true
    }
    var keys []int
    for i, v := range keysMap {
        if v == true {
            keys = append(keys, i)
        }
    }
    sort.Ints(keys)

    for _, k := range keys {
        result = append(result, lengthMap[k]...)
    }
    return result
}
 
Back
Top