알고리즘 퀵 정렬(quicksort) 이란 ?

퀵 정렬은

병합정렬과 마찬가지로 Divide and Conquer 알고리즘입니다.(나누기와 정복). 

 

퀵 정렬의 알고리즘은 pivot(피벗) 요소를 선택하고 선택한 피벗 요소보다 작은 모든 요소는 피벗의 왼쪽으로 이동하고 더 큰 요소는 모두 오른쪽으로 이동하도록 배열 요소를 재정렬합니다. 마지막으로 알고리즘은 피벗요소의 왼쪽과 오른쪽에 있는 하위 배열을 재귀적으로 정렬합니다. 이것을 퀵정렬의 핵심 프로세스 파티션이라고 합니다. 

 

퀵 정렬 알고리즘의 단점 :  이미 정렬된 배열에서 pivot이 가장 크거나 가장 작으면 가장 큰 시간이 소요됩니다. 

 

 

그림을 보시면 더 이해하기 쉬울거같습니다. 

여러 가지 방법으로 분할을 할수 있습니다, 아주 간단한 논리입니다. 가장 왼쪽 요소부터 시작하여 더 작은 혹은 같은 요소의 인덱스를 i로 추척합니다. 순회하는 동안 더 작은 요소를 찾으면 현재 요소를 arr[i] 로 바꿉니다, 그렇지 않다면 현재 요소를 무시하면 됩니다. 

 

작은 수가 인덱스의 시작점 이고 높은수가 인덱스에 마지막 입니다. 

quickSort(arr[],low,high)
if(low<high){
/*pi is partitioning index, arr[pi] is now at right place*/
pi = partition(arr,low,high);
quickSort(arr,low, pi-1); // before pi
quickSort(arr,pi+1, high); // after pi
}
}

혹은 마지막 요소를 pivot으로 정하고 sorted array 의 알맞은 자리에 넣어둡니다. 
그리고 피봇보다 작은값은 왼쪽 큰값을 오른쪽으로 넣는 방식으로 행하여지빈다. 

partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  

    i = (low – 1)  // Index of smaller element and indicates the 
    // right position of pivot found so far

    for (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] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

// Java implementation of QuickSort
import java.io.*;

class GFG {

	// A utility function to swap two elements
	static void swap(int[] arr, int i, int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	/* 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)
	{

		// pivot
		int pivot = arr[high];

		// Index of smaller element and
		// indicates the right position
		// of pivot found so far
		int i = (low - 1);

		for (int j = low; j <= high - 1; j++) {

			// If current element is smaller
			// than the pivot
			if (arr[j] < pivot) {

				// Increment index of
				// smaller element
				i++;
				swap(arr, i, j);
			}
		}
		swap(arr, i + 1, high);
		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[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
	static void printArray(int[] arr, int size)
	{
		for (int i = 0; i < size; i++)
			System.out.print(arr[i] + " ");

		System.out.println();
	}

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

		quickSort(arr, 0, n - 1);
		System.out.println("Sorted array: ");
		printArray(arr, n);
	}
}

// This code is contributed by Ayush Choudhary

OutPut

Sorted array: 
1 5 7 8 9 10 

 

 

출처 :  https://www.geeksforgeeks.org/quick-sort/   , 한번에 끝내는 알고리즘 영상에서 퀵정렬 알고리즘 강의