Quick Sort Algoritması (Hızlı Sıralama) Nedir?

Quick Sort Algoritması (Hızlı Sıralama) Nedir?

Quick Sort Algoritması, böl ve yönet (divide and conquer) algoritmalarından biri olan ve yaygın olarak kullanılan bir sıralama algoritmasıdır. Sıralanacak bir diziyi daha küçük iki parçaya ayırıp oluşan bu küçük parçaların kendi içinde sıralanması mantığıyla çalışmaktadır.

Sapientia Üniversitesi’nde Macar halk dansı yapılarak anlatılan Quick Sort algoritmasını izlerken çalışma mantığını kavrayabilirsiniz.

Quick Sort Algoritmasının (Hızlı Sıralama Algoritması) orijinalinde (Hoare, C.A.R. (1962)) ilk elemanı pivot olarak seçse de pivot elemanı seçerken 4 farklı seçenek mevcut:

  1. Her zaman ilk öğeyi pivot olarak seçmek

  2. Her zaman son öğeyi pivot olarak seçmek

  3. Pivot olarak rastgele bir öğe seçmek

  4. Pivot olarak medyanı seçmek

İlk olarak pivot eleman seçildikten sonra, pivottan büyük elemanlar sağına, pivottan küçük elemanlar soluna gelecek şekilde bir sıralama gerçekleştirilir. Pivot elemana eşit olan sayılar sıralamanın küçükten büyüğe ya da büyükten küçüğe olmasına bağlı olarak pivot elemanın her iki tarafına da geçebilir. Kodlamada sağ ve solun oluşması için iki indis gerekir.

Özyinelemeli olarak (recursive) çağrılarak, oluşan küçük diziler için aynı işlem tekrarlanır. Sağdaki elemanlar içerisinden bir pivot ve soldaki elemanlar içerisinden bir pivot seçilerek tekrar aynı işlem gerçekleşir ve sıralanır. Ta ki bütün dizi sıralanana kadar aynı işlem gerçekleşir.

Quick Sort Algoritması (Hızlı Sıralama) Örnek

Örnek olarak bir dizi ele alalım. {5, 3, 2, 6, 8} olsun. Sıralamanın ilk adımı olarak bir pivot seçelim. İlk elemanı pivot olabilir. Daha sonra sırayla sayılara bakalım ve pivot elemandan büyük mü, küçük mü, eşit mi kontrol edelim. 3 sayısı 5’ten küçük olduğu için sola gelir. Aynı şekilde 2’de. Daha sonra 6’ya bakılır ve 5’ten büyük olduğu için sağa gelir. 8’de 5’ten büyük olduğu için sağa gelir. İlk sıralama da başka eleman kalmadığı için aynı işlem alt dizilere de (sağ ve sol) yapılır. Bir pivot seçilir ve kendi içinde sıralanır. Dizinin son sıralanmış hali {2, 3, 5, 6, 8} şeklindedir.

Quick Sort C++ Kodları

#include <bits/stdc++.h> 
using namespace std; 

// A utility function to swap two elements 
void swap(int* a, int* b) 
{ 
	int t = *a; 
	*a = *b; 
	*b = t; 
} 

/* This function takes last element as pivot, places 
the pivot element at its correct position in sorted 
array, and places all smaller (smaller than pivot) 
to left of pivot and all greater elements to right 
of pivot */
int partition (int arr[], int low, int high) 
{ 
	int pivot = arr[high]; // pivot 
	int i = (low - 1); // Index of smaller element 

	for (int j = low; j <= high - 1; j++) 
	{ 
		// If current element is smaller than the pivot 
		if (arr[j] < pivot) 
		{ 
			i++; // increment index of smaller element 
			swap(&arr[i], &arr[j]); 
		} 
	} 
	swap(&arr[i + 1], &arr[high]); 
	return (i + 1); 
} 

