퀵정렬

https://visualgo.net/en/sorting

기준점(pivot)을 정한다
기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모은다.
나뉘어진 왼쪽, 오른쪽은 다시 각각 기준점을 정하고 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모은다

비주얼고만 보고 구현해봤다. 피벗은 항상 왼쪽끝으로 지정하고 구현해봤다
디버깅하는 시간까지 꽤 오래 걸렸다. 더 간단하게 구현해야야 할까..
메모리는 추가 할당하지 않고 풀 수 있었는데 추가로 메모리를 할당해서 풀면 구조가 더 간단해 지려나?

public class QuickSort {

    private ArrayList<Integer> list;

    QuickSort()
    {
        list = new ArrayList<>();
    }

    void add(Integer value)
    {
        list.add(value);
    }

    void quicksort(int start, int end)
    {
        if(start >= end)
            return;

        int pivot = start;

        int left = start+1;//point bigger value. if not ++
        int right = start+1;//iterater

        while(right <= end)
        {
            if( list.get(pivot) >= list.get(right))
            {
                if(left != right)
                    Collections.swap(list, left, right);

                left++;
            }

            right++;
        }

        Collections.swap(list, start, left-1);

        int leftEnd = left-2;
        if(start < leftEnd)
            quicksort(start, leftEnd);

        if(left < end)
            quicksort(left, end);
    }

    void sort()
    {
        if(list.isEmpty() == true)
            return;
        if(list.size() == 1)
            return;

        quicksort(0, list.size()-1);
    }

    @Override
    public String toString() {
        return "QuickSort{" +
                "list=" + list +
                '}';
    }
}

public class QuickSortTest {

    public static void main(String[] args) {

        QuickSort qs = new QuickSort();

        for(int i = 0; i < 20; ++i)
        {
            qs.add((int)(Math.random()*100));
        }

        qs.sort();

        System.out.println(qs);
    }
}

시간복잡도는 평균 nlogn
최악의 경우 n^2 이다