Thuật toán sắp xếp các số thành dãy : chẵn lẻ chẵn lẻ

tức là 1 số chẵn 1 số lẻ xen kẽ nhau mà ko quan trọng sắp xếp tăng giảm á ?

Em thử search với từ khóa “chẵn lẻ” bằng công cụ tìm kiếm của diễn đàn xem. Có một số bài tương tự. Em xem trước đi, xem có phải đúng cái em đang hỏi không?

Dạ để e xem . Không phải a Đạt ơi
@TTmagic đúng rồi bạn

hóng luôn xem thê nào. nói về thuật toán thì mù màu

Nhìn có vẻ dài nhưng nó không thực hiện được bao nhiêu bước đâu

#include <iostream>
using namespace std;

void swap(int* a,int* b)	{
	
	int temp = *a;
	*a = *b;
	*b = temp;
}

void merge(int* a,int left,int align,int right)	{
	
	int temp1[align-left+1];
	int temp2[right-align];
	int index = left;
	
	for(int i = 0; i < align-left+1; i++)
		temp1[i] = a[index++];
	
	for(int i = 0; i < right-align; i++)
		temp2[i] = a[index++];
		
	index = 0;	
	for(int i = 0; i < align-left+1; i++,index+=2)
		a[index] = temp1[i];
		
	index = 1;
	for(int i = 0; i < right-align; i++,index+=2)
		a[index] = temp2[i];
} 

//Move element is even to left, element is odd to right
void move(int* a,int left,int right)	{
	
	int l = left,r = right;
	
	while(l < r)	{
		
		while(!(a[l] & 1) && l < right)
			l++;
		while(a[r]&1 && r > left)
			r--;
			
		if(l < r)
			swap(&a[l],&a[r]);
	}
	
	int align = l+1;
	merge(a,left,align,right);
}

int main() {
	
	int a[] = { 1,6,4,3,7,7,9,5 };
	int n = sizeof(a)/sizeof(a[0]);
	
	move(a,0,n-1); 
	
	for(int i = 0; i < n; i++)
		cout << a[i] << " ";
		
	return 0;
}

Bạn thích thì tách trực tiếp ra 2 mảng rồi trộn nó lại cho ngắn gọn cũng được. Nếu bạn cần đảm bảo thứ tự cho các phần tử chẵn và các phần tử lẻ thì sắp xếp cho 2 cái mảng phụ temp1 và temp2 là được
Nếu không cho phép dùng mảng phụ thì phải dùng đệ quy làm trực tiếp. Cái này bó tay!

Thuật toán thì mình có thể chỉ cho bạn
Ví dụ bạn có 1 mảng []a = { 1 3 6 4 5 6 7}
Khai báo thêm 1 mảng [7]b để lưu giá trị sau khi tìm thấy.
Chạy 1 vòng for của mảng a để tìm kiếm giá trị lưu vào mảng []b;
Bạn lưu theo biến i của vòng for. Cho i chạy từ 1; i++. 1 2 3 4. Lẻ, chẵn, lẻ chẵn …
Có nghĩa là lợi dụng tính liên tục chẵn lẻ của vòng for để giải quyết bài toán

Có nghĩa là lợi dụng tính liên tục chẵn lẻ của vòng for để giải quyết bài toán

đã hiểu nhưng thắc mắc là so sánh thế nào để được giá trị chẵn lẻ trong khi mảng nhập là 1 con số vô cùng lớn

đã hiểu nhưng thắc mắc là so sánh thế nào để được giá trị chẵn lẻ

Thực ra thì mình cũng chưa có code xem đúng hay sai. Đây chỉ là suy nghĩ khi đọc xong đề bài thôi.

Thường thường làm những bài như này người ta tách mảng ban đần làm 2 mảng. 1 mảng lưu toàn số chẵn và 1 mảng lưu số lẻ.
Sau đó đưa lần lượt 2 mảng chẵn lẻ này vào 1 mảng mới theo cách.
Cho tất cả các giá trị chẵn vào mảng mới tại các vị trí i chẵn , mảng lẻ cho vào vị trí i lẻ.

nói cách này thì xong lâu rồi. chứ thuật toán là chịu

E thì thi vẽ sơ đồ pascal mà

Bó tay. huhuhu T____T

E thì thi vẽ sơ đồ pascal mà

vẽ thì bạn làm như a kia đi, đưa các số chẵn vào 1 mảng a, số lẻ vào 1 mảng b, rồi gộp lại thành mảng c có các phần tử mang chỉ số chẵn là mảng a, chỉ số lẻ là mảng b.

ý tưởng của mình cũng như bn @@

Lọc chẵn lẻ ra 2 mảng Chan[], le[]:
Duyệt mảng mới newArr[]
- Nếu i % 2 == 0 thì newArr[] = chan[] else newArr[] = le[];
Xuất newArr[]

tìm tất cả các số chẵn ,lưu vào những vị trí chẵn của dãy,dùng biến i=i+2,xong là số lẻ thì nhét vào vị trí lẻ … có lẽ thế

Ý e là chẵn lẻ xen kẽ kìa

tìm tất cả các số chẵn ,lưu vào những vị trí chẵn của dãy,dùng biến i=i+2,xong là số lẻ thì nhét vào vị trí lẻ … có lẽ thế

Nếu các số chẵn lưu vào vị trí chẵn của dãy thì những số lẻ nằm trên những vị trí chẵn có thể bị đè lên làm mất mát dữ liệu. Không nên làm trực tiếp như thế.

nhét lẻ vào rồi mất cả chẵn ah :v

ý t là tạo 1 mảng kết quả mà,cứ xét mảng gốc,số nào là số chẵn thì đưa vào vị trí chẵn của mảng kq,xong đưa lẻ vào vị trí còn lại,lúc đầu nên khởi tạo tất cả các số của mảng kq là -1 chẳng hạn,xong chạy 1 vòng nữa,nếu chỗ nào -1 thì lùi cái phần tử tiếp theo đi(trường hợp số chẵn số lẻ không bằng nhau)…mình nghĩ thế?sai chỗ nào các bạn chỉ với,hoang mang style rồi

Dùng O(1) mem thì có thể nghĩ theo hướng chia đôi mảng theo quicksort xong tìm cách swap cho xen kẽ