/* The main function that implements QuickSort 
arr[] --> Array to be sorted, 
low --> Starting index, 
high --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
	if (low < high) 
	{ 
		/* pi is partitioning index, arr[p] is now 
		at right place */
		int pi = partition(arr, low, high); 

		// Separately sort elements before 
		// partition and after partition 
		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high); 
	} 
} 

/* Function to print an array */
void printArray(int arr[], int size) 
{ 
	int i; 
	for (i = 0; i < size; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

// Driver Code 
int main() 
{ 
	int arr[] = {10, 7, 8, 9, 1, 5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	quickSort(arr, 0, n - 1); 
	cout << "Sorted array: \n"; 
	printArray(arr, n); 
	return 0; 
} 

// This code is contributed by rathbhupendra 

Quick Sort C Kodları

#include<stdio.h> 

// A utility function to swap two elements 
void swap(int* a, int* b) 
{ 
	int t = *a; 
	*a = *b; 
	*b = t; 
} 

/* This function takes last element as pivot, places 
the pivot element at its correct position in sorted 
	array, and places all smaller (smaller than pivot) 
to left of pivot and all greater elements to right 
of pivot */
int partition (int arr[], int low, int high) 
{ 
	int pivot = arr[high]; // pivot 
	int i = (low - 1); // Index of smaller element 

	for (int j = low; j <= high- 1; j++) 
	{ 
		// If current element is smaller than the pivot 
		if (arr[j] < pivot) 
		{ 
			i++; // increment index of smaller element 
			swap(&arr[i], &arr[j]); 
		} 
	} 
	swap(&arr[i + 1], &arr[high]); 
	return (i + 1); 
} 

/* The main function that implements QuickSort 
arr[] --> Array to be sorted, 
low --> Starting index, 
high --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
	if (low < high) 
	{ 
		/* pi is partitioning index, arr[p] is now 
		at right place */
		int pi = partition(arr, low, high); 

		// Separately sort elements before 
		// partition and after partition 
		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high); 
	} 
} 

/* Function to print an array */
void printArray(int arr[], int size) 
{ 
	int i; 
	for (i=0; i < size; i++) 
		printf("%d ", arr[i]); 
	printf("\n"); 
} 

// Driver program to test above functions 
int main() 
{ 
	int arr[] = {10, 7, 8, 9, 1, 5}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	quickSort(arr, 0, n-1); 
	printf("Sorted array: \n"); 
	printArray(arr, n); 
	return 0; 
} 

Quick Sort Java Kodları

class QuickSort 
{ 
	/* This function takes last element as pivot, 
	places the pivot element at its correct 
	position in sorted array, and places all 
	smaller (smaller than pivot) to left of 
	pivot and all greater elements to right 
	of pivot */
	int partition(int arr[], int low, int high) 
	{ 
		int pivot = arr[high]; 
		int i = (low-1); // index of smaller element 
		for (int j=low; j<high; j++) 
		{ 
			// If current element is smaller than the pivot 
			if (arr[j] < pivot) 
			{ 
				i++; 

				// swap arr[i] and arr[j] 
				int temp = arr[i]; 
				arr[i] = arr[j]; 
				arr[j] = temp; 
			} 
		} 

		// swap arr[i+1] and arr[high] (or pivot) 
		int temp = arr[i+1]; 
		arr[i+1] = arr[high]; 
		arr[high] = temp; 

		return i+1; 
	} 


	/* The main function that implements QuickSort() 
	arr[] --> Array to be sorted, 
	low --> Starting index, 
	high --> Ending index */
	void sort(int arr[], int low, int high) 
	{ 
		if (low < high) 
		{ 
			/* pi is partitioning index, arr[pi] is 
			now at right place */
			int pi = partition(arr, low, high); 

			// Recursively sort elements before 
			// partition and after partition 
			sort(arr, low, pi-1); 
			sort(arr, pi+1, high); 
		} 
	} 

