#017 퀵 정렬

# 문제)

아래와 같이 정렬되지 않은 배열이 있을때 퀵 정렬을 사용하여 오름차순 정렬하여라.

5

2

4

3

1

병합 정렬과 거의 유사한 분할&정복 방식임.

다만 병합 정렬의 경우, 새로운 배열을 통해 정렬한 반면 퀵정렬을 pivot값을 기준으로 swap하여 정렬한다.

퀵정렬은 먼저 partition작업을 통해 정렬을 수행한다.

left를 기준값으로 pivot을 잡고 mid=(왼쪽 인덱스+오른쪽 인덱스)/2, low = 왼쪽 인덱스+1, high=오른쪽 인덱스를 초기화한다.

*퀵정렬 효율성을 위해 pivot값 선택을 개선할 수 있음. 일단은 왼쪽을 pivot을 잡도록 하겠음.

low와 high가 겹치지 않을때까지 아래 내용을 반복한다.

low는 오른쪽 방향으로 이동하면서 pivot보다 큰값을 찾는다.

high는 왼족 방향으로 이동하면서 pivot보다 작은 값을 찾는다.

그리고 이 두개를 swap 한다.

low와 high가 겹쳐지면 pivot과 high를 swap해준다.

그리고 pivot값과 swap된 high 인덱스를 반환해줌.

partition작업이 끝나면 넘겨받은 인덱스 기준으로 왼쪽, 오른쪽을 분할하여 퀵정렬을 반복한다. (재귀방법)

package dataStructure.sort.quick;

import java.util.Random;

public class QuickSort {

   

    private int maxSize = 10;

    private int[] array = new int[maxSize];

    private int size = 0;

   

    public QuickSort() {

        // TODO Auto-generated constructor stub

        Random random = new Random();

        int randomNumber = 0;

        for(int i=0;i<maxSize;i++) {

            randomNumber = random.nextInt()%maxSize;

            add( randomNumber >= 0 ? randomNumber : randomNumber*-1);

        }

    }

   

    public void add(int value) {

        array[size++]=value;

    }

   

    public void quickSort(int left, int right) {

        if(left < right) {

            int mid = partition(left, right);

            quickSort(left, mid);

            quickSort(mid+1, right);

        }

    }

   

    public int partition(int left, int right) {

        int pivot = array[left];

        int low = left+1;

        int high = right;

       

        while(low <= high) {

            while(low <= right) {

               if(pivot >= array[low]) {

                   low++;

               }else {

                   break;

               }

            }

       

            while(high >= left+1) {

                if(pivot <= array[high]) {

                    high--;

                }else {

                    break;

                }

            }

           

            if( low <= high ) {

                swap(low, high);

            }

        }

        if(left < high) {

            swap(left, high);

        }

        return high;

    }

   

    private void swap(int frontIndex, int tailIndex) {

        int temp = array[frontIndex];

        array[frontIndex] = array[tailIndex];

        array[tailIndex] = temp;

    }

   

    @Override

    public String toString() {

        StringBuilder result = new StringBuilder();

        result.append("[");

        int i=0;

        while(i<size) {

            result.append(array[i]);

            if(i != size-1) {

                result.append(",");

            }

            i++;

        }

        result.append("]");

        return result.toString();

    }

   

    public int getSize() {

        return size;

    }

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        QuickSort quick = new QuickSort();

        //quick.add(3);quick.add(4);quick.add(1);quick.add(5);quick.add(2);

        System.out.println(quick);

        quick.quickSort(0, quick.getSize()-1);

        System.out.println(quick);

    }

}