[DSA] Sắp xếp giảm dần
Để sắp xếp một danh sách các số nguyên theo thứ tự giảm dần bằng cách sử dụng Stack, ta có thể thực hiện các bước sau đây:
- Tạo một Stack rỗng để lưu trữ các phần tử của danh sách.
- Duyệt qua danh sách và đẩy từng phần tử vào Stack bằng hàm push.
- Tạo một mảng rỗng để lưu trữ các phần tử đã sắp xếp.
- Lặp lại việc lấy phần tử từ Stack bằng hàm pop và đưa phần tử đó vào mảng đã tạo ở bước 3 cho đến khi Stack rỗng.
Mảng chứa các phần tử đã sắp xếp theo thứ tự giảm dần.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Định nghĩa cấu trúc stack
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
// Hàm khởi tạo stack
void initStack(Stack *s) {
s->top = -1;
}
// Hàm kiểm tra stack có rỗng không
int isEmpty(Stack *s) {
return s->top == -1;
}
// Hàm kiểm tra stack có đầy không
int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
// Hàm đẩy phần tử vào stack
void push(Stack *s, int x) {
if (isFull(s)) {
printf("Stack is full. Cannot push %d\n", x);
return;
}
s->data[++s->top] = x;
}
// Hàm lấy phần tử ra khỏi stack
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty. Cannot pop\n");
return -1;
}
return s->data[s->top--];
}
// Hàm sắp xếp một danh sách các số nguyên theo thứ tự giảm dần bằng cách sử dụng stack
void sortDescending(Stack *s) {
Stack temp;
initStack(&temp);
while (!isEmpty(s)) {
int x = pop(s);
while (!isEmpty(&temp) && temp.data[temp.top] < x) {
push(s, pop(&temp));
}
push(&temp, x);
}
while (!isEmpty(&temp)) {
push(s, pop(&temp));
}
}
// Hàm in ra stack
void printStack(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return;
}
printf("Stack: ");
for (int i = s->top; i >= 0; i--) {
printf("%d ", s->data[i]);
}
printf("\n");
}
int main() {
Stack s;
initStack(&s);
push(&s, 10);
push(&s, 4);
push(&s, 6);
push(&s, 8);
push(&s, 1);
push(&s, 2);
printf("Before sorting:\n");
printStack(&s);
sortDescending(&s);
printf("After sorting:\n");
printStack(&s);
return 0;
}
Không có nhận xét nào