مرتب سازی سریع (Quick Sort) در جاوا

سلام دوستان در این سری از آموزش برنامه نویسی جاوا به آموزش مرتب سازی سریع (Quick Sort) در جاوا می پردازیم کوییک‌سورت یکی از الگوریتم‌های مرتب‌سازی است که به‌دلیل مصرف حافظه کم، سرعت اجرای مناسب و پیاده‌سازی ساده بسیار مورد قبول واقع شده‌است.
الگوریتم مرتب سازی سریع (Quick Sort) که یکی از بهترین الگوریتم در مرتب سازی (Sort) آرایه است در ادامه با ما همراه باشید تا نحوه پیاده سازی این الگوریتم را در زبان جاوا یاد گیرید.

الگوریتم مرتب سازی سریع (Quick Sort)

۱- انتخاب عنصر لولا : یکی از عناصر آرایه به عنوان عنصر لولا (pivot) – به عنوان مثال عنصر اول – انتخاب می‌شود.
۲- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ (left) و راست (right) نامیده می‌شوند.
۳- مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند. این تابع به صورت Recursive است چون خود را درون خود صدا میزند.
در ادامه یک مثال ساده از مرتب سازی سریع (Quick Sort) مشاهده می کنید.

در ادامه یک کلاس قرار دارد که نام آن QuickSort است آنا را ساخته و کدهای زیر رار در آن قرار دهید.

public class QuickSort {
	private int[] arrA;
	public QuickSort(int[] arrA) {
		this.arrA = arrA;
	}
	public void quickS(int low, int high) {
		int mid = (low + high) / 2;
		int left = low;
		int right = high;
		int pivot = arrA[mid];
		while (left <= right) {
			while (arrA[left] < pivot)
				left++;
			while (arrA[right] > pivot)
				right--;
			if (left <= right) {
				int temp = arrA[left];
				arrA[left] = arrA[right];
				arrA[right] = temp;
				left++;
				right--;
			}
		}
		if (low < right)
			quickS(low, right);
		if (left < high)
			quickS(left, high);
	}
	public void display() {
		for (int i = 0; i < arrA.length; i++) {
			System.out.print(" " + arrA[i]);
		}
	}
}

public class QuickSort {

private int[] arrA;

public QuickSort(int[] arrA) {

this.arrA = arrA;

}

public void quickS(int low, int high) {

int mid = (low + high) / 2;

int left = low;

int right = high;

int pivot = arrA[mid];

while (left <= right) {

while (arrA[left] < pivot)

left++;

while (arrA[right] > pivot)

right--;

if (left <= right) {

int temp = arrA[left];

arrA[left] = arrA[right];

arrA[right] = temp;

left++;

right--;

}

if (low < right)

quickS(low, right);

if (left < high)

quickS(left, high);

}

public void display() {

for (int i = 0; i < arrA.length; i++) {

System.out.print(" " + arrA[i]);

}

در نهایت بعد از اینکه کلاس بالا را ایجاد کردید کدهای زیر را در Main خود استفاده کنید.

int a[] = { 6, 2, 4, 12, 10 };
QuickSort i = new QuickSort(a);
System.out.print("UnSorted : ");
i.display();
i.quickS(0, a.length - 1);
System.out.println("");
System.out.print("Quick Sorted : ");
i.display();

int a[] = { 6, 2, 4, 12, 10 };

QuickSort i = new QuickSort(a);

System.out.print("UnSorted : ");

i.display();

i.quickS(0, a.length - 1);

System.out.println("");

System.out.print("Quick Sorted : ");

i.display();

در بالا در نهایت بعد از انجام عملیات مرتب سازی انجام می شود.

این آموزش هم به پایان رسید.
موفق و پیروز باشید.

مطالعه بیشتر

مرتب سازی سریع (Quick Sort) در جاوا

الگوریتم مرتب سازی سریع (Quick Sort)

مطالب مشابه

دیدگاهتان را بنویسید لغو پاسخ

الگوریتم مرتب سازی سریع (Quick Sort)

مطالب مشابه

دیدگاهتان را بنویسید لغو پاسخ

اشتراک گذاری در شبکه های اجتماعی