Sắp xếp mảng trong C++

Chỉ dẫn cách sắp xếp mảng trong C++. Bạn sẽ học được cách sắp xếp phần tử trong mảng C++ bằng hàm qsort() trong thư viện chuẩn, cũng như cách tự tạo hàm sắp xếp mảng trong C++ sau bài học này.

Tất cả chúng ta có 3 phương thức để sắp xếp mảng trong C++ như sau:

• Sắp xếp phần tử trong mảng C++ theo thứ tự tăng dần bằng hàm qsort
• Sắp xếp phần tử trong mảng C++ theo thứ tự giảm dần dần bằng hàm qsort
• Sắp xếp mảng trong C++ bằng hàm tự tạo

Sắp xếp mảng tăng dần trong C++ bằng hàm qsort

Hàm qsort trong C++ là một hàm có sẵn trong header file cstdlib, giúp tất cả chúng ta sắp xếp mảng trong C++. Cú pháp sử dụng hàm qsort() trong C++ như sau:

qsort(array, length, size, compare_fuct);

Trong số đó:

• array là mảng cần so sánh
• length là độ dài (số phần tử) của mảng đó. Đọc thêm: Độ dài mảng trong C++.
• size là kích cỡ một phần tử trong mảng. Chẳng hạn như kiểu int là 4 byte, char là 1 byte ví dụ. Đọc thêm: Kiểu dữ liệu trong C++.
• compare_fuct là hàm so sánh để quyết định thứ tự sắp xếp

Để quyết định thứ tự sắp xếp mảng bằng hàm qsort(), tất cả chúng ta cần sử dụng tới một hàm trung gian là hàm so sánh compare_fuct giúp tìm thấy quan hệ lớn nhỏ giữa hai phần tử.

Trong trường hợp sắp xếp mảng tăng dần trong C++ thì tất cả chúng ta sẽ khái niệm hàm so sánh này như sau:

int
 
compareIntAsc
(
const
 
void
* a, 
const
 
void
* b)
{

    
int
 aNum = *(
int
*)a;

    
int
 bNum = *(
int
*)b;


    
return
 aNum - bNum;

}

& tất cả chúng ta sử dụng hàm qsort để viết chương trình sắp xếp phần tử trong mảng C++ theo thứ tự tăng dần như sau:

using
 
namespace
 
std
;







void
 
show_array
(
int
 
array
[], 
int
 length)
{

    
for
(
short
 i = 
; i < length; i++)  
cout
 << 
array
[i] <<
' '
;   

    
cout
 << 
endl
;

}



int
 
compareIntAsc
(
const
 
void
* a, 
const
 
void
* b)
{

    
int
 aNum = *(
int
*)a;

    
int
 bNum = *(
int
*)b;


    
return
 aNum - bNum;

}



int
 
main
()
{

    
int
 array1[] = {
5
, 
4
, 
7
, 
2
, 
8
, 
7
, 
3
};

    
int
 array2[] = {
99
, 
4
, 
5
, 
2
, 
80
, 
7
, 
3
};


    

    qsort(array1, SIZE_OF_ARRAY(array1), 
sizeof
(
int
), compareIntAsc);

    qsort(array2, SIZE_OF_ARRAY(array2), 
sizeof
(
int
), compareIntAsc);


    

    show_array(array1, SIZE_OF_ARRAY(array1));

    show_array(array2, SIZE_OF_ARRAY(array2));


    
return
 
;

}

Kết quả của phép sắp xếp mảng tăng dần trong C++ như dưới đây. Bạn hãy thử chạy chương trình & kiểm soát nhé.

2 3 4 5 7 7 8 

2 3 4 5 7 80 99 

Sắp xếp mảng giảm dần trong C++ bằng hàm qsort

Như ở phần trên Kiyoshi đã giải thích, thì việc sắp xếp tăng dần hay giảm dần mảng trong C++ bằng hàm qsort() sẽ lệ thuộc vào hàm so sánh sử dụng trong hàm này.

Thành ra, để sắp xếp phần tử trong mảng C++ theo thứ tự giảm dần dần bằng hàm qsort, tất cả chúng ta dễ dàng chỉ cần biến đổi hàm so sánh như dưới đây là xong:

int
 
