공부기록/알고리즘

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

taeni-log 2022. 7. 31. 17:58

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

 

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

 

[퀵정렬 구현]

<실행코드> - 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) 구현시 사용된다. 

 

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

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

'공부기록 > 알고리즘' 카테고리의 다른 글

[Algorithm] 퀵 정렬 (Quick Sort)1_JAVA  (0) 2022.07.31
[Algorithm] 자료구조_정렬(Sorting)  (0) 2022.07.30