1_[algorithm]퀵 정렬

퀵 정렬

source: https://upload.wikimedia.org/wikipedia/commons/9/9c/Quicksort-example.gif

• 기준점(pivot) 을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수 작성[보통 맨 앞을 피벗으로 삼고 시작]
• 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 동일 작업을 반복
• 함수는 왼쪽(left) + 기준점(pivot)+ 오른쪽(right)를 리턴

🌟 왼쪽과 오른쪽은 정렬되지 않은 상태이다!

🌟 병합정렬은 끝까지 잘게 쪼개는데, 퀵정렬은 쪼개면서 어느정도 정렬을 해나가고 그 위치에 따라 순서대로 합치면 됨!

먼저, 아래의 리스트를 맨 앞 데이터를 기준으로 , 작은 데이터는 left 변수에 , 그렇지 않은 데이터는 right 변수에 넣어보자

dataList=[4,1,2,5,7]

package sorting.quick;

import java.util.ArrayList;
import java.util.List;

public class Test {

    public static void splitFunc(List<Integer> list){
        int size=list.size();
        int pivot=list.get(0);
        List<Integer> left=new ArrayList<>();
        List<Integer> right=new ArrayList<>();

        if(size<=1){
            return;
        }

        for(int idx=1; idx < size; idx++){
            if(pivot<list.get(idx)){
                right.add(list.get(idx));
            }else{
                left.add(list.get(idx));
            }
        }
        System.out.println("left: "+left);
        System.out.println("right: "+right);
        System.out.println("pivot: "+pivot);

    }

    public static void main(String[] args){
        List<Integer> list= new ArrayList<>();
        list.add(4);
        list.add(1);
        list.add(2);
        list.add(5);
        list.add(7);

        splitFunc(list);
    }
}

위와 같이 생각을 정리해보면, 콘솔에서 다음과 같이 피벗보다 작으면 left에, 크면 right에 분리됨을 확인해볼 수 있다

left: [1, 2]
right: [5, 7]
pivot: 4

참고로, 만약 아래처럼 int 배열에 대해서 arrayList를 만들어주고자 한다면,

new ArrayList<>(Arrays.asList(배열);

Integer를 사용하면 toString 등이 오버라이딩되어 사용하기에 편리할 수 있다

---

➕(확장)

dataList가 다음 세 데이터를 가지고 있을 때 맨 앞의 데이터를 기준으로

• 작은 데이터는 left 변수에 넣고
• 그렇지 않은 데이터는 right변수에 넣고
• left, right, pivot 변수에 들어있는 배열 아이템들을 하나의 배열로 정렬하여 출력해보기

Integer[] dataList={3,4,2}

package sorting.quick;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {

    public static void splitFunc(List<Integer> list){
        List<Integer> temp=new ArrayList<>();
        int size=list.size();
        int pivot=list.get(0);
        List<Integer> left=new ArrayList<>();
        List<Integer> right=new ArrayList<>();

        if(size<=1){
            return;
        }

        for(int idx=1; idx < size; idx++){
            if(pivot<list.get(idx)){
                right.add(list.get(idx));
            }else{
                left.add(list.get(idx));
            }
        }
        System.out.println("left: "+left);
        System.out.println("right: "+right);
        System.out.println("pivot: "+pivot);

        //2단계, 합치기
        left.forEach(i->{
            temp.add(i);
        });

        temp.add(pivot);

        right.forEach(i->{
            temp.add(i);
        });

        System.out.println("step2: merge left, pivot, right: "+temp);

    }

    public static void main(String[] args){
        List<Integer> list= new ArrayList<>(Arrays.asList(3,4,2));
        System.out.println("before: "+list);
        splitFunc(list);

    }
}

before: [3, 4, 2]
left: [2]
right: [4]
pivot: 3
step2: merge left, pivot, right: [2, 3, 4]

위와 동일한 결과를 addAll(리스트)을 이용해서 변경해줄 수도 있다!

package sorting.quick;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {

    public static void splitFunc(List<Integer> list){
        List<Integer> temp=new ArrayList<>();
        int size=list.size();
        int pivot=list.get(0);
        List<Integer> left=new ArrayList<>();
        List<Integer> right=new ArrayList<>();

        if(size<=1){
            return;
        }

        for(int idx=1; idx < size; idx++){
            if(pivot<list.get(idx)){
                right.add(list.get(idx));
            }else{
                left.add(list.get(idx));
            }
        }
        System.out.println("left: "+left);
        System.out.println("right: "+right);
        System.out.println("pivot: "+pivot);

        //2단계, 합치기
        temp.addAll(left);
        temp.addAll(Arrays.asList(pivot));
        temp.addAll(right);

        System.out.println("step2: merge left, pivot, right: "+temp);

    }

    public static void main(String[] args){
        List<Integer> list= new ArrayList<>(Arrays.asList(3,4,2));
        System.out.println("before: "+list);
        splitFunc(list);

    }
}

---

이제 2단계 `합칠 때에 왼쪽과 오른쪽에 대해서 정렬이 필요하므로 재귀적으로 퀵소트를 수행하는 메서드를 부르도록 변경만 해주면 된다!

package sorting.quick;

import java.util.ArrayList;
import java.util.Arrays;

public class QuickSort {

    public ArrayList<Integer> sort(ArrayList<Integer> list){
        ArrayList<Integer> merged=new ArrayList<>();
        int size= list.size();

        if(size<=1){
            return list;
        }
        int pivot =list.get(0);

        ArrayList<Integer> left= new ArrayList<>();
        ArrayList<Integer> right= new ArrayList<>();

        for(int i = 1; i < size; i++){
            if(list.get(i)>pivot){
                right.add(list.get(i));
            }else{
                left.add(list.get(i));
            }
        }

        **merged.addAll(sort(left));
        merged.addAll(Arrays.asList(pivot));
        merged.addAll(sort(right));**

        return merged;

    }

}

package sorting.quick;

import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    public static void main(String[] args){
        QuickSort qs=new QuickSort();
        ArrayList<Integer> arr=new ArrayList<>(Arrays.asList(3,2,5,1,6,4,8,10,9,7));
        System.out.println("Before: "+arr);
        arr=qs.sort(arr);
        System.out.println("After: "+arr);
    }
}

Before: [3, 2, 5, 1, 6, 4, 8, 10, 9, 7]
After: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

그 결과, 정렬된 데이터를 확인해볼 수 있다!

📌 퀵 정렬의 시간복잡도 : O(nlogn)

• 단, 최악의 경우 모든 데이터를 비교하는 상황이 나와서 O(n^2)복잡도가 나올 수도 있다!