compareIntDesc
(
const
 
void
* a, 
const
 
void
* b)
{

    
int
 aNum = *(
int
*)a;

    
int
 bNum = *(
int
*)b;


    
return
 bNum - aNum;

}

Sự độc đáo giữa 2 hàm so sánh đó là ở giá trị mà nó trả về. Với hàm compareIntAsc() ở sắp xếp tăng dần thì tất cả chúng ta trả về return aNum - bNum, & với hàm compareIntDesc() ở sắp xếp giảm dần thì tất cả chúng ta trả về giá trị trái lại là return bNum - aNum.

& tất cả chúng ta sử dụng hàm qsort để viết chương trình sắp xếp phần tử trong mảng C++ theo thứ tự giảm dần như sau:

using
 
namespace
 
std
;






void
 
show_array
(
int
 
array
[], 
int
 length)
{

    
for
(
short
 i = 
; i < length; i++)  
cout
 << 
array
[i] <<
' '
;   

    
cout
 << 
endl
;

}



int
 
compareIntDesc
(
const
 
void
* a, 
const
 
void
* b)
{

    
int
 aNum = *(
int
*)a;

    
int
 bNum = *(
int
*)b;


    
return
 bNum - aNum;

}


int
 
main
()
{

    
int
 array1[] = {
5
, 
4
, 
7
, 
2
, 
8
, 
7
, 
3
};

    
int
 array2[] = {
99
, 
4
, 
5
, 
2
, 
80
, 
7
, 
3
};


    

    qsort(array1, SIZE_OF_ARRAY(array1), 
sizeof
(
int
), compareIntDesc);

    qsort(array2, SIZE_OF_ARRAY(array2), 
sizeof
(
int
), compareIntDesc);


    

    show_array(array1, SIZE_OF_ARRAY(array1));

    show_array(array2, SIZE_OF_ARRAY(array2));


    
return
 
;

}

Kết quả của phép sắp xếp mảng giảm dần trong C++ như dưới đây. Bạn hãy thử chạy chương trình & kiểm soát nhé.

8 7 7 5 4 3 2 

99 80 7 5 4 3 2 

Sắp xếp mảng trong C++ bằng hàm tự tạo

Tất cả chúng ta nên sử dụng hàm qsort() ở trên trong các dự án thực tiễn khi cần sắp xếp mảng trong C++. Ngoài ra nếu bạn mong muốn luyện tập viết code C++, cũng như mong muốn tinh thông hơn về cách sắp xếp trong C++ như vậy nào, thì hãy thử tự tạo các hàm sắp xếp mảng tăng dần & giảm dần trong C++ ở phần dưới đây.

Logic sắp xếp mảng

Chẳng hạn tất cả chúng ta có mảng int như sau:

int
 
array
[] = {
4
, 
1
, 
, 
2
, 
3
};

Để sắp xếp mảng này tăng dần trong C++, tất cả chúng ta sử dụng sáng kiến không quá khó. Tất cả chúng ta xét số trước hết của mảng & so sánh lần lượt với các số sót lại từ địa điểm số đó tới cuối mảng. Nếu tìm ra số trước hết bé hơn số đang xét thì sẽ hoán đổi địa điểm của 2 số này với nhau, rồi tiếp tục lặp cho tới khi không còn số nào bé hơn số đang xét nữa, thì chuyển sang xét ở số thứ 2 trong mảng. Cứ như vậy cho tới khi toàn bộ các số đều được xét.

Với mảng ở trên thì tất cả chúng ta sẽ hoán đổi lần lượt như sau:

1. So sánh số trước hết là số 4 lần lượt với các số sót lại. Số 1 là số trước hết bé hơn 4 nên hoán đổi địa điểm 4 với 1. Hiện tại, 1 trở thành số trước hết trong mảng.

2. So sánh 1 lần lượt với các số sót lại. Số 0 là số trước hết bé hơn 1 nên hoán đổi địa điểm 4 với 1. Hiện tại, 0 trở thành số trước hết trong mảng.

3. So sánh 0 lần lượt với các số sót lại. Do không còn số nào bé hơn 0 nữa, nên chấm dứt xét số trước hết & chuyển sang xét số thứ 2 trong mảng, bây giờ là số 4.

4. Lặp lại qúa trình xét ở trên cho tới số cuối cùng trong mảng.

