Trong kỹ thuật sắp xếp lựa chọn, danh sách được chia thành hai phần. Trong một phần, tất cả các phần tử được sắp xếp và trong phần khác, các phần tử không được sắp xếp. Lúc đầu, chúng tôi lấy dữ liệu tối đa hoặc tối thiểu từ mảng. Sau khi nhận được dữ liệu (tối thiểu), chúng tôi đặt nó ở đầu danh sách bằng cách thay thế dữ liệu ở vị trí đầu tiên bằng dữ liệu tối thiểu. Sau khi thực hiện mảng nhỏ dần. Như vậy kỹ thuật sắp xếp này đã được thực hiện.
Sự phức tạp của Kỹ thuật Sắp xếp Lựa chọn
-
Độ phức tạp về thời gian:O (n 2 )
-
Độ phức tạp của không gian:O (1)
Input − The unsorted list: 5 9 7 23 78 20 Output − Array after Sorting: 5 7 9 20 23 78
Thuật toán
selectionSort (mảng, kích thước)
Đầu vào :Một mảng dữ liệu và tổng số trong mảng
Đầu ra :Mảng được sắp xếp
Begin for i := 0 to size-2 do //find minimum from ith location to size iMin := i; for j:= i+1 to size – 1 do if array[j] < array[iMin] then iMin := j done swap array[i] with array[iMin]. done End
Mã mẫu
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void selectionSort(int *array, int size) {
int i, j, imin;
for(i = 0; i<size-1; i++) {
imin = i; //get index of minimum data
for(j = i+1; j<size; j++)
if(array[j] < array[imin])
imin = j;
//placing in correct position
swap(array[i], array[imin]);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
selectionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
} Đầu ra
Enter the number of elements: 6 Enter elements: 5 9 7 23 78 20 Array before Sorting: 5 9 7 23 78 20 Array after Sorting: 5 7 9 20 23 78