Quick Sort Algorithm

Kategori: Popular Algorithms , 22 Kasım 2019 , JanFranco


Problem:

Klasik sıralama problemi, n boyutlu bir dizinin elemanlarının küçükten büyüğe sıralanması.

Yaklaşım:

Divide and conquer tasarım tekniğini kullanan Quick Sort algoritmasını implemente edeceğiz. Algoritma tasarım ve analiz bölümünde Quick Sort algoritmasını, sahte kodunu ve analizini görmüştük.

Çözüm:




import java.util.Random;

public class QuickSort {
	
	static int partition(int[] arr, int low, int high) {
		int pivot = arr[high], i = low - 1;
		for(int j=low; j<high; j++) {
			if(arr[j] < pivot) {
				i++;
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		
		int temp = arr[i+1];
		arr[i+1] = arr[high];
		arr[high] = temp;
		
		return i+1;
	}
	
	static void sort(int arr[], int low, int high) { 
        if (low < high) { 
            int pi = partition(arr, low, high); 
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    }
	
	static int[] generateArr(int n, int max) {
		Random random = new Random();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = random.nextInt(max);
		}
		return arr;
	}
	
	static void printArr(int[] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	public static void main(String[] args) {
		int[] arr = generateArr(50, 100);
		System.out.println("Before quick sort:");
		printArr(arr);
		sort(arr, 0, arr.length-1);
		System.out.println("\nAfter quick sort:");
		printArr(arr);
	}

}

>>

Before quick sort:
42 80 19 18 37 28 70 76 25 25 42 37 57 27 1 60 32 50 31 44 60 79 66 20 6 44 34 77 42 82 48 98 80 99 21 7 51 17 28 30 40 2 28 74 99 36 29 29 45 94 
After quick sort:
1 2 6 7 17 18 19 20 21 25 25 27 28 28 28 29 29 30 31 32 34 36 37 37 40 42 42 42 44 44 45 48 50 51 57 60 60 66 70 74 76 77 79 80 80 82 94 98 99 99 


Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın