정렬

정렬알고리즘은 여러가지가 있는데

솔직히 왜 여러가지 쓰는지 모르겠습니다. 그냥 sort()쓰면 되는거 아닌가요?

근데 책은 샀고 책에 내용은 있으니 하기는 하겠습니다

 

 

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복합니다.

버블 정렬하는 과정

 

import java.util.Scanner;

public class BubbleSort {
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void bubbleSort(int[] a, int n){
        for(int i=0; i<n-1; i++)
            for(int j=n-1; j>i; j--)
                if(a[j - 1] > a[j])
                    swap(a, j-1, j);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("버블 정렬(버전 1)");
        System.out.printf("요솟수:");
        int nx = sc.nextInt();
        int []x = new int[nx];

        for(int i=0;i<nx; i++){
            System.out.printf("x["+i+"]:");
            x[i] = sc.nextInt();
        }

        bubbleSort(x, nx);

        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0;i<nx; i++)
            System.out.println("x["+i+"]="+x[i]);
    }
}

척 보기에도 복잡하지 않고 간답합니다. 하지만 그만큼 성능또한 떨어집니다. 시간 복잡도가 무려 O(n^2)입니다.

 

 

단순 선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 입니다.

static void selectionSort(int[] a, int n){
        for(int i=0; i<n-1; i++){
            int min=i;
            for(int j=i+1; j<n; j++)
                if(a[j] < a[min])
                    min = j;
                swap(a, i, min);
        }
    }

이 또한 시간복잡도가 O(n^2)이기 떄문에 성능을 기대하기는 어렵습니다.

 

 

단순 삽입 정렬은 선택한 요소를 구보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘입니다.

static void insertionSort(int[] a, int n){
        for(int i=1; i<n; i++){
            int j;
            int tmp = a[i];
            for(j=i; j>0 && a[j-1] > tmp; j--)
                a[j] = a[j-1];
            a[j] = tmp;
        }
    }

이 또한 시간 복잡도는 O(n^2)입니다. 셋 다 구리네요.