Giải thích thuật toán sắp xếp?

[Kenly (Kenly Boy)]

Em suy nghĩ mãi về cái về cái thuật toán này mà không ra @@ Các bác cho thằng em sáng dạ ra với em vẫn không hiểu nó được vận hành như thế nào ? ai đó giúp em mô phỏng hoạt động của nó với. Em cảm ơn !

int[] myArray={3,-3,4,20,40,28,39};
       for(int i=0; i<myArray.length-1;i++){
           for(int j = i; j<=myArray.length-1;j++){
               if(myArray[i]<myArray[j]){
                   
                   int temp;
                   temp=myArray[i];
                   myArray[i]=myArray[j];
                   myArray[j]=temp;
               }
           }
           
           
       }
       for(int i = 0; i< myArray.length;i++){
           System.out.println(myArray[i]+"");
       }
       

[rogp10]

Cái này mình đã bàn rồi, thực ra logic của nó chỉ là Selection sort mà thôi, hay có thể gọi là “phiên bản lỗi của Selection sort”. Vì a[i] sẽ đóng vai trò max (bài này là max) trong Selection sort.

[Kenly (Kenly Boy)]

Ý bác là cái này á. Tôi nghĩ là không phải đâu @@

[rogp10]

Selection sort tìm chỉ số của phần tử min/max và đợi đến cuối cùng mới swap. Max của đoạn a[j…n] có thể tìm theo kiểu for(int j = i; j < a.length; ++j) if(max < a[j]) vân vân. Bài của bạn xếp giảm nên dĩ nhiên code phải khác xếp tăng rồi

Giờ thay max bằng a[i] vì sắp giảm nên max có chỉ số bé nhất. Vậy thì không thể gán trực tiếp được vì sẽ hỏng invariant (không được gán, chỉ được swap).

[Kenly (Kenly Boy)]

Em đang hỏi giải thích cái code trên cơ mà @@ vs lại tăng hay giảm cái code của em bác thay đổi dấu ở:

if(myArray[i]<myArray[j])

nó sẽ t ra thôi !

[rogp10]

Ơ, thì mình đã giải thích rồi đấy nó giống bài tìm max thôi.

[Kenly (Kenly Boy)]

Dạ cho mình cảm ơn ^^ mong là có cao nhân khác giải thích cho em hiểu hơn @@

[rogp10]

Thật ra tìm thuật toán trong code là hạ sách chẳng qua vì code này ở đâu cũng có thôi.

Ý tưởng cơ bản là tìm max/min thứ nhất, thứ hai, thứ ba, … rồi sẽ ra được mảng giảm/tăng theo ý muốn. Tất nhiên là nó dzỏm vì mỗi phép so sánh đáng lí phải lấy ra được 1 bit entropy, mà n! khả năng thì có nlog2(n) bit thôi.

[Kenly (Kenly Boy)]

Dạ cảm ơn bác đã dống góp ! mong là sẽ có cao nhân khác giúp mình hiểu hơn…

[nguyenhuuca (Nguyen Ca)]

https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxjYW5oaG9hbmh8Z3g6NDFlYzhkYmJjYTRjNDE3MQ
coi nó chạy từng bước là hiểu thôi. chạy cái slide trên
Cái thuật giải này là tự nhiên nhất rồi.

[rogp10]

Thực sự thuật toán tự nhiên nhất là Selection Sort tại vì tìm min nó dễ hơn là canh swap ntn.

Khi đã hiểu rồi thì luồng dữ liệu của “Interchange” và Selection là như nhau (các cặp so sánh và đổi chỗ không khác gì nhau). Bubble với Gnome thì khác hẳn. Nếu nói về nghịch thế (inversions) thì cả Bubble và Gnome cũng sử dụng vậy, chỉ là liền kề hay không.

[hieudien]

Em cứ tưởng cái này là ngược lại của bubble sort @@ chỉ đơn giản là nếu nó lớn hơn thì cho nó lên đầu thôi mà

[rogp10]

