[정렬알고리즘] 백준 문제 다양한 정렬으로 풀어보기

https://www.acmicpc.net/problem/25305

25305번: 커트라인

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine()," ");

        for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        int temp;
        for(int i=0; i<N-1; i++){
            for(int j=i+1; j<N; j++){
                if(arr[i]<arr[j]){
                    temp = arr[j];
                    arr[j]=arr[i];
                    arr[i]=temp;
                }
            }
        }

        System.out.println(arr[K-1]);
    }
}

해당 문제를 위의 코드로 풀었는데 정렬 알고리즘에 대한 개념이 제대로 박혀있지 않은 채 그냥 정렬을 시킨다는 것에 의의를 두고 푼 것 같아 7가지 정렬을 해당 문제로 정리해보려고 한다. 

 

1. 선택 정렬(selection sort)

• 설명: 제자리 정렬 알고리즘의 하나로 각 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
• 시간 복잡도: O(n^2)
• 과정
  • 주어진 배열에서 최댓값을 찾은 다음 맨 앞에 위치한 값과 교체한다.
  • 맨 앞에 위치한 값을 제외한 배열에서 똑같은 과정을 반복한다. 

int temp, indexMax;
        for(int i=0; i<N-1; i++){
            indexMax=i;
            for(int j=i+1; j<N; j++){
               if(arr[j]>arr[indexMax]){
                   indexMax=j; }
            }
            temp = arr[indexMax];
            arr[indexMax]=arr[i];
            arr[i]=temp;
        }

indexMax라는 변수를 통하여 최대 값이 존재하는 인덱스를 찾아냈다. 이후 정렬의 끝까지 탐색이 끝난 후, indexMax의 값을 인덱스로 가진 값을 맨 앞의 위치에 옮긴다. 

2. 버블 정렬(bubble sort)

• 설명: 선택정렬과 비슷한 알고리즘으로 인접한 두 요소의 대소를 비교해가며 자리를 교환하는 방식이다. 거품이 수면에 올라오는 것과 유사하다고 하여 붙여진 이름이다. 
• 시간 복잡도: O(n^2) // 굉장히 비효율적이다. 
• 과정
  • 처음부터 시작하여 인접한 두 원소의 대소를 비교한다. 배열의 끝까지 반복하면 제일 끝에 제일 큰/작은 원소가 위치하게 되므로 그다음과정에선 제일 끝의 원소를 제외한다.

  int temp;
        for(int i=0; i<N-1; i++){
            for(int j=i+1; j<N-1-i; j++){
                if(arr[j]<arr[j+1]){
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }

 

3. 삽입 정렬(insertion sort)

• 설명: 선택정렬과 비슷한 알고리즘으로 인접한 두 요소의 대소를 비교해가며 자리를 교환하는 방식이다. 거품이 수면에 올라오는 것과 유사하다고 하여 붙여진 이름이다. 
• 시간 복잡도: O(n^2) // 굉장히 비효율적이다. 
• 과정
  • 처음부터 시작하여 인접한 두 원소의 대소를 비교한다. 배열의 끝까지 반복하면 제일 끝에 제일 큰/작은 원소가 위치하게 되므로 그다음과정에선 제일 끝의 원소를 제외한다.

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[] arr = new int[num];

        for(int i=0; i<num; i++){
            arr[i]=Integer.parseInt(br.readLine());
        }

        insertion_sort(arr, num);
        for(int i=0;i<num;i++){
            System.out.println(arr[i]);
        }
    }

    private static void insertion_sort(int[] arr, int num){
        int key;
        for(int i=1; i<num; i++){
            key = arr[i];
            for(int j=i-1;j>=0 && arr[j]>key;j--){
                arr[j+1]= arr[j];
                arr[j]=key;
            }
        }
    }
}

 

4. 퀵 정렬(quick sort)

• 설명
  • 이름과 같이 빠른 정렬이 특징인 정렬이며 제자리 정렬이다. 하나의 피벗을 기준으로 피벗보다 큰 원소들의 부분리스트, 피벗보다 작은 원소들의 부분리스트로 정렬한 후 각 부분리스트에서 다시 같은 과정을 반복한다.
  • 병합 정렬과의 차이점이 있다면 병합 정렬은 두 리스트의 크기가 균등하지만 퀵 정렬은 피봇값을 기준으로 나누어지기 때문에 균등하지 않을 수 있다. (=비균등하다.)
