Bài viết hướng dẫn độc giả, đặc biệt là những độc giả mới bắt đầu làm quen với lập trình hình thành tư duy phân tích và thiết kế một thuật toán xáo trộn 1 mảng cho trước.
Data Structure & Algorithm C/C++ Huỳnh Duy Lộc 2017-09-13 21:00:41

Giới thiệu

Trong quá trình học tập và rèn luyện lập trình, tôi gặp nhiều vấn đề nảy sinh với một yêu cầu tưởng chừng như đơn giản như xáo trộn mảng cho trước, tuy vậy, với nhiều độc giả mới bước vào con đường lập trình, yêu cầu đó có lẽ sẽ khiến nhiều bạn bỡ ngỡ.

Bài viết hướng đến độc giả muốn luyện tập tư duy và kỹ thuật lập trình hoặc có nhu cầu tạo ra thuật toán này để ứng dụng vào công việc hoặc học tập.

Tiền đề bài viết

Bài viết sinh thêm ý tưởng và mục tiêu trở thành các bài tham khảo cho học viên STDIO Training và cũng mang mục tiêu tập luyện khả năng diễn đạt của bản thân.

Môi trường thử nghiệm

Tôi dùng ngôn ngữ C++ trên Visual Studio Community 2017 để hiện thực thuật toán. Nếu chưa cài đặt Visual Studio Community, bạn có thể tham khảo bài viết Cài Đặt Môi Trường Lập Trình C++ Với Visual Studio 2017 Community.

Thuật toán xáo trộn mảng cho trước

Phân tích thiết kế thuật toán

Tận dụng một tính chất của mảng là: chỉ số của các phần tử trong mảng không được trùng nhau. Do đó phương pháp này sẽ tiến hành gồm 2 bước như sau:

  • Bước 1: Tạo một mảng số không trùng nhau bằng cách duyệt mảng từ đầu đến cuối và gán giá trị của từng phần tử bằng với chỉ số của nó (ở đây tôi đang lấy ví dụ là một mảng số nguyên nên giá trị từng phần tử trong mảng sẽ là các số nguyên).
  • Bước 2: Duyệt lại mảng trên, tại phần tử ở vị trí thứ i bất kì, hoán đổi giá trị của phần tử ở vị trí thứ i ấy với giá trị của một phần tử ở vị trí thứ j, với j là một vị trí ngẫu nhiên mà vị trí ấy là kết quả của phép chọn ngẫu nhiên giá trị trong khoảng từ i + 1 và n (n là số lượng phần tử của mảng).

Hiện thực thuật toán

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void Swap(int* number_1, int* number_2)
{
	int temp = *number_1;
	*number_1 = *number_2;
	*number_2 = temp;
}

void ShuffleArray(int* arr, int n)
{
	srand(time(NULL));

	int minPosition;
	int maxPosition = n - 1;
	int swapPosition;

	int i = 0;
	while (i < n - 1)
	{
		minPosition = i + 1;
		swapPosition = rand() % (maxPosition - minPosition + 1) + minPosition;

		Swap(&arr[i], &arr[swapPosition]);
		i++;
	}
}

int main()
{
	int arr[5] = { 1, 2, 3, 4, 5 };
	int size = 5;

	ShuffleArray(arr, size);

	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}

	while (true);
	return 0;
}