	/* A utility function to print array of size n */
	static void printArray(int arr[]) 
	{ 
		int n = arr.length; 
		for (int i=0; i<n; ++i) 
			System.out.print(arr[i]+" "); 
		System.out.println(); 
	} 

	// Driver program 
	public static void main(String args[]) 
	{ 
		int arr[] = {10, 7, 8, 9, 1, 5}; 
		int n = arr.length; 

		QuickSort ob = new QuickSort(); 
		ob.sort(arr, 0, n-1); 

		System.out.println("sorted array"); 
		printArray(arr); 
	} 
} 
/*This code is contributed by Rajat Mishra */

Quick Sort Python Kodları

def partition(arr,low,high): 
	i = ( low-1 )		 # index of smaller element 
	pivot = arr[high]	 # pivot 

	for j in range(low , high): 

		# If current element is smaller than the pivot 
		if arr[j] < pivot: 
		
			# increment index of smaller element 
			i = i+1
			arr[i],arr[j] = arr[j],arr[i] 

	arr[i+1],arr[high] = arr[high],arr[i+1] 
	return ( i+1 ) 

# The main function that implements QuickSort 
# arr[] --> Array to be sorted, 
# low --> Starting index, 
# high --> Ending index 

# Function to do Quick sort 
def quickSort(arr,low,high): 
	if low < high: 

		# pi is partitioning index, arr[p] is now 
		# at right place 
		pi = partition(arr,low,high) 

		# Separately sort elements before 
		# partition and after partition 
		quickSort(arr, low, pi-1) 
		quickSort(arr, pi+1, high) 

# Driver code to test above 
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 
print ("Sorted array is:") 
for i in range(n): 
	print ("%d" %arr[i]), 

# This code is contributed by Mohit Kumra 

Quick Sort C# Kodları

using System; 

class GFG { 
	
	/* This function takes last element as pivot, 
	places the pivot element at its correct 
	position in sorted array, and places all 
	smaller (smaller than pivot) to left of 
	pivot and all greater elements to right 
	of pivot */
	static int partition(int []arr, int low, 
int high) 
	{ 
		int pivot = arr[high]; 
		
		// index of smaller element 
		int i = (low - 1); 
		for (int j = low; j < high; j++) 
		{ 
			// If current element is smaller 
			// than the pivot 
			if (arr[j] < pivot) 
			{ 
				i++; 

				// swap arr[i] and arr[j] 
				int temp = arr[i]; 
				arr[i] = arr[j]; 
				arr[j] = temp; 
			} 
		} 

		// swap arr[i+1] and arr[high] (or pivot) 
		int temp1 = arr[i+1]; 
		arr[i+1] = arr[high]; 
		arr[high] = temp1; 

		return i+1; 
	} 


	/* The main function that implements QuickSort() 
	arr[] --> Array to be sorted, 
	low --> Starting index, 
	high --> Ending index */
	static void quickSort(int []arr, int low, int high) 
	{ 
		if (low < high) 
		{ 
			
			/* pi is partitioning index, arr[pi] is 
			now at right place */
			int pi = partition(arr, low, high); 

			// Recursively sort elements before 
			// partition and after partition 
			quickSort(arr, low, pi-1); 
			quickSort(arr, pi+1, high); 
		} 
	} 

	// A utility function to print array of size n 
	static void printArray(int []arr, int n) 
	{ 
		for (int i = 0; i < n; ++i) 
			Console.Write(arr[i] + " "); 
			
		Console.WriteLine(); 
	} 

	// Driver program 
	public static void Main() 
	{ 
		int []arr = {10, 7, 8, 9, 1, 5}; 
		int n = arr.Length; 
		quickSort(arr, 0, n-1); 
		Console.WriteLine("sorted array "); 
		printArray(arr, n); 
	} 
} 

// This code is contributed by Sam007. 
Kaynakça : https://www.geeksforgeeks.org/quick-sort/

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Bunları da okumak ister misiniz