chỉ đơn giản là nếu nó lớn hơn thì cho nó lên đầu thôi mà

Cùng mục tiêu nhưng cách làm khác nhau.

[Kenly (Kenly Boy)]

Full giải thuật toán đây các bác…Theo nhiều các

[Kenly (Kenly Boy)]

Giờ em đã hiểu hơn rồi. Chắc lâu nay đầu em cứ nghĩ cao siêu thì ra nó lại đơn giản đến như thế ^^ cảm ơn các bác đã đóng góp.
Chỉ cần in ra các bước là ok mà gì mà căng thẳng.
P/s: tôi thích mày mò

public class MyClass {
    public static void main(String args[]) {
        int[] myArray = { 5,7,-6,9,6};
 
for (int i = 0; i < myArray.length - 1; i++) {
    System.out.println("so mang i: " +i );
    System.out.println("so trong mang i: " + myArray[i] );
   
    System.out.println("--------------------");
    for (int j = i; j <= myArray.length - 1; j++) {   
          System.out.println("so mang j: " +j );
    System.out.println("so trong mang j: " + myArray[j]);
    System.out.println("--------------------");
        if (myArray[i] > myArray[j]) {
            // Thao tác này đổi chỗ 2å giá trị ở 2 vị trí i, j của mảng
            int temp;
            temp = myArray[i];
             System.out.println("so temp: " + temp );
             System.out.println("--------------------");
            myArray[i] = myArray[j];
            System.out.println("so array[i]: " + myArray[i] );
            System.out.println("so array[j]: " + myArray[j] );
            System.out.println("--------------------");
            myArray[j] = temp;
            System.out.println("so temp: " + temp );
               System.out.println("--------------------");
            
            
            
        }
    }
}
 

    }
}

[Ba_Nam (Hacker boy)]

Chỉ là sort thôi mà @@

[rogp10]

Sort có 5 7 cách sort :v

[Ba_Nam (Hacker boy)]

À ừ …

[rogp10]

Để tiếp tục thì phải nêu lên cái đúng trước. Selection Sort tìm vị trí của số max trước:

for(maxp = i, int j = i+1; j < n; ++j)
   if(a[j] > a[maxp]) maxp = j;

rồi mới swap.

for(int i = 0; i < n; ++i) {
    for(maxp = i, int j = i+1; j < n; ++j)
       if(a[j] > a[maxp]) maxp = j;
    if(i != maxp) swap(a[i], a[maxp]); //nếu không có điều kiện thì số lần ghi là 2n.
}

Ưu điểm (!) của thuật toán chỉ là ít ghi (O(n) lần) vào mem nhưng lại không tận dụng đươc các đoạn đúng thứ tự trong mảng. Bubble tính ra vẫn rất tệ vì swap nhiều kinh khủng.

Một đoạn code đầy trên mạng thay đoạn lệnh trong vòng lặp j bằng:

if(a[j] > a[i]) swap(a[i], a[j]); //O(n^2) lần ghi mem!

Lệnh swap lấy a[i] = a[j] cũ và gán a[j] = a[i] cũ. Nửa đầu cho thấy rằng a[i] đóng vai trò của a[maxp] bên kia (do maxp ban đầu bằng i). Do sort không được đưa thêm giá trị mới và xóa đi giá trị (invariant) nên phải swap. Nhưng như vậy thì swap nhiều quá nên gọi là phiên bản lỗi.

Phân tích kĩ hơn, gán a[i] = a[j] tức là gán max cho a[i] (và a[j] không còn được xét nữa), nên a[j] > a[i] chính là a[j] > max, giống như một đoạn code tìm max mẫu mực.

Vì sắp xếp mảng P nghĩa là đưa ra một hoán vị (lặp) tăng dần của P theo thứ tự nào đó nên không được đưa vào giá trị mới.

Ngoài ra khi dịch “phiên bản lỗi” thì phải đề phòng có swap, mà máy sẽ dùng swap trick, nên mất 1 thanh ghi để lưu trữ a[j]