• 시간 복잡도: 
• 과정
  • 1. 리스트 안에 있는 원소중 하나(=피벗)를 고른다.
  • 2. 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 옮긴다.
  • 3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 순환호출을 통하여 같은 과정을 반복한다. 
  • 4. 부분리스트의 크기가 1이 아닐 때까지 반복한 후 인접한 리스트들끼리 합친다. 

https://www.acmicpc.net/problem/2587

2587번: 대표값2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static int[] sort(int[] arr){
        l_pivot_sort(arr,0,arr.length -1);
        return arr;
    }

    private static void l_pivot_sort(int[] arr, int lo, int hi){
        if(lo>=hi){
            return;
        }

        int pivot = partition(arr,lo,hi);

        l_pivot_sort(arr,lo,pivot-1);
        l_pivot_sort(arr,pivot+1,hi);
    }

    private static int partition(int[] arr, int left, int right){

        int lo = left;
        int hi = right;
        int pivot = arr[left];  //부분 리스트의 왼쪽 요소를 피벗으로 설정.

        //lo가 hi보다 작을 때 까지만 반복한다.
        while (lo<hi){

            while (arr[hi] > pivot && lo < hi) {
                hi--;
            }

            while (arr[lo]<=pivot && lo<hi){
                lo++;
            }

            swap(arr,lo,hi);
        }

        swap(arr, left, lo);
        return lo;
    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sum=0;
        int[] arr = new int[5];
        for(int i=0;i<5;i++){
            arr[i]=Integer.parseInt(br.readLine());
            sum+=arr[i];
        }
        System.out.println(sum/5);  //평균값 출력

        sort(arr);
        int value = arr[2];
        System.out.println(value);
    }
}

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

import javax.imageio.plugins.jpeg.JPEGImageReadParam;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int num = Integer.parseInt(br.readLine());
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        quickSort(arr);
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {

        if (start >= end) {
            return;
        }

        int pivot = start;
        int lo = start + 1;
        int hi = end;

        while (lo <= hi) {
            while (lo <= end && arr[lo] <= arr[pivot])
                lo++;
            while (hi > start && arr[hi] > arr[pivot])
                hi--;
            if (lo > hi)
                swap(arr, hi, pivot);
            else
                swap(arr, lo, hi);

            quickSort(arr, start, hi - 1);
            quickSort(arr, hi + 1, end);
        }

    }
    private static void swap( int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

위 문제는 문제의 의도는 정렬 그 자체는 아니였지만 퀵 정렬이 헷갈려서 풀어보았다. 

https://www.acmicpc.net/problem/1546

1546번: 평균

import javax.swing.plaf.basic.BasicButtonUI;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        double[] arr = new double[num];

        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        for(int i=0;i<num;i++){
            arr[i]=Double.parseDouble(st.nextToken());
        }

        quickSort(arr);

        double hiScore=arr[num-1];
        double score=arr[num-1];


        for(int i=0;i<num-1;i++){
            arr[i]=arr[i]/hiScore*100;
            score+=arr[i];
            System.out.println(arr[i]);
        }
        System.out.println(arr[num-1]);
        System.out.println(score/num);
    }

    public static void quickSort(double[] arr){
        quickSort(arr, 0, arr.length-1);
    }

    private static void quickSort(double[] arr, int start, int end){

        if(start>end){
            return;
        }

        int pivot = start;
        int lo = start+1;
        int hi = end;

        while(lo<=hi){
            while(lo<=pivot && arr[lo]<=arr[pivot]){
                lo++;
            }
            while (hi>pivot && arr[hi]>=arr[pivot]){
                hi--;
            }
            if(lo>hi){
                swap(arr,hi,pivot);
            }
            else{
                swap(arr,lo,hi);
            }

            quickSort(arr,start,hi-1);
            quickSort(arr,hi+1,end);
        }


    }

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

이 문제도 마찬가지