Sắp xếp là quá trình sắp xếp các phần tử theo thứ tự tăng dần (hoặc) giảm dần.
Các kiểu sắp xếp
Ngôn ngữ C cung cấp năm kỹ thuật sắp xếp như sau -
- Sắp xếp bong bóng (hoặc) Sắp xếp trao đổi
- Sắp xếp lựa chọn
- Sắp xếp chèn (hoặc) Sắp xếp tuyến tính
- Sắp xếp nhanh (hoặc) Sắp xếp trao đổi phân vùng
- Sắp xếp Hợp nhất (hoặc) Sắp xếp bên ngoài
Sắp xếp nhanh
Đó là một thuật toán phân chia và chinh phục.
- Bước 1 - Chọn một phần tử từ một mảng, gọi nó là phần tử tổng hợp.
- Bước 2 - Chia phần tử mảng chưa được sắp xếp thành hai mảng.
- Bước 3 - Nếu giá trị nhỏ hơn phần tử pivot nằm trong mảng con thứ nhất thì các phần tử còn lại có giá trị lớn hơn pivot sẽ nằm trong mảng con thứ hai.
Hãy xem xét một ví dụ được đưa ra bên dưới, trong đó
- P là phần tử xoay vòng.
- L là con trỏ bên trái.
- R là con trỏ phù hợp.
Các phần tử là 6, 3, 7, 2, 4, 5.
Bây giờ,
- Trụ ở vị trí cố định.
- Tất cả các yếu tố bên trái đều ít hơn.
- Các phần tử bên phải lớn hơn pivot.
- Bây giờ, chia mảng thành 2 mảng con phần bên trái và phần bên phải.
- Sử dụng phân vùng bên trái, áp dụng sắp xếp nhanh.
Bây giờ,
- Trụ ở vị trí cố định.
- Tất cả các phần tử bên trái ít hơn và được sắp xếp
- Các phần tử bên phải lớn hơn và được sắp xếp theo thứ tự.
- Danh sách được sắp xếp cuối cùng là kết hợp hai mảng con là 2, 3, 4, 5, 6, 7
Ví dụ
Sau đây là chương trình C để sắp xếp các phần tử bằng cách sử dụng kỹ thuật sắp xếp nhanh -
#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
} Đầu ra
Khi chương trình trên được thực thi, nó tạo ra kết quả sau -
How many elements are u going to enter?: 10 Enter 10 elements: 2 3 5 7 1 9 3 8 0 4 Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9