Cần giải thích về thuật toán sắp xếp mảng theo thứ tự tăng dần trong C

#1

Xin chào , Mình đang làm một bài tập về sắp xếp mảng trong C. và đây là code mẫu mà mình kiếm được

#include <stdio.h>
#include <stdlib.h>

void sapxep(int a[],int kichthuoc);
int main()
{
    int a[8]={8,3,4,5,6,7,1,2};
    printf("Mang truoc khi sap xep\n");
    printf("a ={8,3,4,5,6,7,1,2}\n");
    sapxep(a,8);
    return 0;
}

void sapxep(int a[],int kichthuoc)
{
    int i,j,temp=0;
    for(i=0;i<kichthuoc-1;i++)
        for(j=i+1;j<kichthuoc;j++)
    {
        if(a[i]>a[j])
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    printf("Mang sau khi sap xep lai\n");
    for(i=0;i<kichthuoc;i++)
    {
        printf("%d ",a[i]);
    }
}

Mong các bạn giải thích giúp mình về 2 vòng lặp for về cách thức nó họat động ra sao , như thế nào ?
Mình có dạo một vòng quanh google thì tìm được thuật toán sắp xếp nổi bọt và nó có liên quan đến đoạn code này, nhưng đọc thì cũng hiểu lan man, không nắm bắt rõ được, do mình tự học và mình cũng chưa học phần cấu trúc dữ liệu và giải thuật, thế nên, mong các bạn giải thích về cái cách mà 2 vòng lặp đó hoạt động . Và đây là đoạn code mình không hiểu.

int i,j,temp=0;
    for(i=0;i<kichthuoc-1;i++)
        for(j=i+1;j<kichthuoc;j++)
    {
        if(a[i]>a[j])
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }

Mong các bạn giúp đỡ. Xin cảm ơn :smiley:

Giải thích vòng lặp for lồng nhau?
Thắc mắc về chương trình trộn mảng một chiều trong C
#2

Với mỗi phần tử thứ i, ta kiểm tra xem có “bọt” (là phần tử bé hơn/lớn hơn phần tử i hiện tại) nào nổi lên ở phía sau (từ phần tử i+1 đến phần tử cuối) hay không, nếu có “bọt” thì đổi chỗ “bọt” với phần tử i. Nói 1 cách đơn giản nhất, khi duyệt dãy từ trái sang phải, tại vị trí thứ i, ta cố gắng để phần tử thứ i bé nhất/lớn nhất (theo thứ tự sắp xếp) có thể: khi i=1 thì ta tìm số bé nhất trong cả dãy rồi gán vào a[1], khi i=2 thì ta tìm số bé nhất trong dãy từ a[2] đến a[n],…

#3

Cảm ơn bạn đã giải thích, nhưng mình vẫn không hiểu đọan sau cho lắm :sweat_smile:

#4

Bạn không hiểu chỗ nào?

#5

Đoạn này ấy mình vẫn chưa hiểu lắm ?

#6

Mình nghĩ là đoạn ấy dễ hiểu mà…
Tức là với mỗi phần tử thứ i, nếu ta phát hiện ra phần tử a[j] nhỏ hơn nó ở phía sau (đoạn từ phần tử thứ i+1 đến phần tử cuối) thì tráo đổi 2 phần tử đó (đoạn temp=a[i]; a[i]=a[j]; a[j]=temp là tráo đổi 2 phần tử thông qua phần tử phụ temp) để cho phần tử thứ i nhỏ nhất có thể. Mục đích của thuật toán này là đẩy hết số lớn về đầu dãy.

#7

Mình có kiếm được một hình ảnh minh hoạ về thuật toán sắp xếp nổi bọt xem qua thì cũng hiểu được một phần rồi, nhưng cái mình không hiểu ở đây là vòng for hoạt động như thế nào để giống như ở hình dưới :slight_smile:
http://hoidaplaptrinh.net/media/img/BubbleSort.gif

#8

Đây không phải là thuật toán nổi bọt.
Đây là thuật toán sắp xếp chọn. Chọn số nhỏ nhất trong những số chưa sắp xếp để đưa lên đầu dãy.
“Selection Sort”

1 Like
#9

Em cũng không để ý code kia là selection sort =))

#10
  • for lồng thì nhớ là: 1 cha có nhiều con là được
  • còn cái thuật toán bạn đưa ra đấy là interchange sort chứ không phải bubble sort bạn nha[quote=“Hoai_Nam_Truong, post:1, topic:46790”]
    Mình có dạo một vòng quanh google thì tìm được thuật toán sắp xếp nổi bọt và nó có liên quan đến đoạn code này,
    [/quote]
// Đổi chỗ trực tiếp - sắp xếp mảng tăng dần
void InterchangeSort(int arr[], int num){

    for (int i = 0; i < num - 1; ++i) {
        
        for (int j = i + 1; j < num; ++j) {
            
            if(arr[i] > arr[j]){

                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}
#11

Và nếu thấy rằng arr[i] đóng vai trò là min thứ i+1 thì đây có thể xem là selection sort phiên bản lỗi (swap nhiều quá). Vì vậy kinh điển không bao giờ nhắc đến thuật toán này.

Điểm khác biệt cơ bản: bubble sort so sánh hai phần tử liền kề, vì vậy nếu để nguyên mà chạy thì dở nhất trong họ O(n^2). Nhìn chung insertion là tốt nhất, còn shellsort thì không thông dụng.

3 Likes
#12

thuật toán sắp xếp nổi bọt : quả nào to nhất thì nỗi lên trước
ở vòng lặp đầu tiên -> rà soát tất cả
ở vòng lặp thứ 2
-> tìm những quả bóng vô lý (quả trước to hơn quả sau)
-> tìm được quả bóng vô lý -> thay đổi vị trí của chúng

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?