[알고리즘] 정렬 (Sort)

1. 선택 정렬 (Selection Sort)

• $O(n^{2})$
• 배열에서 가장 큰 원소를 찾아 배열의 끝자리에 있는 원소와 자리를 바꿈(swap)
• 나머지 원소들에 대해서도 반복

selection sort

package com.company;

public class Main {

    //원본 배열 (정렬x)
    static int A[] = {3,5,1,2,8,7,6,10,9,4};


    static void selection_sort(int list[])
    {
        //가장 큰 값 찾기 + swap 반복
        for(int i=list.length-1;i>=0;i--)
        {
            int max_index = 0;
            int max = list[max_index];

            //가장 큰 값 찾기
            for(int j=0;j<=i;j++)
            {
                if(max < list[j])
                {
                    max = list[j];
                    max_index = j;
                }
            }

            //가장 끝에 있는 원소와 swap
            swap(list,i, max_index);

        }

        //결과 출력 : 
        print_result(list);
    }
    
    static void swap(int list[], int index1,int index2)
    {
        int temp = list[index1];
        list[index1] = list[index2];
        list[index2] = temp;
    }
    static void print_result(int list[])
    {
        for(int i=0;i<list.length;i++)
            System.out.println(list[i]);
    }

    public static void main(String[] args) {

        selection_sort(A);
    }
}

 

​

​

2. 버블 정렬 (Bubble Sort)

• $O(n^{2})$
• 선택 정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업 반복 → but 끝자리로 옮기는 방법만 다름
• 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어있지 않으면 하나씩 바꾸어 나감

bubble sort

package com.company;

public class Main {

    //원본 배열 (정렬x)
    static int A[] = {3,5,1,2,8,7,6,10,9,4};

    static void bubble_sort(int list[])
    {

        for(int i=list.length-1;i>=1;i--)
        {
            for(int j=0;j<i;j++)
            {
                //이웃한 수와 비교 후 본인이 더 크면 swap
                if(list[j] > list[j+1])
                    swap(list,j,j+1);
            }

        }

        //결과 출력 :
        print_result(list);
    }

    static void swap(int list[], int index1,int index2)
    {
        int temp = list[index1];
        list[index1] = list[index2];
        list[index2] = temp;
    }
    static void print_result(int list[])
    {
        for(int i=0;i<list.length;i++)
            System.out.println(list[i]);
    }

    public static void main(String[] args) {

        bubble_sort(A);
    }
}

​

​

​

3. 삽입 정렬 (Insertion Sort)

• $O(n^{2})$
• 이미 정렬되어있는 i개 배열에 하나의 원소를 더 더하여 정렬된 i+1 개 배열을 만드는 과정 반복
• 한 개짜리 배열에서 시작해서 그 크기를 하나씩 늘려감

​

insertion sort

public class Main {

    static int list[] = {0,3,1,4,2,5,6,11,8,9,10,7};

    static void insertionSort(int list[])
    {
        for(int i = 1;i< list.length;i++)
        {
            int j = i - 1;

            while(j >= 0 && list[j] > list[j+1])
            {
                swap(list, j, j+1);
                j--;
            }
        }
    }

    static void print()
    {
        for(int i =0;i< list.length;i++)
            System.out.println(list[i]);
    }

    static void swap(int list[], int a, int b)
    {
        int temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }

    public static void main(String[] args) {

        insertionSort(list);
        print();

    }


}

​

​

​

4. 병합 정렬 (Merge Sort)

• $O(n log {n})$
• 배열을 반으로(전반부, 후반부) 나누고 정렬 후 병합 → 재귀를 이용하여 반복
• 가장 작은 단위부터 차례로 정렬 후 병합

package com.company;

public class Main {

    //원본 배열 (정렬x)
    static int A[] = {3,5,1,2,8,7,6,10,9,4};

    static void mergeSort(int list[], int left, int right)
    {
        if(left < right)
        {
            int mid = (left + right) / 2;
            mergeSort(list, left, mid);//전반부 정렬
            mergeSort(list,mid + 1, right);//후반부 정렬
            merge(list, left, right, mid);//병합
        }
    }

