Hai vòng lặp For lồng vào nhau hoạt động như thế nào?

kinh_tieu · August 20, 2019, 5:11am

Trong phần sắp xếp dãy số trong mảng có hàm hoán vị này nhưng mình không hiểu cơ chế hoạt động của nó, cụ thể các bước hoán vị như thế nào, tại sao điều kiện phải là i<n-1 ? Mong các cao thủ chỉ giáo. Thank you.

void TangDan(int a[], int n)
 { int tg; 
  for(int i = 0; i < n - 1; i++) 
  { 
    for(int j = i + 1; j <n;  j++) 
    {
       if(a[i] &gt; a[j]) 
       { 
          tg = a[i]; 
          a[i] = a[j]; 
          a[j] = tg;
        }
    } 
      
  } 
}

rogp10 · August 20, 2019, 5:18am

Vì chỉ số chạy từ 0 đến n-1 nên n-1 mà +1 nữa là văng ra ngoài

Còn hoán vị ntn thì bạn lấy hai cái chén/bát… rồi làm thử thôi.

Bây giờ tới phần thuật toán. Code ở trên thực chất là phiên bản lỗi của selection sort (luồng chạy không khác) mà selection sort bắt nguồn từ ý tưởng đơn giản là chọn phần tử nhỏ nhất, nhỏ nhì, … rồi ráp lại thành mảng.

vanhieu · August 20, 2019, 7:48am

Cái này không đúng nhé, vì ở vòng for dưới có điều kiện j < n rồi. Việc để i < n-1 giúp code bớt đi 1 lần lặp dư thừa không cần thiết thôi.

Ý tưởng thuật toán thì bạn xem gif này nhé:

Code chuẩn theo ý tưởng của ảnh gif trên:

void swap(int &xp, int &yp)
{
    int temp = xp;
    xp = yp;
    yp = temp;
}
 
// Hàm selection sort
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
    // Di chuyển ranh giới của mảng đã sắp xếp và chưa sắp xếp
    for (i = 0; i < n-1; i++)
    {
    // Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp
    min_idx = i;
    for (j = i+1; j < n; j++)
        if (arr[j] < arr[min_idx])
        min_idx = j;
 
    // Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên
        swap(arr[min_idx], arr[i]);
    }
}

kinh_tieu · August 20, 2019, 2:22pm

Thank you các bạn đã giải đáp