[Algorithm] 퀵 정렬 (Quick Sort)2_JAVA

계속 해서 퀵정렬을 살펴보자.

 

우선 앞에서 배운 내용을 바탕으로 퀵정렬을 구현해보면 아래와 같다.

 

[퀵정렬 구현]

<실행코드> - JAVA import java.util.*; public class QuickSort{         private static void quickSort(int[] arr) { //quickSort 함수 선언                quickSort(arr,0,arr.length-1); //정렬을 할 배열을 받아서 시작 위치와 끝나는 위치를 정하기         }         //start, end, 파티션을 나눌 범위를 설정해 인자로 받음         private static void quickSort(int[] arr, int start, int end) { //재귀함수를 본격적으로 호출                int part2 = partition(arr,start,end); //해당 배열의  파티션을 나누고 값을 받아오기                        if(start < part2-1){                               quickSort(arr,start, part2-1);                        }                        if(part2<end){//                                quickSort(arr,part2, end);//                        }                }                 private static int partition(int[] arr, int start, int end) {         //시작은 오른쪽 파티션의 시작값 끝나는 지점은 처음에 받은 배열에 끝나는 값으로 호출                int pivot = arr[(start + end)/2]; //인덱스를 받고, 피벗은 중간값으로 설정                   while(start <= end) {// 시작과 끝이 같은 동안만 반복                        while(arr[start] < pivot)start++;                        while(arr[end] > pivot) end--;                        if(start <= end) {// end와 시작점이 만났는지 확인                                     swap (arr, start, end); //각각을 swap함                               start++;                               end--; /                        }                }                return start;          }         private static void swap(int[] arr, int start, int end) { //swap 함수 정의                int tmp = arr[start];//임시공간에 잠시 담고                arr[start] = arr[end]; // 옮기고                arr[end] = tmp; // 임시 공간에 저장 했던걸 옮긴데이터에 복사         }         private static void printArray(int[] arr){//배열 출력                for(int data : arr) {                        System.out.println(data + ", ");                }                System.out.println();         }                public static void main(String[] args) {                int[] arr= {3,9,4,7,5,0,1,6,8,2};//정렬이 안된 값으로 test 해보기                printArray(arr); // 정렬 전 출력                quickSort(arr);//정렬하기                printArray(arr);//정렬 후 출력         } }

지금 구현된 코드는 피벗의 값을 그냥 중간이라고 임의로 설정한 것이다. 

 

이렇게 코드를 구현할 때 퀵정렬의 시간복잡도는 보통 O(nlogn) 이다.

그 이유는 한번 검색할 때마다 검색하는 시간이 절반씩이라 logn

즉 n만큼의 파티션을 나누는데 나누는 데 나눌때마다 데이터가 절반씩 줄어들기 때문이다. 

 

하지만 피벗값이 만일 가장 작거나 큰값이라면 시간복잡도는 O(n^2) n의 제곱이다. 

- 퀵정렬의 시간복잡도 : O(n log n)
- 재귀함수
: 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식으로 주로 반복문(for,while) 구현시 사용된다. 

 

오늘 퀵정렬의 개념에 대해서 배우고 코드를 짰는데,

아직 내용이 백퍼센트 이해가 된건 아니라 더 공부해보고 나중에는 도움없이 혼자 생각해서 코드를 짜봐야 겠다.