Mảng đã sắp xếp (Sorted Array) có các phần tử theo thứ tự (số, chữ cái...). Có nhiều thuật toán sắp xếp: bubble sort, insertion sort, selection sort, merge sort, quick sort, heap sort... Đây dùng Selection Sort.
Selection Sort: lặp lại tìm phần tử nhỏ nhất trong phần chưa sắp xếp và hoán đổi với phần tử đầu phần chưa sắp xếp.
Ví dụ
#include <iostream>
using namespace std;
void selectionSort(int a[], int n) {
int i, j, min, temp;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
int main() {
int a[] = {22, 91, 35, 78, 10, 8, 75, 99, 1, 67};
int n = sizeof(a) / sizeof(a[0]);
int i;
cout << "Given array is:" << endl;
for (i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
selectionSort(a, n);
cout << "\nSorted array is: \n";
for (i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}Kết quả
Given array is: 22 91 35 78 10 8 75 99 1 67 Sorted array is: 1 8 10 22 35 67 75 78 91 99
Hàm selectionSort()
Hai vòng lặp lồng. Vòng ngoài i từ 0 đến n-2. Vòng trong tìm min từ i+1 đến n-1. Hoán đổi a[i] và a[min].
void selectionSort(int a[], int n) {
int i, j, min, temp;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}Hàm main()
int main() {
int a[] = {22, 91, 35, 78, 10, 8, 75, 99, 1, 67};
int n = sizeof(a) / sizeof(a[0]);
int i;
cout << "Given array is:" << endl;
for (i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
selectionSort(a, n);
cout << "\nSorted array is: \n";
for (i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}