Quick Sort 구현(Java)

💡 Quick Sort 란?

➡️ 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 범용 정렬 알고리즘이다.

다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

 

분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	O(n^2)
최선 시간복잡도	O(n log n)
평균 시간복잡도	O(n log n)

 

<참고>

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전

 

💡 Quick Sort 구현 - Java Code

import java.util.*;

public class Quick_Sort {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
	    int arr[] = new int[n];
	    
	    for(int i=0; i<n; i++) {
	    	arr[i] = sc.nextInt();
	    }
	    quick1(arr);
	    
        print(arr);
	    sc.close();
	  }

	  public static void quick1(int[] arr) {
	    quick2(arr, 0, arr.length - 1);
	  }

	  private static void quick2(int[] arr, int left, int right) {
	    
	    if (left >= right)
	      return;

	    int pivot = left;
	    int lo = left + 1;
	    int hi = right;
	    
	    while (lo <= hi) {
	      while (lo <= right && arr[lo] <= arr[pivot]) 
	        lo++;
	      while (hi > left && arr[hi] >= arr[pivot]) 
	        hi--;
	      if (lo > hi)				 
	        swap(arr, hi, pivot);
	      else
	        swap(arr, lo, hi);			 
	      }
		
	    quick2(arr, left, hi - 1);
	    quick2(arr, hi + 1, right);

	  }
	  private static void swap(int[] arr, int i, int j) {
	    int temp = arr[i];
	    arr[i] = arr[j];
	    arr[j] = temp;
	  }
	  public static void print(int[] a) {
	        for (int i=0;i<a.length;i++)
	            System.out.print(a[i]+" ");
	        System.out.println();
	    }
}

 

 

📍 Test Case 출력 확인

Quick Sort Test case 확인!!