    static void merge(int list[], int left, int right, int mid)
    {
        int i = left;//전반부 시작위치
        int j = mid + 1;//후반부 시작위치
        int k = left;

        //임시 정렬 리스트
        int sorted_list[] = new int[list.length];

        //전반부 혹은 후반부 중 하나가 완전히 다 삽입 될 떄까지
        while(i <= mid && j <= right)
        {
            //전반부 vs 후반부 원소 비교하여 삽입
            if(list[i] < list[j])
                sorted_list[k++] = list[i++];
            else
                sorted_list[k++] = list[j++];
        }

        //삽입덜된 전반부 삽입
        while(i <= mid)
        {
            sorted_list[k++] = list[i++];
        }

        //삽입덜된 후반부 삽입
        while(j <= right)
        {
            sorted_list[k++] = list[j++];
        }

        //원래 list로 복사
        for(k = left;k <= right;k++)
            list[k] = sorted_list[k];
    }

    public static void main(String[] args) {

        mergeSort(A,0, A.length-1);
    }
}

​

​

​

5. 퀵 정렬 (Quick Sort)

• $O(n log{n})$
• Worst Case : $O(n^{2})$
• 기준원소(pivot)를 기준으로 기준원소보다 작은 수는 왼쪽, 큰 수는 오른쪽으로 정렬 -> 정해진 기준원소 위치를 기준으로 분할 후 반복
• 기준원소는 아무 수나 해도 되지만 보통 범위에 맨 뒤에 있는 수를 기준

package com.company;

public class Main {

    //원본 배열 (정렬x)
    static int A[] = {3,5,1,2,8,7,6,10,9,4};

    static void quickSort(int[] list, int p, int r)
    {
        if(p < r)
        {
            int q = partition(list,p,r);//정렬 후 분할위치 q 반환
            quickSort(list,p,q-1);//pivot 위치 q를 기준으로 전반부 정렬
            quickSort(list,q+1,r);//pivot 위치 q를 기준으로 후반부 정렬
        }
    }

    static int partition(int[] list, int p, int r)
    {
        int i = p - 1;//pivot보다 작은 값이 들어갈 위치
        
        int pivot = list[r];

        for(int j = p;j < r;j++)
        {
            if(list[j] < pivot)//현재 값이 pivot보다 작으면 i+1과 swap
            {
                swap(list,i+1,j);
                i++;
            }
        }

        swap(list,i+1,r);//i+1에 pivot값 삽입 (바꾸기)
        return i+1;
    }

    static void swap(int list[],int a, int b)
    {
        int temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }
    public static void main(String[] args) {

        quickSort(A, 0, A.length-1);

    }
}

}

​

6. 힙 정렬 (Heap Sort)

• $O(n logn)$
• 오름차순 정렬엔 최소 힙 구조 사용
• 내림차순 정렬엔 최대 힙 구조 사용
• mergeSort와 달리 임시 배열이 필요하지 않음

 

​1. minHeaplify

: list의 값들을 '마지막 단말 노드의 부모노드부터 heaplify (자식노드들과 비교 후 자기보다 큰 값이 있으면 교환)'

 

2. deleteHeap

: heap의 루트노드의 값을 반환하고 마지막 노드 값을 루트노드에 옮기고 루트 노드에 대하여 heaplify (heap의 삭제과정과 동일)

public class Main {

    static int list[] = {0,3,1,4,2,5,6,11,8,9,10,7};

    static void heapSort(int list[])
    {
        for(int i = (list.length-1)/2;i >= 0;i--)
            minHeaplify(list, i, list.length-1);

        int last = list.length-1;

        for(int i = 0 ;i < list.length; i++)
        {
            System.out.println(deleteHeap(list, last));
            last--;
        }
    }

    //오름차순 정렬
    static void minHeaplify(int heap[], int start, int last)
    {
        int parent = start;
        int child = parent * 2 + 1 ;//왼쪽 자식

        while(child <= last)
        {
            int min = parent;

            if(heap[min] > heap[child])
                min = child;

            //오른쪽 자식 존재
            if(child+1 <= last && heap[min] > heap[child+1])
                min = child+1;

            if(min != parent)
            {
                swap(heap, parent, min);
                parent = min;
                child = parent * 2;
            }
            else
                break;
        }
    }

    static int deleteHeap(int heap[], int last)
    {
        //루트 노드 값 반환
        int value = heap[0];

        //마지막 노드의 값을 임시로 루트 노드에 올려놓는다 -> heap 크기 감소 (last--)
        heap[0] = heap[last--];

        //루트 노드에 대해 heaplify
        minHeaplify(heap, 0, last);

        return value;
    }

    static void swap(int list[], int a, int b)
    {
        int temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }

    public static void main(String[] args) {

        heapSort(list);

    }


}