Quicksort stable là đâyCode:const compare = (a,b)=>a.toString.length - b.toString().length; const array = [1,2,9,134,12,1]; const result = array.sort(compare);
Vẫn chưa đúng bạn. Input { 1,0,8,123,0,0 }.Sửa lại
Fixed : Quên chưa ép kiểu về int
C:/* qsort example */ return ( (int)log10(*(int*)a) - (int)log10(*(int*)b ));
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ớ.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?
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.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.
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}
/* 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;
}
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.
Thanks bro. Tớ chưa tính case 0 thậtThí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.
Quick sort thôi fenCho 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?
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
}
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).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ạ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 đề.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.
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;
}
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
}