Cuối cùng, kết quả tất cả chúng ta thu về mảng kết quả là {0, 1, 2, 3, 4}.

Với sắp xếp mảng giảm dần trong C++, tất cả chúng ta cũng sử dụng logic tương đương. Ngoài ra thay vì tìm số trước hết bé hơn số đang xét, thì tất cả chúng ta sẽ làm trái lại là tìm số trước hết to hơn số đang xét mà thôi.

Logic hoán đổi phần tử

Để có thể hoán đổi 2 phần tử như trên, tất cả chúng ta cần phải chuẩn bị một vùng tạm thời để chứa một trong 2 phần tử, & hoán đổi với logic temp = X; X = Y; Y = temp;

& để thực hiện được logic hoán đổi 2 số ở trên, tất cả chúng ta sẽ sử dụng từ khoá define để tạo một macro dùng để hoán đổi phần tử, mà Kiyoshi đã chỉ dẫn trong Đảo ngược mảng trong C++ như sau:

Sắp xếp mảng trong C++ bằng hàm tự tạo

Vận dụng các học thức trên, tất cả chúng ta sẽ viết hàm sắp xếp mảng tăng dần trong C++ & hàm sắp xếp mảng giảm dần trong C++ như sau:

void
 
asc_order
(
int
 
array
[], 
int
 n)
{

    

    
for
(
int
 i = 
; i < n - 
1
; i++){

        
for
(
int
 j = i + 
1
; j < n; j++){

            

            
if
(
array
[i] > 
array
[j]) SWAP(
int
,
array
[i],
array
[j]);   

        }

    }

}



void
 
desc_order
(
int
 * 
array
,
int
 n)
{

    

    
for
(
int
 i = 
; i < n - 
1
; i++){

        
for
(
int
 j = i + 
1
; j < n; j++){

            

            
if
(
array
[i] < 
array
[j]) SWAP(
int
,
array
[i],
array
[j]);   

        }

    }

}

& tất cả chúng ta viết chương trình nhập một mảng & sắp xếp phần tử trong mảng C++ như sau:

using
 
namespace
 
std
;






void
 
show_array
(
int
 
array
[], 
int
 length)
{

    
for
(
short
 i = 
; i < length; i++)  
cout
 << 
array
[i] <<
' '
;   

    
cout
 << 
endl
;

}



void
 
asc_order
(
int
 
array
[], 
int
 n)
{

    

    
for
(
int
 i = 
; i < n - 
1
; i++){

        
for
(
int
 j = i + 
1
; j < n; j++){

            

            
if
(
array
[i] > 
array
[j]) SWAP(
int
,
array
[i],
array
[j]);   

        }

    }

}



void
 
desc_order
(
int
 * 
array
,
int
 n)
{

    

    
for
(
int
 i = 
; i < n - 
1
; i++){

        
for
(
int
 j = i + 
1
; j < n; j++){

            

            
if
(
array
[i] < 
array
[j]) SWAP(
int
,
array
[i],
array
[j]);   

        }

    }

}

  

int
 
main
()
{

    
int
 
array
[
100
], n;

    
cout
 << 
">>Nhap so phan tu: "
;

    
cin
 >> n;

 

    
cout
 << 
">>Nhap phan tu:n"
;

    
for
 (
int
 i = 
; i < n; i++) 
cin
 >> 
array
[i];


    

    asc_order(
array
,n);

   

    

    show_array(
array
, n);


    

    desc_order(
array
,n);


    

    show_array(
array
, n);

     

     
return
 
;

}

Kết quả của phép sắp xếp mảng trong C++ bằng hàm tự tạo sẽ như dưới đây. Bạn hãy thử chạy chương trình & kiểm soát nhé.

>>Nhap so phan tu: 5

>>Nhap phan tu:

2 6 87 0 5

0 2 5 6 87 

87 6 5 2 0 

Kết luận

Trên đây Kiyoshi đã chỉ dẫn bạn cách sắp xếp mảng trong C++ rồi. Để nắm vững bài viết bài học hơn, bạn hãy thực hành viết lại các chẳng hạn của ngày lúc này nhé.

& hãy cùng khám phá những học thức sâu hơn về C++ trong các bài học kế đến.