Sắp xếp mảng là bài toán thường gặp trong thực tế. Mặc dù hầu hết các ngôn ngữ lập trình hiện nay đều cung cấp các phương thức sắp xếp mảng. Tuy nhiên, trong thực tế, đôi khi bạn không gặp đúng bài toán có thể áp dụng các thuật toán có sẵn này mà phải tự sắp xếp.
Yêu cầu
Viết chương trình khởi tạo một mảng n phần tử số nguyên, sau đó sắp xếp các phần tử trong mảng theo thứ tự tăng dần.
Phân tích và tìm cách giải
- Đầu vào: mảng các phần tử a[] ={3,2,8,9,1,8,4,5}
- Đầu ra: In ra mảng đã sắp xếp tăng dần
- Phân tích:
- Có nhiều thuật toán sắp xếp khác nhau như Chèn (Insertion Sort), Nổi bọt (Bubble Sort), Sắp xếp nhanh (Quick Sort). Ở đây chúng ta sẽ sử dụng phương pháp sắp xếp nổi bọt để cài đặt.
- Duyệt và tìm phần tử nhỏ nhất đưa lên vị trí đầu tiên.
- Lặp lại bưới trên cho phần tử thứ 2, cho đến phần tử cuối cùng thì mảng được sắp xếp.
Các bước thực hiện
Khởi tạo mảng a[]
Cho lặp biến i từ 0 đến n-1, với n là kích thước của mảng
Lặp biến j từ i+1 đến n
Nếu a[j] <a[i]
Đổi a[i] với a [j]
In mảng a[] mới ra thì đây là mảng đã được sắp xếp tăng dần.
Cách biểu diễn thuật toán sắp xếp các phần tử trong mảng
Trong trường hợp này, tôi sử dụng ngôn ngữ giả.
Declare int a[]={3,2,8,9,1,8,4,5},i, j, temp
Loop i=0 to a.lengh -2
Loop j=i+1 to a.lengh -1
If(a[j]<a[i]) //Hoán đổi giá trị a[i] và a[j]
temp=a[i]
a[i]=a[j]
a[j]=temp
// In mảng đã sắp xếp
Loop i=0 to a.lengh -1
Print a[i]
Kết quả Dry Run cho thuật toán này:
